1
правка
Изменения
м
* [[Детерминированные конечные автоматы]]
Исправлена ошибка в окончании слова
Заметим, что у нас конечное число возможных таблиц
<tex>T_x : Q \cup \{d\} \to Q \cup \{h\}</tex>,
а именно <tex>(k+1)^{k+1}</tex>, где <tex>k</tex> {{---}} размер множество множества <tex>Q</tex>. Таким образом, у нас конечное количество информации о <tex>x</tex>, которое мы может перенести через границу справа от <tex>x</tex>, и которое закодировано у нас в таблицe <tex>T_x</tex>.
Отметим также, что если <tex>T_x=T_y</tex> и автомат допускает строку <tex>xz</tex>, то тогда он допускает и строку <tex>yz</tex>, потому что последовательность состояний , перенесенных через границу <tex>x</tex> и <tex>z</tex> (либо <tex>y</tex> и <tex>z</tex>) в любом направлении , полностью определяется таблицами <tex>T_x=T_y</tex> и строкой <tex>z</tex>. Чтобы допустить строку <tex>xz</tex>, автомат должен в какой-то момент прочитать правый маркер конца строки, находясь в допускающем состоянии <tex>t</tex>.
Теперь мы может использовать теорему Майхилла-Нероуда, чтобы показать, что язык <tex>L(M)</tex> нашего автомата <tex>M</tex> [[Регулярные_языки:_два_определения_и_их_эквивалентность|регулярный]].
Рассмотрим следующий язык <tex>L_n = (a+b)^∗a(a+b)^{n-1}a(a+b)^∗</tex> при <tex>\forall n > 0</tex>.
Он может быть легко распознан с помощью следующего [[Недетерминированные_конечные_автоматы|недетерменированного недетерминированного конечного автомата]].
[[Файл:2dfa_example_1.png|600px]]
== См. также ==
* [[Локальные автоматы]]
* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Другие автоматы]]
