Изменения

Формально, пусть <tex>Tm</tex> имеет на ленте <tex>\#w\#A_1A_2...\ldots A_k\#</tex>. <tex>Tm</tex> передвигает недетерминированно головку по <tex>A_1A_2...\ldots A_k</tex>, выбирая позицию <tex>i</tex> и константу <tex>r</tex> между <tex>1</tex> и максимальной длиной левой части любого правила вывода в <tex>P</tex>. Затем <tex>Tm</tex> проверяет подстроки <tex>A_iA_{i+1}...\ldots A_{i+r-1}</tex>. Если <tex>A_iA_{i+1}...\ldots A_{i+r-1}</tex> — левая часть некоторого правила вывода из <tex>P</tex>, она может быть заменена на правую часть. <tex>Tm</tex> может сдвинуть <tex>A_{i+r}A_{i+r+1}...\ldots A_k\#</tex> либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от <tex>r</tex>.

Используя правила <tex>1 </tex> и <tex>2</tex>, <Br><tex>A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2]...\ldots [a_n,a_n]A_2</tex>, где <tex>a_i \in \Sigma</tex> для некоторого <tex>i</tex>.

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

Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для <tex>k - 1</tex> шагов. Пусть <br><tex>(q_0,a_1a_2...\ldots a_n,1) \vdash (q_1,X_1X_2...\ldots X_r,j_1) \vdash (q_2,Y_1Y_2...\ldots Y_S,j_2)</tex><br> за <tex>k</tex> шагов. По предположению индукции<br><tex>q_0[a_1,a_1][a_2,a_2]...\ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,X_1][a_2][X_2]...\ldots [a_{r-1},X_{r-1}]q_1[a_{j_1},X_{j_1}]...\ldots [a_{n+m},X_{n+m}</tex>.<br>

По правилам <tex>6 </tex> или <tex>7</tex>:<Br>

Таким образом, <Tex>q_0[a_1,a_1][a_2,a_2]...\ldots [a_n,a_n][e,B]^m \Rightarrow [a_1,Y_1]q_2[a_{j_2},Y_{j_2}]...\ldots [a_{n+m},Y_{n+m}]</tex>, что доказывает предположение индукции.

По правилам <tex>8-, 9, 10, если </tex>:<Br>Eсли <Tex>q \in F</tex>, легко показать что <tex>[a_1,X_1]...\ldots q[a_j,X_j]...\ldots [a_{n+m},X_{n+m}] \Rightarrow^* a_1a_2...\ldots a_n</tex>.

Таким образом, <tex>G</tex> может генерировать <tex>a_1a_2...\ldots a_n</tex>, если <tex>a_1a_2...\ldots a_n</tex> допускается <tex>Tm</tex>. Таким образом, <tex>L(G)</tex> включает все слова, допускаемые <tex>Tm</tex>. Для завершения доказательства необходимо показать, что все слова из <tex>L(G)</tex> допускаются <Tex>Tm</tex>. Индукцией доказывается, что <tex>A_1 \Rightarrow w</tex> только если <Tex>w</tex> допускается <tex>Tm</tex>.

|definition = построить МТ для слудующей следующей грамматики:

* Четыре состояния <tex>\{A,B,Y,N\}</tex>, где <tex>Y</tex> — доупускающее, <tex>N</tex> — недоупускающее<br>;