418
правок
Изменения
→Регулярность языков
Отметим также, что если <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>T_x = T_y => \forall z ( M accepts xz <=> M accepts yz) <=> \forall z (xz \in L(M) <=> yz \in L(M)) <=> x =_{L(M)} y</tex>, где <tex>=_{L(M)}</tex> {{---}} отношение эквивалентности на множестве слов в алфавите. Таким образом, если 2 строки имеют одинаковые таблицы, то тогда они эквивалентны отношением <tex>=_{L(M)}</tex>. Поскольку у нас только конечное число таблиц, отношение <tex>=_{L(M)}</tex> имеет только конечное количество классов эквивалентности, самое большее один для каждой таблицы. По теореме <tex>L(M)</tex> {{---}} регулярный язык.
== Пример ==
