143
правки
Изменения
часть 2
Пусть <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>. Каждая сентенциальная форма вывода появляется по порядку между последними двумя <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>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> Пусть <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>, то вывод никогда не приводит к терминальной строке. Формально, пусть<br><tex>G=(N,\Sigma,P,A_1)</tex>, где <tex>N=([\Sigma \cup \{e\}] \times \Gamma) \cup Q \cup \{A_1,A_2,A_3\}</tex><br>Правила: # <tex>A_1 \rightarrow q_0A_2</tex># <tex>A_2 \rightarrow [a, a]A_2</tex> для каждого <tex>a \in \Sigma</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,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>[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>[a,C]q \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 qqq</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> Используя правила 1 и 2 <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>
}}
