NFA 接受具有 2、5、8、11 ... 1 数量的所有二进制字符串的集合

Question

如何构造一个 NFA，它接受所有字符串 w 的集合，使得 n1(w) mod 3 > 1，其中 n1(w) 是字母表中 w 中 1 的数量 = {0 ,1}?

所以，基本上是一个 NFA，它接受具有 2、5、8、... 个 1 的所有字符串的集合。

我猜该语言的正则表达式是 (0*10*10*)(0*10*10*10*)*

我可以为上面的常规 exp 创建一个 NFA，但我不确定这是否可以进一步减少，或者它一开始是否正确。我是常规语言、DFA、NFA 的新手。请帮助我！

Answer 1

让我在字母表上提出这个 NFA {0,1}:

Q = {A, B, C}
q0 = {A}
F = {C}
d = {(A,0,A)
     (A,1,B)
     (B,0,B)
     (B,1,C)
     (C,0,C)
     (C,1,A)}

请检查是否满足要求。