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

Теорема:

Для любой неукорачивающей грамматики [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 \ge n[/math] из [math] \Gamma_1[/math] заменим набором следующих правил: [math] \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} [/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| \ge |\alpha \gamma \beta|[/math]. Следовательно, такая грамматика является неукорачивающей по определению.

[math]\triangleleft[/math]

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