Блог

На моем экзамене был вопрос с просьбой нарисовать автоматы 2 states ("O" and "E") с принятием конечного состояния ba^(n) , for n>=1 и n должно было быть нечетным числом. Я потратил на это 45 минут, и я даже не думаю, что понял это правильно.

Как бы вы это нарисовали?

Мы можем использовать Myhill-Nerode, чтобы доказать, что было запрошено, невозможно. Мы можем проиллюстрировать классы эквивалентности с помощью отношения неразличимости, принятого для этого языка.

Рассмотрим пустую строку, e . За ним может следовать любая строка, L чтобы получить строку L . Поэтому мы имеем класс эквивалентности [e] , соответствующий начальному состоянию автомата. Обратите внимание, что это состояние не принимается, поскольку e не является строкой в языке.

Рассмотрим строку a . За этим не может следовать какая-либо строка для получения строки L , и поэтому это другой класс эквивалентности [a] . Очевидно a , что это не строка в языке, и поэтому это не принимается. Это не может быть тем же состоянием, которое соответствует [e] ; действительно, состояние, соответствующее [e] переходам в состояние, соответствующее [a] на входе a .

Теперь у нас есть два разных непринимающих состояния, которые должны появляться при любом минимальном распознавании DFA L . Поскольку L не является пустым (оставлено в качестве упражнения), в любом минимальном DFA должно быть какое-то другое принимающее состояние (состояния). Следовательно, DFA с двумя состояниями не принимается L . QED

Продолжая анализ, классами эквивалентности являются [e] , [a] , [b] и [ba] . Таблица переходов:

 q     s    q'
[e]   a    [a]
[e]   b    [b]
[a]   a    [a]
[a]   b    [a]
[b]   a    [ba]
[b]   b    [a]
[ba]  a    [b]
[ba]  b    [a]
 

Единственным принимающим состоянием является состояние, соответствующее [ba] .