Одд DFA для языка

Question

Может кто-то пожалуйста, помогите мне сделать НКУ, который принимает этот язык:

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

Я застрял на этой проблеме в течение нескольких часов в настоящее время. Я не понимаю, где вступает в игру k и как он используется на диаграмме ...

Answer 1

Вот NFA, который проходит 6 состояний вперед, а если есть еще один символ, он останавливается в конечном состоянии. В противном случае он возвращается обратно недетерминированно к началу и за конечным состоянием.

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

Answer 2

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

Мы можем использовать теорему Myhill-Nerode конструктивно производить доказуемо минимальный DFA для этого языка. Это полезное упражнение. Во-первых, определение:

Две строки w и x являются неотличимы по отношению к языковой L тогда и только тогда: (1) для каждой строки y таким образом, что wy находится в L, xy находится в L; (2) для каждой строки z такой, что xz находится в L, wz находится в L.

Проницательность в Myhill-Nerode заключается в том, что если две строки неразличимы w.r.t. регулярный язык, то минимальный DFA для этого языка будет следить за тем, чтобы машина попала в одно и то же состояние для любой строки. Неразличимость рефлексивна, симметрична и транзитивна, поэтому мы можем определить на ней классы эквивалентности. Эти классы эквивалентности непосредственно соответствуют множеству состояний в минимальном DFA. Теперь, чтобы найти классы эквивалентности для нашего языка. Мы считаем, ниточки увеличением длины и увидеть для каждого из них, будь-то ничем не отличается от любой из строк перед ним:

1. e, пустая строка, не имеет строк перед ним. Нам нужно состояние q0, чтобы соответствовать классу эквивалентности, которому принадлежит эта строка. Набор строк, который может появиться после e для достижения строки в L, составляет L; также написано c(c^6)*
2. c, любая строка длины одна, имеет только e перед этим. Однако они не являются неразличимыми; мы можем добавить e к c, чтобы получить ce = c, строка в L, но мы не можем добавить e к e, чтобы получить строку в L, так как e не в L. Поэтому нам необходимо новое состояние q1 для класса эквивалентности, которому принадлежит c. Набор строк, который может появиться после c для достижения строки в L, - (c^6)*.
3. Оказалось, что нужно новое состояние q2; набор строк, которые принимают cc в строку в L, - ccccc(c^6)*. Покажите это.
4. Оказалось, что здесь нужно новое состояние q3; набор строк, которые принимают ccc в строку в L, - cccc(c^6)*. Покажите это.
5. Оказалось, что здесь нужно новое состояние q4; набор строк, которые принимают cccc в строку в L, составляет ccc(c^6)*. Покажите это.
6. Оказалось, что здесь нужно новое состояние q5; набор строк, которые принимают ccccc в строку в L, - cc(c^6)*. Покажите это.
7. Рассмотрим строку cccccc. Какие строки ведут нас к строке в L? Хорошо, c. Таким образом, c следует за любой строкой длины 6. Интересно, что это то же самое, что и L. И у нас уже есть класс эквивалентности для этого: e также может следовать за любой строкой в ​​L, чтобы получить строку в L. cccccc и e неразличимы. Более того: поскольку все строки длины 6 неотличимы от более коротких строк, нам больше не нужно проверять более длинные строки. Гарантируется, что у нашего DFA будет один штат q0 - q5, который мы уже определили. Более того, работа, которую мы сделали выше, определяет переходы нам нужно в нашем DFA, начального состояния и принимающие государства, а также:
   • ДКА будет иметь переход на символ c из состояния q заявить q' если x - строка в классе эквивалентности, соответствующая q, и xc - строка в классе эквивалентности, соответствующая q';
   • Начальным состоянием будет состояние, соответствующее классу эквивалентности, которому принадлежит пустая строка e;
   • Состояние q принимает, если какая-либо строка (следовательно, все строки), принадлежащие классу эквивалентности, соответствующему языку, находится на языке; альтернативно, если набор строк, которые принимают строки в классе эквивалентности для строки в L, содержит e, пустую строку.

Мы можем использовать примечания выше, чтобы записать 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.