Неукорачивающие и контекстно-зависимые грамматики, эквивалентность — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Рассмотрим правило из <tex>\Gamma_1 = \langle \Sigma, N_1, S \in N_1, P \in N_1^{*}\times (\Sigma\cup N_1)^{*}\rangle</tex>. Будем строить правила для контекстно-зависимой грамматики  <tex>\Gamma_2</tex>. Каждое правило <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \geqslant n</tex>, из <tex> \Gamma_1</tex> заменим набором следующих правил:
 
Рассмотрим правило из <tex>\Gamma_1 = \langle \Sigma, N_1, S \in N_1, P \in N_1^{*}\times (\Sigma\cup N_1)^{*}\rangle</tex>. Будем строить правила для контекстно-зависимой грамматики  <tex>\Gamma_2</tex>. Каждое правило <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \geqslant n</tex>, из <tex> \Gamma_1</tex> заменим набором следующих правил:
  
<tex>
+
      <tex>
\begin{document}{rcl}
+
X_1 X_2 X_3 \ldots X_n \to Z_1 X_2 X_3 \ldots X_n,\\
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n,$\\
+
Z_1 X_2 X_3 \ldots X_n \to Z_1 Z_2 X_3 \ldots X_n,\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n,$\\
+
Z_1 Z_2 X_3 \ldots X_n \to Z_1 Z_2 Z_3 \ldots X_n,\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n,$\\
+
                    \ldots\\
&$\ldots$&\\
+
Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n,\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n,$\\
+
Z_1 Z_2 Z_3 \ldots Z_n \to Y_1 Z_2 Z_3 \ldots Z_n,\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n,$\\
+
Y_1 Z_2 Z_3 \ldots Z_n \to Y_1 Y_2 Z_3 \ldots Z_n,\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n,$\\
+
Y_1 Y_2 Z_3 \ldots Z_n \to Y_1 Y_2 Y_3 \ldots Z_n,\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n,$\\
+
                    \ldots\\
&$\ldots$&\\
+
Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n \to Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m.\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m.$\\
+
      </tex>
\end{document}
 
</tex>
 
  
 
Причём нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex> и <tex>Z_{*} \notin N_1</tex>.
 
Причём нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex> и <tex>Z_{*} \notin N_1</tex>.

Версия 18:17, 30 марта 2018

Теорема:
Для любой неукорачивающей грамматики [math]\Gamma_1[/math] существует эквивалентная контекстно-зависимая грамматика [math]\Gamma_2[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим правило из [math]\Gamma_1 = \langle \Sigma, N_1, S \in N_1, P \in N_1^{*}\times (\Sigma\cup N_1)^{*}\rangle[/math]. Будем строить правила для контекстно-зависимой грамматики [math]\Gamma_2[/math]. Каждое правило [math]X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m[/math], где [math]m \geqslant n[/math], из [math] \Gamma_1[/math] заменим набором следующих правил:

     [math]
X_1 X_2 X_3 \ldots X_n \to Z_1 X_2 X_3 \ldots X_n,\\
Z_1 X_2 X_3 \ldots X_n \to Z_1 Z_2 X_3 \ldots X_n,\\
Z_1 Z_2 X_3 \ldots X_n \to Z_1 Z_2 Z_3 \ldots X_n,\\
                    \ldots\\
Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n,\\
Z_1 Z_2 Z_3 \ldots Z_n \to Y_1 Z_2 Z_3 \ldots Z_n,\\
Y_1 Z_2 Z_3 \ldots Z_n \to Y_1 Y_2 Z_3 \ldots Z_n,\\
Y_1 Y_2 Z_3 \ldots Z_n \to Y_1 Y_2 Y_3 \ldots Z_n,\\
                     \ldots\\
Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n \to Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m.\\
      [/math]

Причём нетерминалы [math]Z_{*}[/math] свои для каждого правила из [math]\Gamma_1[/math] и [math]Z_{*} \notin N_1[/math].

В словах языка, задаваемого грамматикой, не может быть нетерминалов, поэтому если в процессе вывода будет применено правило [math]X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n[/math], то впоследствии должны быть применены все остальные правила. В противном случае нетерминалы [math]Z_1[/math] или [math]Z_n[/math] будут присутствовать в выведенном слове.

Правила вида [math]$K$ \to \varepsilon[/math], где [math]$K$ \in N_1[/math] оставляем без изменений.

По определению в [math]\Gamma_1[/math] нет правил другого вида. Получившаяся грамматика [math]\Gamma_2[/math] является эквивалентной грамматике [math]\Gamma_1[/math], так в результате применения набора правил строка [math]X_1 X_2 \ldots X_n[/math] перейдёт в строку [math]Y_1 Y_2 \ldots Y_m[/math]. Осталось заметить, что по определению получившаяся грамматика [math]\Gamma_2[/math] является контекстно-зависимой.
[math]\triangleleft[/math]
Лемма:
Любая контекстно-зависимая грамматика является неукорачивающей.
Доказательство:
[math]\triangleright[/math]
Заметим, что в определении контекстно-зависимой грамматики [math]\gamma[/math] не пуста, поэтому [math]|\alpha A \beta| \leqslant |\alpha \gamma \beta|[/math]. Следовательно, такая грамматика является неукорачивающей по определению.
[math]\triangleleft[/math]

Таким образом, для любой неукорачивающей грамматики можно построить эквивалентную ей контекстно-зависимую, а любая контекстно-зависимая грамматика является неукорачивающей. Значит, эти грамматики задают один и тот же класс языков.

См. также

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