NFA принимает набор всех двоичных строк с 2, 5, 8, 11, ... числом 1 с

Question

Как построить NFA, который принимает множество всех строк w так, что n1 (w) mod 3> 1, где n1 (w) - это число 1 в w по алфавиту = {0,1}?

Итак, в основном NFA, который принимает набор всех строк с 2, 5, 8, ... числом 1 с.

Я думаю, что регулярное выражение для языка будет (0 * 10* 10 *) (0 * 10 * 10 * 10 *) *

Я могу создать 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)}

Пожалуйста, проверьте, удовлетворяет ли оно требованию.