143
правки
Изменения
часть 4
Начиная с этого момента могут быть использованы только правила 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>
}}
