语言的奇特DFA

Question

有没有人能帮我画一个接受这种语言的NFA：

{ w | the length of w is 6k + 1 for some k ≥ 0 }

我已经被这个问题困扰了好几个小时了。我不明白k在哪里起作用，以及它是如何在图表中使用的……

Answer 1

{ w | the length of w is 6k + 1 for some k ≥ 0 }

我们可以使用Myhill-Nerode定理来建设性地产生这种语言的可证明的最小DFA。这是一个很有用的练习。首先，定义如下：

对于语言L而言，两个字符串w和x是不可区分的当且仅当：(1)对于每个字符串y，使得wy在L中，xy在L中；(2)对于每个字符串D10，使得D11在D12中，D13在D14中。

Myhill-Nerode中的洞察是，如果两个字符串是不可区分的w.r.t.一种常规语言，那么该语言的最小DFA将确保机器对于任何一个字符串都处于相同的状态。不可区分性是自反性、对称性和传递性的，因此我们可以在其上定义等价类。这些等价类直接对应于最小DFA中的状态集。现在，找到我们的语言的等价类。我们考虑长度不断增加的字符串，并查看每个字符串是否与之前的任何字符串无法区分：

1. e，空字符串，它之前没有字符串。我们需要一个状态q0来对应于这个字符串所属的等价类。在e之后到达L中的字符串的字符串集本身就是L；也写为L任何长度为1的字符串，在它之前只有e。然而，这些并不是不可区分的；我们可以将e添加到c中以获得ce = c，这是L中的一个字符串，但我们不能将e添加到e中以获得L中的字符串，因为e不在L中。因此，我们需要为c所属的等价类创建一个新的状态q1。在c之后可以到达L中的字符串的字符串集是(c^6)*.
2. It，这里我们需要一个新的状态q2；将cc转换为L中的字符串的字符串集是ccccc(c^6)*。显示这个，

，

1. ，结果是我们需要一个新的状态q3；，在L中，将ccc转换为一个字符串的字符串集合是cccc(c^6)*。显示这个，

，

1. ，结果是我们需要一个新的状态q4；，在L中，将cccc转换为一个字符串的字符串集合是ccc(c^6)*。显示这个，

，

1. ，结果是我们需要一个新的状态q5；，在L中，将ccccc转换为一个字符串的字符串集合是cc(c^6)*。向this.
2. Consider显示字符串cccccc。是什么字符串将我们带到L中的字符串？嗯，c是这样做的。后面跟着任何长度为6的字符串的c也是如此。有趣的是，这与L本身相同。我们已经有了一个与此等价的类：e后面还可以跟L中的任何字符串，以获得L中的字符串。cccccc和e是难以区分的。更重要的是:由于所有长度为6的字符串与较短的字符串无法区分，我们不再需要不断检查较长的字符串。我们的DFA保证会有一个我们已经确定的状态q0 - q5。更重要的是，我们在上面所做的工作定义了我们在DFA中需要的转换，初始状态和接受状态：
   • 如果x是对应于q的等价类中的字符串，而xc是等价类中对应于q';
   • The的字符串，则DFA将在symbol q'上具有从状态q到状态q'的转换；初始状态将是对应于空字符串e所属的等价类的状态；
   • 如果属于对应于该语言的等价类的任何字符串(因此是所有字符串)存在于该语言中，则状态q为accepting；或者，如果将等价类中的字符串作为L中的字符串的字符串集包括e，则为空的take

​

我们可以使用上面的注释以表格形式编写DFA：

q    x    q'
--   --   --
q0   c    q1 //     e + c = c
q1   c    q2 //     c + c = cc
q2   c    q3 //    cc + c = ccc
q3   c    q4 //   ccc + c = cccc
q4   c    q5 //  cccc + c = ccccc
q5   c    q0 // ccccc + c = cccccc ~ e

我们将q0作为初始状态，唯一接受的状态是q1。

Answer 2

这是一个NFA，它前进了6个状态，如果还有一个字符，它就会停在最后一个状态。否则，它将不确定地循环回到开始并越过最终状态。

(Start) S1 -> S2 -> S3 -> S5 -> S6 -> S7 (Final State) -> S8 - (loop forever)
                                                           ^ |
        ^                        v                         |_|
        |________________________| (non deterministically)