如何为特定范围的二进制数绘制 DFA？

Question

我需要学习如何设计接受特定范围内的二进制字符串的 DFA。

一个问题指出 IP 地址中的每个八位字节由 8 位组成，每个八位字节代表一个从 0 到 255 的正整数（含 0 到 255）。然后，我被要求 绘制一个 DFA 以接受字母表 {0, 1} 范围内 119 到 231 范围内所有八位字节的二进制表示。它可以是任何给定的范围，但是解决这样的问题的步骤是什么？

Answer 1

您主要有两类方法：

枚举每个字符串，然后使用 DFA 最小化算法找到大小合理的解决方案。这仅适用于语言有限的情况，例如您的示例。
从语言的已知属性中概括，并直接构建您的 DFA。有时从 NFA 开始在概念上更容易，然后您可以通过算法将其转换为 DFA。

对于您的示例，让我们尝试这两种方法。对于任何一种方法，我们都想看看字符串是什么样的。

(119)10 = (01110111)2
(120)10 = (01111000)2
...
(230)10 = (11100110)2
(231)10 = (11100111)2

使用方法 1，您从具有 9 个状态、8 个线性转换的 DFA 开始。

start -0-> q1 -1-> q2 -1-> q3 -1-> q4 -0-> q5 -1-> q6 -1-> q7 -1-> [q8]
(q8 is an accepting state)

这接受字符串 01110111。现在，添加我们需要接受的内容 01111000:

start -0-> q1 -1-> q2 -1-> q3 -1-> q4 -0-> q5 -1-> q6 -1-> q7 -1-> [q8]
                                    |
                                    1
                                    V
                                   r5 -0-> r6 -0-> r7 -0-> [r8]

此 DFA 接受 01110111 和 01111000。你可以继续这样做，你最终会得到一个非常复杂的类似九头蛇的 DFA，它对语言中的每个单词都有不同的接受状态。然后，您可以运行 DFA 最小化算法来缩小它。

采用方法 2，思考语言中单词的结构。如果可能的话，将它们归类到具有相似结构的组中。例如，任何以 10 开头且长度为 8 的字符串都将被接受（这些是 128 到 191 之间的数字）。所以你可以用一个更简单的 DFA 来匹配它们：

start -1-> q1 -0-> q2 -0,1-> q3 (etc until [q8]).

像这样找到一些相似的类别将有助于减少您必须考虑的分支数量。

如何为特定范围的二进制数绘制 DFA？

How do you draw a DFA for a specific range of binary numbers?

automata

finite-automata

dfa