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

Материал из Викиконспекты
Перейти к: навигация, поиск
(часть 2)
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 7 участников)
Строка 1: Строка 1:
{{Теорема
+
__NOTOC__
 +
{{Лемма
 
|statement=
 
|statement=
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой
+
Для любой формальной грамматики существует машина Тьюринга, распознающая язык этой грамматики.
 
|proof=
 
|proof=
<tex>\Rightarrow</tex> <br>
 
 
Пусть <tex>G = (N, \Sigma, P, S)</tex> — грамматика и <tex>L = L(G)</tex>. Опишем неформально недетерминированную машину Тьюринга <tex>Tm</tex>, допускающую <tex>L</tex>.<br>
 
Пусть <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 = (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>.
 
Вначале <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>.
  
Теперь <tex>Tm</tex> недетерминированно симулирует вывод <tex>G</tex>, начиная с <tex>S</tex>. Каждая сентенциальная форма вывода появляется по порядку между последними двумя <tex>\#</tex>. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с <tex>w</tex>. Если они совпадают, <tex>Tm</tex> допускает.
+
Теперь <tex>Tm</tex> недетерминированно симулирует вывод <tex>G</tex>, начиная с <tex>S</tex>. Каждая [[Формальные грамматики#sform|сентенциальная форма вывода]] появляется по порядку между последними двумя <tex>\#</tex>. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с <tex>w</tex>. Если они совпадают, <tex>Tm</tex> допускает.
  
Формально, пусть <tex>Tm</tex> имеет на ленте <tex>\#w\#A_1A_2...A_k\#</tex>. <tex>Tm</tex> передвигает недетерминированно головку по <tex>A_1A_2...A_k</tex>, выбирая позицию <tex>i</tex> и константу <tex>r</tex> между <tex>1</tex> и максимальной длиной левой части любого правила вывода в <tex>P</tex>. Затем <tex>Tm</tex> проверяет подстроки <tex>A_iA_{i+1}...A_{i+r-1}</tex>. Если <tex>A_iA_{i+1}...A_{i+r-1}</tex> — левая часть некоторого правила вывода из <tex>P</tex>, она может быть заменена на правую часть. <tex>Tm</tex> может сдвинуть <tex>A_{i+r}A_{i+r+1}...A_k\#</tex> либо влево, либо вправо, освобождая или заполняя место, если правая часть имеет длину, отличную от <tex>r</tex>.
+
Формально, пусть <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>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>.
 
Из этой простой симуляции выводов в <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>.
  
<tex>\Leftarrow</tex><br>
+
}}
  
 +
{{Лемма
 +
|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>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>, то вывод никогда не приводит к терминальной строке.
  
Строка 27: Строка 32:
 
# <tex>A_3 \rightarrow [e,B]A_3</tex>
 
# <tex>A_3 \rightarrow [e,B]A_3</tex>
 
# <tex>A_3 \rightarrow e</tex>
 
# <tex>A_3 \rightarrow e</tex>
# <tex>q[a,C] \rightarrow [a,E]p для каждого <tex>a \in \Sigma \cup \{e\}</tex> и каждого <tex>q \in Q</tex> и <tex>С \in \Gamma</tex> такого, что <tex>D(q, C) = (p, E, R)</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>X,J,I</tex> из <tex>\Gamma</tex>, <tex>a</tex> и <tex>b</tex>
+
# <tex>[b, I]q[a,C] \rightarrow p[b,I][a,J]</tex> для каждого <tex>C,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 qqq</tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex>, <tex>C\in \Gamma</tex>, <tex>q \in F</tex>
+
# <tex>[a,C]q \rightarrow qaq</tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex>, <tex>C\in \Gamma</tex>, <tex>q \in F</tex>
# <tex>q[a,C] \rightarrow qqq</tex> для каждого <tex>a \in \Sigma \cup \{e\}</tex>, <tex>C\in \Gamma</tex>, <tex>q \in F</tex>
+
# <tex>q[a,C] \rightarrow qaq</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>q \rightarrow e</tex> для каждого <tex>q \in F</tex>
  
Используя правила 1 и 2 <Br>
+
Используя правила <tex>1</tex> и <tex>2</tex>, <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>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>, а затем  <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>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>.
 +
 
 +
По правилам <tex>6</tex> или <tex>7</tex>:<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] \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>.
 
}}
 
}}
 +
 +
{{Теорема
 +
|statement=
 +
[[Перечислимые языки | Язык]] распознается [[Машина Тьюринга | машиной Тьюринга]] тогда и только тогда, когда он генерируется [[Формальные грамматики | формальной грамматикой]].
 +
}}
 +
 +
== Примеры ==
 +
=== Построение МТ по грамматике ===
 +
{{Задача
 +
|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>.
 +
 +
== См. также ==
 +
*[[Иерархия_Хомского_формальных_грамматик | Иерархия Хомского формальных грамматик]]
 +
 +
== Источники информации ==
 +
* [http://mathhelpplanet.com/static.php?p=porozhdayushchiye-grammatiki  Math Help Planet {{---}} Порождающие грамматики]
 +
* ''И.А. Волкова, А.А. Вылиток, Т.В. Руденко'' {{---}} '''Формальные грамматики и языки. Элементы теории трансляции''', 3-е изд. {{---}} Москва, Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова, 2009 — 115 с. : ISBN 978-5-89407-395-8
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' {{---}} '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)
 +
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Вычислительные формализмы]]

Текущая версия на 19:13, 4 сентября 2022

Лемма:
Для любой формальной грамматики существует машина Тьюринга, распознающая язык этой грамматики.
Доказательство:
[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 \ldots A_k\#[/math]. [math]Tm[/math] передвигает недетерминированно головку по [math]A_1A_2 \ldots A_k[/math], выбирая позицию [math]i[/math] и константу [math]r[/math] между [math]1[/math] и максимальной длиной левой части любого правила вывода в [math]P[/math]. Затем [math]Tm[/math] проверяет подстроки [math]A_iA_{i+1} \ldots A_{i+r-1}[/math]. Если [math]A_iA_{i+1} \ldots A_{i+r-1}[/math] — левая часть некоторого правила вывода из [math]P[/math], она может быть заменена на правую часть. [math]Tm[/math] может сдвинуть [math]A_{i+r}A_{i+r+1} \ldots 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]
Правила:

  1. [math]A_1 \rightarrow q_0A_2[/math]
  2. [math]A_2 \rightarrow [a, a]A_2[/math] для каждого [math]a \in \Sigma[/math]
  3. [math]A_2 \rightarrow A_3[/math]
  4. [math]A_3 \rightarrow [e,B]A_3[/math]
  5. [math]A_3 \rightarrow e[/math]
  6. [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]
  7. [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]
  8. [math][a,C]q \rightarrow qaq[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math], [math]C\in \Gamma[/math], [math]q \in F[/math]
  9. [math]q[a,C] \rightarrow qaq[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math], [math]C\in \Gamma[/math], [math]q \in F[/math]
  10. [math]q \rightarrow e[/math] для каждого [math]q \in F[/math]

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

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

Предположение индукции тривиально для нуля шагов. Предположим, что оно справедливо для [math]k - 1[/math] шагов. Пусть
[math](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)[/math]
за [math]k[/math] шагов. По предположению индукции
[math]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}[/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].

По правилам [math]6[/math] или [math]7[/math]:
[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] \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}][/math], что доказывает предположение индукции.

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

Таким образом, [math]G[/math] может генерировать [math]a_1a_2 \ldots a_n[/math], если [math]a_1a_2 \ldots 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]
Теорема:
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой.

Примеры

Построение МТ по грамматике

Задача:
построить МТ для следующей грамматики:
  1. [math]S \rightarrow 1S1[/math]
  2. [math]S \rightarrow 0S0[/math]
  3. [math]S \rightarrow 1[/math]
  4. [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].

См. также

Источники информации

  • Math Help Planet — Порождающие грамматики
  • И.А. Волкова, А.А. Вылиток, Т.В. РуденкоФормальные грамматики и языки. Элементы теории трансляции, 3-е изд. — Москва, Издательский отдел факультета ВМиК МГУ им. М.В.Ломоносова, 2009 — 115 с. : ISBN 978-5-89407-395-8
  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2008. — 528 с. : ISBN 978-5-8459-1347-0 (рус.)