NFA接受以下语言

Question

我需要构建一个NFA (或DFA)来识别以下语言：L = {w | w mod 3 = 1}。因此，我尝试的方法是让NFA识别可被3整除的数字，然后将1加到其中，但是这种方法比看起来难得多(如果不是不可能的话?)我只做了一个NFA来识别可被3整除的数字。

Answer 1

我假设w将被解释为非负整数的十进制表示(不带前导零)。

有鉴于此，我们可以使用Myhill-Nerode迭代地确定我们需要的状态：

1. 空字符串后面可以跟着L中的任何字符串，以得到L中的字符串。我们将为此调用等效类。注意，这个等价类对应于L的最小DFA的初始状态(如果存在的话)。还请注意，由于空字符串不是非负整数的有效十进制表示形式，所以初始状态不被接受。
2. 字符串0不能用任何东西在L中获取字符串；它导致对应于等效类的死状态。
3. 字符串1、4和7处于L中，因此它们必须对应于新的状态。
4. 字符串2、5和8不在L中，但L中并非所有字符串都引向L中的字符串，它们必须对应于一个新的等价类，我们称之为2。
5. 字符串3、6和9不在L中；但是，在L中，可以用任何东西来得到L中的字符串，这和空字符串是一样的，所以我们不需要一个新的等价类或状态:等价类e.
6. 可以验证每一个两位数字的十进制字符串与上面的一个数字十进制字符串是无法区分的。因此，不需要新的等效类或状态。

要确定转换，只需将转换符号附加到等效类的代表性元素，并查看生成的字符串属于哪个等效类:这将是转换终止的地方。例如，从e到on 0，e到1 on 1，等等。

由于10 =1 (mod 3)，在十进制字符串的末尾添加一个新的数字将导致新的值模3与新的数字模3的值之和为原始数的值模3的总和：

x = a (mod 3)
y = b (mod 3)
x * 10 = x * 1 (mod 3) since 10 = 1 (mod 3)
x . y = x * 10 + y = x * 1 + y = x + y (mod 3)

填入过渡是一项练习。