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

{{Теорема
|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей]] грамматики <tex>\Gamma_1</tex> существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимая]] грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <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 \ge n</tex>, из <tex> \Gamma_1</tex> заменим набором следующих правил:

<tex>
\begin{tabular}{rcl}
$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,$\\
\end{tabular}
</tex>

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

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

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

По [[Иерархия Хомского формальных грамматик#Класс 1|определению]] в <tex>\Gamma_1</tex> нет правил другого вида. Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Осталось заметить, что по [[Иерархия Хомского формальных грамматик#Класс 1|определению]] получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}

{{Лемма
|id= ==lemma==
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики]] <tex>\gamma</tex> не пуста, поэтому <tex>|\alpha A \beta| \le |\alpha \gamma \beta|</tex>. Следовательно, такая грамматика является неукорачивающей по [[Иерархия Хомского формальных грамматик#Класс 1|определению]].
}}

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