143
правки
Изменения
Часть 3
Используя правила 1 и 2 <Br>
<tex>A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2]...[a_n,a_n]A_2<tex>, где <tex>a_i \in \Sigma</tex> для некоторого <tex>i</tex>
Предположим, что <tex>Tm</tex> допускает строку <tex>a_1a_2...a_n</tex>. Тогда для некоторого <tex>m</tex> <tex>Tm</tex> использует не более, чем <tex>m</tex> ячеек справа от входа. Используя правило 3, а затем правило 4 <tex>m</tex> раз, и, наконец, правило 5, имеем<br>
<tex>A_1 \Rightarrow^* q_0[a_1,a_1][a_2,a_2]...[a_n,a_n][e,B]^m</tex><br>
Начиная с этого момента могут быть использованы только правила 6 и 7, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в <tex>(\Sigma \cup {e}) \times \Gamma</tex> никогда не меняются. Индукцией по числу шагов <tex>Tm</tex> можно показать, что если <tex>(q_0,a_1a_2...a_n,1)\vdash(q, X_1X_2...X_S,r)</tex>, то <tex>q_0[a_1,a_1][a_2,a_2]...[a_n,a_n][e,B]^m \Rightarrow [a_1,X_1][a_2,X_2]...[a_{r-1},X_{r-1}]q[a_r,X_r]...[a_{n+m},X_{n+m}]</tex>, где <tex> a_1,a_2,...a_n \in \Sigma</tex>, <tex>a_{n+1}=a_{n+2}=...=a_{n+m}=e</tex>, <tex>X_1, X_2,...,X_{n+m} \in \Gamma</tex> и <tex>X_{S+1}=X_{S+2}=...=X_{n+m}=B</tex>
Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для <tex>k - 1</tex> шагов. Пусть
}}
