418
правок
Изменения
→Регулярность языков
== Регулярность языков ==
Рассмотрим длинную входную строку <tex>w_1</tex> и разобьем на две подстроки <tex>w_1=xz</tex>. Так как у нас наш автомат может производить чтение в любом направлении, то граница <tex>x</tex> и <tex>z</tex> может быть пересечена несколько раз. Каждый раз, когда автомат пересекает границу справа налево (то есть из <tex>z</tex> в <tex>x</tex>), он выходит из состояния <tex>q</tex>. Когда пересечение происходит снова слева направо (если оно вообще происходит), то автомат выходит из состояния <tex>p</tex>. Теперь, если 2ДКА перейдет в <tex>x</tex> в состояние <tex>q</tex> заново, то он снова может появиться в состоянии <tex>p</tex>. Более того, состояние <tex>p</tex> зависит исключительно от <tex>q</tex> и <tex>x</tex>. Обозначим такое отношение через записать <tex>T_x(q) = p</tex>. Мы может записать все такие отношения в виде конечной таблицы <tex>T_x : Q \cup \{d\} \to Q \cup \{h\}</tex>, где <tex>Q</tex> {{---}} множество состояний 2ДКА, а <tex>d</tex> и <tex>h</tex> будут описаны ниже.
На входной строке <tex>xz</tex> 2ДКА начнет чтение с левого маркера конца строки. В процессе работы автомата позиция чтения будет меняться. В конце концов это позиция пересечет слева направо границу между <tex>x</tex> и <tex>z</tex>. В первый раз, когда это произойдет в каком-нибудь состоянии <tex>T_x(d)</tex> (для этого мы и выделили <tex>d</tex>). Так же автомат может никогда не выйти из <tex>x</tex>. В таком случае мы запишем <tex>T_x(d) = h</tex>. Состояние <tex>T_x(d)</tex> дает немного информации о <tex>x</tex>, но только конечное количество, поскольку существует только конечное количество вариантов для <tex>T_x(d)</tex>. Отметим, что <tex>T_x(d)</tex> зависит только от <tex>x</tex> и не зависит от <tex>z</tex>. Если на вход подавалась строка <tex>xw</tex> вместо <tex>xz</tex>, то в таком случае при пересечении границы из <tex>x</tex> в <tex>w</tex> автомат также был бы в состоянии <tex>T_x(d)</tex>, потому что его значение до того момента определялось только <tex>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>T_x = T_y => \Rightarrow \forall z ( M \ \text{accepts }\ xz <=> \Leftrightarrow M \ \text{accepts }\ yz) <=/tex> <tex> \Leftrightarrow \forall z (xz \in L(M) <=/tex> <tex> \Leftrightarrow yz \in L(M)) <=> \Leftrightarrow x =_\equiv_{L(M)} y</tex>, где <tex>=_\equiv_{L(M)}</tex> {{---}} [[Отношение_эквивалентности|отношение эквивалентности ]] на множестве слов в алфавите. Таким образом, если 2 строки имеют одинаковые таблицы, то тогда они эквивалентны отношением <tex>=_\equiv_{L(M)}</tex>. Поскольку у нас только конечное число таблиц, отношение <tex>=_\equiv_{L(M)}</tex> имеет только конечное количество [[Отношение_эквивалентности|классов эквивалентности]], самое большее один для каждой таблицы. По теореме <tex>L(M)</tex> {{---}} регулярный язык.
== Пример ==
