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

Определение:

Грамматика неукорачивающая, если все правила имеют вид [math]\alpha \to \beta[/math], где [math]|\alpha| \le |\beta|[/math] (возможно правило [math]$S$ \to \varepsilon[/math], но тогда [math]$S$[/math] не встречается в правых частях правил).

Определение:

Грамматика контекстно-зависимая, если все правила имеют вид [math]\alpha A \beta \to \alpha \gamma \beta[/math], где [math]A[/math] - нетерминал, [math]\alpha[/math] и [math]\beta[/math] строки из нетерминалов, [math]\gamma[/math] не пуста (возможно правило [math]$S$ \to \varepsilon[/math], но тогда [math]$S$[/math] не встречается в правых частях правил).

Теорема:

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

Доказательство:

[math]\triangleright[/math]

Рассмотрим правило из [math]\Gamma_1[/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_2[/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]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]\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]

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