Изменения

Ещё раз отметим, что <tex>T_x(q)</tex> зависит только от <tex>x</tex> и <tex>q</tex> и не зависит от <tex>z</tex>. Если автомат переходит в <tex>x</tex> справа в состояние <tex>q</tex>, то тогда он появится заново в состоянии <tex>T_x(q)</tex> (или никогда не перейдет, если <tex>T_x(q) = h</tex>), потому что автомат детерминированный, и поведение его поведение полностью определяется <tex>x</tex> и состоянием, в которое он вошел. Если мы запишем <tex>T_x(q)</tex> для каждого состояния <tex>q</tex> вместе с <tex>T_x(d)</tex>, это даст нам всю информацию о <tex>x</tex>, которую можно перенести через границу между <tex>x</tex> и <tex>z</tex>. Все это позволит узнать <tex>T_x(d)</tex> сразу после пересечения границы, а также посмотреть значения <tex>T_x(q)</tex>. Если <tex>y</tex> {{---}} другая строка, такая что <tex>T_y=T_x</tex>, то тогда <tex>x</tex> и <tex>y</tex> будут неразличимы. Заметим, что у нас конечное число возможных таблиц<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>.