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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 21 промежуточная версия 8 участников)
Строка 1: Строка 1:
{{Определение
 
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$  \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
 
}}
 
 
{{Определение
 
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$  \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
 
}}
 
 
 
{{Теорема
 
{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
+
|statement=Для любой [[Иерархия Хомского формальных грамматик#Класс 1 | неукорачивающей]] грамматики <tex>\Gamma_1</tex> существует эквивалентная [[Иерархия Хомского формальных грамматик#Класс 1 |контекстно-зависимая]] грамматика <tex>\Gamma_2</tex>.
 
|proof=
 
|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 = \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_2</tex> следующий набор правил:
 
  
 
<tex>
 
<tex>
\begin{tabular}{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$\\
+
\vdots\\
&$\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$\\
+
\vdots\\
&$\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$\\
 
\end{tabular}
 
 
</tex>
 
</tex>
  
Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</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 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</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>\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>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью
+
Правила вида <tex>$K$  \to \varepsilon</tex>, где <tex>$K$ \in N_1</tex> оставляем без изменений.
  
Получившаяся грамматика <tex>\Gamma_2</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=Любая контекстно-зависимая грамматика является неукорачивающей.
 
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
+
|proof= Заметим, что в [[Иерархия Хомского формальных грамматик#Класс 1|определении контекстно-зависимой грамматики]] <tex>\gamma</tex> не пуста, поэтому <tex>|\alpha A \beta| \leqslant |\alpha \gamma \beta|</tex>. Следовательно, такая грамматика является неукорачивающей по [[Иерархия Хомского формальных грамматик#Класс 1|определению]].
 
}}
 
}}
  
Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, а также любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.
+
Таким образом, для любой неукорачивающей грамматики можно построить эквивалентную ей контекстно-зависимую, а любая контекстно-зависимая грамматика является неукорачивающей. Значит, эти грамматики задают один и тот же класс языков.
 +
 
 +
== См. также ==
 +
* [[Иерархия Хомского формальных грамматик]] <br \>
 +
* [[Формальные грамматики]]
 +
 
 +
== Источники информации ==
 +
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
* [https://ru.wikipedia.org/wiki/%D0%98%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%A5%D0%BE%D0%BC%D1%81%D0%BA%D0%BE%D0%B3%D0%BE Википедия {{---}} Иерархия Хомского]
 +
* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D1%82%D0%B5%D0%BA%D1%81%D1%82%D0%BD%D0%BE-%D0%B7%D0%B0%D0%B2%D0%B8%D1%81%D0%B8%D0%BC%D0%B0%D1%8F_%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0 Википедия {{---}} Контекстно-зависимая грамматика]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Базовые понятия о грамматиках]]

Текущая версия на 19:20, 4 сентября 2022

Теорема:
Для любой неукорачивающей грамматики [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,\\ \vdots\\ 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,\\ \vdots\\ 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]

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

См. также

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