Возможность порождения формальной грамматикой произвольного перечислимого языка

Теорема:

Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой

Доказательство:

[math]\triangleright[/math]

Лемма: Для любой формальной грамматики существует машина Тьюринга, распознающая этот язык Доказательство: [math]\triangleright[/math] Пусть [math]G = (N, \Sigma, P, S)[/math] — грамматика и [math]L = L(G)[/math]. Опишем неформально недетерминированную машину Тьюринга [math]Tm[/math], допускающую [math]L[/math]. [math]Tm = (Q, \Sigma, \Gamma, D, q_0, F)[/math], где [math]\Gamma = T \cup \Sigma \cup \{B,\#,X\}[/math] и [math]B,\#,X \notin N \cup \Sigma[/math] Вначале [math]Tm[/math] содержит на ленте [math]w \in \Sigma^*[/math]. [math]Tm[/math] вставляет [math]\#[/math] перед [math]w[/math], сдвигая все символы [math]w[/math] на одну ячейку вправо, и [math]\#S\#[/math] после [math]w[/math], так что содержимым ленты становится [math]\#w\#S\#[/math]. Теперь [math]Tm[/math] недетерминированно симулирует вывод [math]G[/math], начиная с [math]S[/math]. Каждая сентенциальная форма вывода появляется по порядку между последними двумя [math]\#[/math]. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с [math]w[/math]. Если они совпадают, [math]Tm[/math] допускает. Формально, пусть [math]Tm[/math] имеет на ленте [math]\#w\#A_1A_2...A_k\#[/math]. [math]Tm[/math] передвигает недетерминированно головку по [math]A_1A_2...A_k[/math], выбирая позицию [math]i[/math] и константу [math]r[/math] между [math]1[/math] и максимальной длиной левой части любого правила вывода в [math]P[/math]. Затем [math]Tm[/math] проверяет подстроки [math]A_iA_{i+1}...A_{i+r-1}[/math]. Если [math]A_iA_{i+1}...A_{i+r-1}[/math] — левая часть некоторого правила вывода из [math]P[/math], она может быть заменена на правую часть. [math]Tm[/math] может сдвинуть [math]A_{i+r}A_{i+r+1}...A_k\#[/math] либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от [math]r[/math]. Из этой простой симуляции выводов в [math]G[/math] видно, что [math]Tm[/math] печатает на ленте строку вида [math]\#w\#y\#[/math], [math]y \in V*[/math] в точности, если [math]S \Rightarrow^* y[/math]. Если [math]y = w[/math], [math]Tm[/math] допускает [math]L[/math]. [math]\triangleleft[/math] Лемма: Если язык распознается некоторой машиной Тьюринга то существует формальная грамматика, которая его генерирует. Доказательство: [math]\triangleright[/math] Пусть [math]Tm=(Q,\Sigma,\Gamma,D,q_0,F)[/math] допускает [math]L[/math]. Построим грамматику [math]G[/math], которая недерминированно генерирует две копии представления некоторого слова из [math]\Sigma^*[/math] и затем симулирует поведение [math]Tm[/math] на одной из копий. Если [math]Tm[/math] допускает слово, то G трансформирует вторую копию в терминальную строку. Если [math]Tm[/math] не допускает [math]L[/math], то вывод никогда не приводит к терминальной строке. Формально, пусть [math]G=(N,\Sigma,P,A_1)[/math], где [math]N=([\Sigma \cup \{e\}] \times \Gamma) \cup Q \cup \{A_1,A_2,A_3\}[/math] Правила: [math]A_1 \rightarrow q_0A_2[/math] [math]A_2 \rightarrow [a, a]A_2[/math] для каждого [math]a \in \Sigma[/math] [math]A_2 \rightarrow A_3[/math] [math]A_3 \rightarrow [e,B]A_3[/math] [math]A_3 \rightarrow e[/math] [math]q[a,C] \rightarrow [a,E]p[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math] и каждого [math]q \in Q[/math] и [math]C \in \Gamma[/math] такого, что [math]D(q, C) = (p, E, R)[/math] [math][b, I]q[a,C] \rightarrow p[b,I][a,J][/math] для каждого [math]C,J,I[/math] из [math]\Gamma[/math], [math]a[/math] и [math]b[/math] и [math]p,q \in Q[/math] таких, что [math]D(q, C) = (p, J, L)[/math] [math][a,C]q \rightarrow qaq[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math], [math]C\in \Gamma[/math], [math]q \in F[/math] [math]q[a,C] \rightarrow qaq[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math], [math]C\in \Gamma[/math], [math]q \in F[/math] [math]q \rightarrow e[/math] для каждого [math]q \in F[/math] Используя правила 1 и 2 [math]A_1 \Rightarrow^* q_o[a_1,a_1][a_2,a_2]...[a_n,a_n]A_2\lt tex\gt , где \lt tex\gt a_i \in \Sigma[/math] для некоторого [math]i[/math] Предположим, что [math]Tm[/math] допускает строку [math]a_1a_2...a_n[/math]. Тогда для некоторого [math]m[/math] [math]Tm[/math] использует не более, чем [math]m[/math] ячеек справа от входа. Используя правило 3, а затем правило 4 [math]m[/math] раз, и, наконец, правило 5, имеем [math]A_1 \Rightarrow^* q_0[a_1,a_1][a_2,a_2]...[a_n,a_n][e,B]^m[/math] Начиная с этого момента могут быть использованы только правила 6 и 7, пока не сгенерируется допускающее состояние. Отметим, что первые компоненты ленточных символов в [math](\Sigma \cup {e}) \times \Gamma[/math] никогда не меняются. Индукцией по числу шагов [math]Tm[/math] можно показать, что если [math](q_0,a_1a_2...a_n,1)\vdash(q, X_1X_2...X_S,r)[/math], то [math]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}][/math], где [math] a_1,a_2,...a_n \in \Sigma[/math], [math]a_{n+1}=a_{n+2}=...=a_{n+m}=e[/math], [math]X_1, X_2,...,X_{n+m} \in \Gamma[/math] и [math]X_{S+1}=X_{S+2}=...=X_{n+m}=B[/math] Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для [math]k - 1[/math] шагов. Пусть [math](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)[/math] за [math]k[/math] шагов. По предположению индукции [math]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}[/math] ПУсть [math]E=L[/math], если [math]j_2 = j_1 - 1[/math] и [math]E = R[/math], если [math]j_2 = j_1 + 1[/math]. В этом случае [math]D(q_1, X_{j_1}) = (q_1, Y_{j_1}, E)[/math]. По правилам 6 или 7 [math]q_1[a_{j_1}] \rightarrow [a_{j_1},Y_{j_1}]q_1[/math] или [math][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}][/math] в зависимости от того, равно ли [math]E[/math] значению [math]R[/math] или [math]L[/math] Теперь [math]X_i=Y_i \forall i \neq j_1[/math] Таким образом, [math]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}][/math], что доказывает предположение индукции. По правилам 8-10, если [math]q \in F[/math], легко показать что [math][a_1,X_1]...q[a_j,X_j]...[a_{n+m},X_{n+m}] \Rightarrow^* a_1a_2...a_n[/math]. Таким образом, [math]G[/math] может генерировать [math]a_1a_2...a_n[/math], если [math]a_1a_2...a_n[/math] допускается [math]Tm[/math]. Таким образом, [math]L(G)[/math] включает все слова, допускаемые [math]Tm[/math]. Для завершения доказательства необходимо показать, что все слова из [math]L(G)[/math] допускаются [math]Tm[/math]. Индукцией доказывается, что [math]A_1 \Rightarrow w[/math] только если [math]w[/math] допускается [math]Tm[/math] [math]\triangleleft[/math]

[math]\triangleleft[/math]

Примеры

Задача:

построить МТ для слудующей грамматики: [math]S \rightarrow 1S1[/math] [math]S \rightarrow 0S0[/math] [math]S \rightarrow 1[/math] [math]S \rightarrow 0[/math]

Решением будет МТ, которая изменяет содержимое ленты следующим образом ([math]w, \alpha , \beta \in \{0,1\}^*[/math]):

1. [math]w \Rightarrow \#w\#S\#[/math]
2. [math]\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 S 1 \beta \#[/math] это первое правило грамматики
3. [math]\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 0 S 0 \beta \#[/math] это второе правило грамматики
4. [math]\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 \beta \#[/math] это третье правило грамматики
5. [math]\#w\#\alpha S \beta \# \Rightarrow \#w\#\alpha 1 \beta \#[/math] это четвертое правило грамматики
6. [math]\#w\#w\# \Rightarrow Y[/math], где [math]Y[/math] — допускающее состояние

Причем она перебирает все возможные последовательности применения таких преобразований недетерминированно (если ни одно применить нельзя, МТ возвращает ленту в исходное состояние)

Задача:

написать грамматику, генерирующю язык щаданной МТ: Четыре состояния [math]\{A,B,Y,N\}[/math], где [math]Y[/math] — доупускающее, [math]N[/math] — недоупускающее [math]A \rightarrow A[/math] по единице, головка сдвигается вправо [math]A \rightarrow B[/math] по нулю, головка сдвигается вправо [math]A \rightarrow Y[/math] по пустому символу, головка сдвигается вправо [math]B \rightarrow B[/math] по нулю, головка сдвигается вправо [math]B \rightarrow Y[/math] по пустому символу, головка сдвигается вправо [math]B \rightarrow N[/math] по единице, головка сдвигается вправо

Грамматика будет следующей:

1. [math]A_1 \rightarrow q_A A_2[/math]
2. [math]A_2 \rightarrow [0,0][/math]
3. [math]A_2 \rightarrow [1,1][/math]
4. [math]A_2 \rightarrow A_3[/math]
5. [math]A_3 \rightarrow [e,B]A_3[/math]
6. [math]A_3 \rightarrow e[/math]
7. [math]q_A[0, 0] \rightarrow [0,0]q_A[/math]
8. [math]q_A[1, 0] \rightarrow [1,0]q_A[/math]
9. [math]q_A[e, 0] \rightarrow [e,0]q_A[/math]
10. [math]q_A[0, 1] \rightarrow [0,1]q_B[/math]
11. [math]q_A[1, 1] \rightarrow [1,1]q_B[/math]
12. [math]q_A[e, 1] \rightarrow [e,1]q_B[/math]
13. [math]q_A[0, 1] \rightarrow [0,0]q_B[/math]
14. [math]q_A[0, B] \rightarrow [0,B]q_Y[/math]
15. [math]q_A[1, B] \rightarrow [1,B]q_Y[/math]
16. [math]q_A[e, B] \rightarrow [e,B]q_Y[/math]
17. [math]q_Y[0, 0] \rightarrow q_Y0q_Y[/math]
18. [math]q_Y[1, 0] \rightarrow q_Y1q_Y[/math]
19. [math]q_Y[e, 0] \rightarrow q_Yq_Y[/math]
20. [math]q_Y[0, 1] \rightarrow q_Y0q_Y[/math]
21. [math]q_Y[1, 1] \rightarrow q_Y1q_Y[/math]
22. [math]q_Y[e, 1] \rightarrow q_Yq_Y[/math]
23. [math]q_Y[0, B] \rightarrow q_Y0q_Y[/math]
24. [math]q_Y[1, B] \rightarrow q_Y1q_Y[/math]
25. [math]q_Y[e, B] \rightarrow q_Yq_Y[/math]
26. [math]q_Y \rightarrow e[/math]