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

Материал из Викиконспекты
Перейти к: навигация, поиск
(часть 1)
 
(часть 2)
Строка 6: Строка 6:
 
Пусть <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>. Каждая сентенциальная форма вывода появляется по порядку между последними двумя <tex>\#</tex>. Если некоторый выбор переходов ведет к терминальной строке, она сравнивается с <tex>w</tex>. Если они совпадают, <tex>Tm</tex> допускает.
Строка 12: Строка 12:
 
Формально, пусть <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...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>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>
 
}}
 
}}

Версия 04:51, 19 января 2012

Теорема:
Язык распознается машиной Тьюринга тогда и только тогда, когда он генерируется формальной грамматикой
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow[/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]\Leftarrow[/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 для каждого \lt tex\gt a \in \Sigma \cup \{e\}[/math] и каждого [math]q \in Q[/math] и [math]С \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]X,J,I[/math] из [math]\Gamma[/math], [math]a[/math] и [math]b[/math]
  8. [math][a,C]q \rightarrow qqq[/math] для каждого [math]a \in \Sigma \cup \{e\}[/math], [math]C\in \Gamma[/math], [math]q \in F[/math]
  9. [math]q[a,C] \rightarrow qqq[/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]

Используя правила 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]\triangleleft[/math]