由 1 的 NFA 分隔的一对零？

Question

我正在研究一种语言 L = { 每对零由长度为 4i 的 1 分隔，i>=0 }

例如110011110 应该被接受，因为前两个零之间没有任何分隔。然后下一对被4个分开。

这是我对 NFA 的尝试，还有什么遗漏吗？

Answer 1

我们可以直接使用 Myhill-Nerode 来为这种语言推导出一个最小的 DFA。推理很简单。

e，空字符串，可以跟在L中的任意字符串，得到L中的字符串。
0 可以后跟 1* 或 (1^4i)L 以获得 L 中的字符串。
1后面可以跟L，得到L中的字符串。这意味着它与空字符串没有区别。这也意味着我们不需要担心以 1 开头的较长字符串，因为它们将被不以 1 开头的较短字符串覆盖。
00 后面可以跟 0 一样的东西，所以没区别。这也意味着我们无需担心以 00 开头的较长字符串，因为它们由不以 00 开头的较短字符串处理。
01 后面可以跟 1* 或 111(1^4i)L 得到 L 中的字符串。
10、11以1开头可以忽略（见3）
000、001可以忽略，因为它们都是00开头的（见4）
010 后面不能跟任何东西来得到 L 中的字符串。我们也可以忽略以此开头的任何东西，因为它不能导致 L 中的字符串。
011 后面可以跟 1* 或 11(1^4i)L 得到 L 中的字符串。
100, 101, 110, 111 可以忽略，因为它们以 1 开头（见 3）
0000、0001、0010、0011可以忽略，因为它们都是以00开头的（见4）
0100、0101可以忽略，因为它们都是以010开头的（见8）
0110 后面不能跟任何内容以获取 L 中的字符串，因此与 010 无法区分。
0111后面可以跟1*或1(1^4i)L得到L中的字符串。
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111都可以忽略，因为都是1开头（见3）
唯一可以区别于较短字符串的长度为 4 的字符串是 0111； 01110 与 010 没有区别，因为没有任何东西将它引向 L 中的字符串，而 01111 与 0 没有区别，因为它可以后跟 1* 或 (1^4i)L 以得到 L 中的某些内容。

这看起来工作量很大，但实际上是一个非常简单的练习。我们可以返回并列出我们完整的最短长度可区分字符串集：

e，从上面的第 1 点开始
0，从上面的第 2 点开始
01，来自上面第 5 行
010，从上面第 8 点开始
011，从上面第 9 点开始
0111，从上面第 14 点开始

要写下 DFA，我们需要为这些最短长度的可区分字符串中的每一个提供一个状态。从对应于字符串 x 的状态的转换将导致对应于通过将输入符号连接到 x 形成的字符串的状态。所以：

            ___________________________
            |                         ^
        0   V  1       1        1     | 1
--->(e)--->(0)--->(01)--->(011)--->(0111)
    \_/    \_/      | 0     | 0       | 0
     1      0       |       V         V
                    |<-----------------
                    V
                    (010)
                    \___/
                     0,1

e为初始状态
e 的状态在 1 上循环到自身，因为 e.1 = 1 并且 1 与 e 没有区别。无法区分的字符串导致最小 DFA 中的相同状态。
e 的状态在 0 上进入 0 的状态，因为 e.0 = 0 并且 0 与所有长度相同或更短的字符串是可区分的。
状态 0 导致状态 01 导致状态 011 在 1 上导致状态 0111，因为 0111 = 011.1 = 01.1.1 = 0.1.1.1 并且这些都可以与相同或更短长度的字符串区分开来。
0111 在 1 上导致 0，因为 0111.1 = 01111 与 0 没有区别。
状态 0、01、011 和 0111 在 0 上导致状态 010，因为 0.0 = 00、01.0 = 010、011.0 = 0110 和 0111.0 = 01110 与 010 没有区别。
010 在所有输入上都指向自身，因为无法向其添加任何内容以获得 L 中的字符串，因此对于在前面与此进行任何连接也是如此。

现在我们有了结构，我们只需要查看每个状态并判断其规范字符串是否在 L 中。如果是，则该状态正在接受；否则就不是。

e 在 L 中，所以 (e) 正在接受。
0 在 L 中，所以 (0) 正在接受。
01 在 L，所以 (01) 正在接受。
010 在 L 中，所以 (010) 不接受。
011 在 L 中，所以 (011) 正在接受。
0111 在 L，所以 (0111) 正在接受。

这样就完成了L的最小DFA的推导。

由 1 的 NFA 分隔的一对零？

Pair of Zeros separated by 1's NFA?

finite-automata

dfa

nfa

computation-theory