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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Грамматика неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
+
{{Определение
 +
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
 +
}}
  
Грамматика контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
+
{{Определение
 +
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
 +
}}
  
 
+
{{Теорема
Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
+
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
 +
|proof=
  
 
Рассмотрим правило из <tex>\Gamma_1</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>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
Строка 34: Строка 39:
  
 
Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
 
Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
 +
}}

Версия 20:44, 13 октября 2010

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


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


Теорема:
Для любой неукорачивающей грамматики [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]X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n[/math]

[math]Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n[/math]

[math]\ldots[/math]

[math]Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n[/math]

[math]Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n[/math]

[math]\ldots[/math]

[math]Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m[/math]

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

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило [math]X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m[/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]\gamma[/math] не пуста, а поэтому [math]|\alpha A \beta| \ge |\alpha \gamma \beta|[/math].

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
[math]\triangleleft[/math]