NFA验收混乱

Question

我在一门高级理论课上，主修计算机科学，任务是设计一个NFA。如果我没记错的话，如果NFA中的任何路径可以接受字符串并进入接受状态，NFA就会接受输入。我理解并且能够很好地创建DFA，并且理解DFA表达问题的需要，而这些问题在等价的DFA中要大得多。但我对NFA必须有多具体才能接受一些东西感到有点困惑。

例如，我的一个家庭作业问题如下：

给出{w x w^R |x∈{0，1}∗，w∈{0，1}^2}的NFA，

其中，如果我解释正确的话，w^R是字符串w的反转，x是任意长度的二进制字符串，w是"00"，"01"，"10“，"11”。

因此，本质上，NFA将接受以w开头的字符串，有一些字符串x，然后以w的反转结束。

我已经正确地设计了，尽管在之前的家庭作业中为此设计了非常大的DFA，但我确信这个练习是为了告诉我，在某些情况下，NFA比DFA更容易使用。我想出了这样的答案：

http://s1056.photobucket.com/user/pcd132/media/Untitled_zps4317347c.jpg.html

这个NFA几乎可以接受任何非空的二进制字符串，那么它能满足这个问题吗？我只是对这样一个概念感到困惑:如果它以某种方式接受了某种东西，那么它就应该被接受。或者我应该以一种只接受条件而不接受其他条件的方式来构建它？如果我不理解这一点，谢谢你的帮助和澄清。

Answer 1

您将希望NFA接受您的语言中的所有字符串，而只接受您的语言中的字符串。只接受其中之一是不够的(因为E*的NFA足以获取所有字符串，而不接受任何内容的NFA则足以获取字符串)。

有很多方法可以为这种语言生成NFA。一种方法是首先添加7个状态，这些状态包含所有4个长度为2的二进制字符串。每个状态在0或1上循环到自己以接受任何x，然后以开始构造w^R的方式移动到唯一状态。这些状态中的每个状态依次移动到接受状态，以完成w^R并接受。