143
правки
Изменения
точки, точки, точечки
{{Теорема
|statement=
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой.
|proof=
{{Лемма
|statement=
Для любой формальной грамматики существует машина Тьюринга, распознающая этот язык.
|proof=
Пусть <tex>G = (N, \Sigma, P, S)</tex> — грамматика и <tex>L = L(G)</tex>. Опишем неформально недетерминированную машину Тьюринга <tex>Tm</tex>, допускающую <tex>L</tex>.<br>
<tex>Tm = (Q, \Sigma, \Gamma, D, q_0, F)</tex>, где <tex>\Gamma = T \cup \Sigma \cup \{B,\#,X\}</tex> и <tex>B,\#,X \notin N \cup \Sigma</tex>.<br>
Вначале <tex>Tm</tex> содержит на ленте <tex>w \in \Sigma^*</tex>. <tex>Tm</tex> вставляет <tex>\#</tex> перед <tex>w</tex>, сдвигая все символы <tex>w</tex> на одну ячейку вправо, и <tex>\#S\#</tex> после <tex>w</tex>, так что содержимым ленты становится <Tex>\#w\#S\#</tex>.
Используя правила 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> шагов. Пусть <br><tex>(q_0,a_1a_2...a_n,1) \vdash (q_1,X_1X_2...X_r,j_1) \vdash (q_2,Y_1Y_2...Y_S,j_2)</tex><br> за <tex>k</tex> шагов. По предположению индукции<br>
<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_1[a_{j_1},X_{j_1}]...[a_{n+m},X_{n+m}</tex>.<br>ПУсть Пусть <tex>E=L</tex>, если <tex>j_2 = j_1 - 1</tex> и <tex>E = R</tex>, если <tex>j_2 = j_1 + 1</tex>. В этом случае <tex>D(q_1, X_{j_1}) = (q_1, Y_{j_1}, E)</tex>.
По правилам 6 или 7:<Br>
<tex>q_1[a_{j_1}] \rightarrow [a_{j_1},Y_{j_1}]q_1</tex> или <Br>
<tex>[a_{j_1-1},X_{j_1-1}]q_1[a_{j_1},X_{j_1}] \rightarrow q_2[a_{j_1-1}, X_{j_1-1}][a_{j_1}, Y_{j_1}]</tex><Br>
в зависимости от того, равно ли <tex>E</tex> значению <tex>R</tex> или <tex>L</tex>.
Теперь <tex>X_i=Y_i \forall i \neq j_1</tex>.
Таким образом, <Tex>q_0[a_1,a_1][a_2,a_2]...[a_n,a_n][e,B]^m \Rightarrow [a_1,Y_1]q_2[a_{j_2},Y_{j_2}]...[a_{n+m},Y_{n+m}]</tex>, что доказывает предположение индукции.
По правилам 8-10, если <Tex>q \in F</tex>, легко показать что <tex>[a_1,X_1]...q[a_j,X_j]...[a_{n+m},X_{n+m}] \Rightarrow^* a_1a_2...a_n</tex>.
Таким образом, <tex>G</tex> может генерировать <tex>a_1a_2...a_n</tex>, если <tex>a_1a_2...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>.
}}
