36
правок
Изменения
Нет описания правки
__NOTOC__{{ТеоремаЛемма
|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>.
Теперь <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...\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>.
{{Лемма
|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>1 </tex> и <tex>2 </tex>, <Br><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]A_2[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_i 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 (рус.)
[[Категория: Теория вычислимости]]
[[Категория: Вычислительные формализмы]]
