143
правки
Изменения
примеры, разбил доказательство
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой
|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>G</tex> видно, что <tex>Tm</tex> печатает на ленте строку вида <tex>\#w\#y\#</tex>, <tex>y \in V*</tex> в точности, если <tex>S \Rightarrow^* y</tex>. Если <tex>y = w</tex>, <tex>Tm</tex> допускает <tex>L</tex>.
{{Лемма
|statement=
Если язык распознается некоторой машиной Тьюринга то существует формальная грамматика, которая его генерирует.
|proof=
Пусть <tex>Tm=(Q,\Sigma,\Gamma,D,q_0,F)</tex> допускает <tex>L</tex>. Построим грамматику <tex>G</tex>, которая недерминированно генерирует две копии представления некоторого слова из <tex>\Sigma^*</tex> и затем симулирует поведение <tex>Tm</tex> на одной из копий. Если <tex>Tm</tex> допускает слово, то G трансформирует вторую копию в терминальную строку. Если <tex>Tm</tex> не допускает <tex>L</tex>, то вывод никогда не приводит к терминальной строке.
# <tex>A_3 \rightarrow [e,B]A_3</tex>
# <tex>A_3 \rightarrow e</tex>
# <tex>q[a,C] \rightarrow [a,E]p </tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex> и каждого <tex>q \in Q</tex> и <tex>С C \in \Gamma</tex> такого, что <tex>D(q, C) = (p, E, R)</tex># <tex>[b, I]q[a,C] \rightarrow p[b,I][a,J]</tex> для каждого <tex>XC,J,I</tex> из <tex>\Gamma</tex>, <tex>a</tex> и <tex>b</tex> и <tex>p,q \in Q</tex> таких, что <tex>D(q, C) = (p, J, L)</tex># <tex>[a,C]q \rightarrow qqqqaq</tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex>, <tex>C\in \Gamma</tex>, <tex>q \in F</tex># <tex>q[a,C] \rightarrow qqqqaq</tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex>, <tex>C\in \Gamma</tex>, <tex>q \in F</tex>
# <tex>q \rightarrow e</tex> для каждого <tex>q \in F</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>
}}
}}
== Примеры ==
{{Задача
|definition = построить МТ для слудующей грамматики:
#<tex>S \rightarrow 1S1</tex>
#<tex>S \rightarrow 0S0</tex>
#<tex>S \rightarrow 1</tex>
#<tex>S \rightarrow 0</tex>
}}
Решением будет МТ, которая изменяет содержимое ленты следующим образом (<tex>w, \alpha , \beta \in \{0,1\}^*</tex>):
#<tex>w \Rightarrow \#w\#S\#</tex>
#<tex>\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 S 1 \beta \#</tex> это первое правило грамматики
#<tex>\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 0 S 0 \beta \#</tex> это второе правило грамматики
#<tex>\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 \beta \#</tex> это третье правило грамматики
#<tex>\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 \beta \#</tex> это четвертое правило грамматики
#<tex>\#w\#w\# \Rightarrow Y</tex>, где <tex>Y</tex> — допускающее состояние
Причем она перебирает все возможные последовательности применения таких преобразований недетерминированно (если ни одно применить нельзя, МТ возвращает ленту в исходное состояние)
{{Задача
|definition = написать грамматику, генерирующю язык щаданной МТ:<br>
* Четыре состояния <tex>\{A,B,Y,N\}</tex>, где <tex>Y</tex> — доупускающее, <tex>N</tex> — недоупускающее<br>
* <tex>A \rightarrow A</tex> по единице, головка сдвигается вправо
* <tex>A \rightarrow B</tex> по нулю, головка сдвигается вправо
* <tex>A \rightarrow Y</tex> по пустому символу, головка сдвигается вправо
* <tex>B \rightarrow B</tex> по нулю, головка сдвигается вправо
* <tex>B \rightarrow Y</tex> по пустому символу, головка сдвигается вправо
* <tex>B \rightarrow N</tex> по единице, головка сдвигается вправо
}}
Грамматика будет следующей:
#<tex>A_1 \rightarrow q_A A_2</tex>
#<tex>A_2 \rightarrow [0,0]</tex>
#<tex>A_2 \rightarrow [1,1]</tex>
#<tex>A_2 \rightarrow A_3</tex>
#<tex>A_3 \rightarrow [e,B]A_3</tex>
#<tex>A_3 \rightarrow e</tex>
#<tex>q_A[0, 0] \rightarrow [0,0]q_A</tex>
#<tex>q_A[1, 0] \rightarrow [1,0]q_A</tex>
#<tex>q_A[e, 0] \rightarrow [e,0]q_A</tex>
#<tex>q_A[0, 1] \rightarrow [0,1]q_B</tex>
#<tex>q_A[1, 1] \rightarrow [1,1]q_B</tex>
#<tex>q_A[e, 1] \rightarrow [e,1]q_B</tex>
#<tex>q_A[0, 1] \rightarrow [0,0]q_B</tex>
#<tex>q_A[0, B] \rightarrow [0,B]q_Y</tex>
#<tex>q_A[1, B] \rightarrow [1,B]q_Y</tex>
#<tex>q_A[e, B] \rightarrow [e,B]q_Y</tex>
#<tex>q_Y[0, 0] \rightarrow q_Y0q_Y</tex>
#<tex>q_Y[1, 0] \rightarrow q_Y1q_Y</tex>
#<tex>q_Y[e, 0] \rightarrow q_Yq_Y</tex>
#<tex>q_Y[0, 1] \rightarrow q_Y0q_Y</tex>
#<tex>q_Y[1, 1] \rightarrow q_Y1q_Y</tex>
#<tex>q_Y[e, 1] \rightarrow q_Yq_Y</tex>
#<tex>q_Y[0, B] \rightarrow q_Y0q_Y</tex>
#<tex>q_Y[1, B] \rightarrow q_Y1q_Y</tex>
#<tex>q_Y[e, B] \rightarrow q_Yq_Y</tex>
#<tex>q_Y \rightarrow e</tex>
