Удаление цепных правил из грамматики — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «{{Определение |definition = Правила вида <tex>A \to B</tex> (<tex>A,B</tex> - нетерминалы) называются цепными. }} …»)
 
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
−
|definition = Правила вида <tex>A \to B</tex> (<tex>A,B</tex> - нетерминалы) называются цепными.
+
|definition=
 +
Цепное правило — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
 
}}
 
}}
  
−
Зачастую удобно рассматривать грамматики без цепных правил. Оказывается, что верно следующее утверждение:
+
Наличие цепных правил в грамматике может усложнять доказательства теорем и давать излишние шаги в выводах слов. Научимся удалять цепные правила из грамматики.
  
−
{{Утверждение
+
{{Определение
−
|statement=Для любой контекстно-свободной (К-С) грамматики существует эквивалентная ей К-С грамматика без цепных правил.
+
|definition=
 +
Цепная пара — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=Для любой КС-грамматики <tex>G</tex> существует эквивалентная ей КС-грамматика <tex>G_1</tex> без цепных правил.
 
|proof=
 
|proof=
−
Построим граф. Вершинами в нем будут нетерминальные символы, а ребро из <tex>A</tex> в <tex>B</tex> будет тогда и только тогда, когда есть правило <tex>A \to B</tex>. Сделаем транзитивное замыкание для этого графа и добавим правила, соответствующие новым ребрам. Заметим, что теперь любое выводимое слово можно вывести, используя не более одного '''цепного правила''' подряд. Также нетрудно понять, что новая грамматика эквивалентна старой.
+
Алгоритм удаления цепных правил из грамматики:
 +
 
 +
1) Найти все цепные пары <tex>G</tex>.
 +
 
 +
2) Для каждой пары <tex>(A,B)</tex> добавить к правилам <tex>G_1</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>G</tex>.
 +
 
 +
Найти все цепные пары можно по индукции:
 +
 
 +
'''Базис.''' <tex>(A,A)</tex> {{---}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов.
 +
 
 +
'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.
  
−
Далее, рассмотрим все цепные правила <tex>A \to B</tex>. Пусть из <tex>B</tex> можно вывести: <tex>B \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n</tex>.
+
Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>G</tex>, и только их.
  
−
Тогда добавим следующее правило в нашу грамматику: <tex>A \to \alpha_1 \mid \alpha_2 \mid \dots \mid \alpha_n</tex>. При этом получившаяся грамматика будет тоже эквивалентна исходной.
+
Докажем, что, если грамматика <tex>G_1</tex> построена по грамматике <tex>G</tex> с помощью данного алгоритма, то <tex>L(G_1)=L(G)</tex>, то есть <tex>w\in L(G_1)</tex> тогда и только тогда, когда <tex>w\in L(G)</tex>.
  
−
Заметим, что теперь любое слово можно вывести, не используя цепных правил вовсе. Поэтому удалим их.
+
''Достаточность.'' Предположим, <tex>S\Rightarrow _{G_1}^* w</tex>. Так как каждое правило <tex>G_1</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>G</tex>, за которой следует нецепное правило из <tex>G</tex>, то из <tex>\alpha\Rightarrow _{G_1}\beta</tex> следует <tex>\alpha\Rightarrow _G^*\beta</tex>. Таким образом, каждый шаг порождения в <tex>G_1</tex> может быть заменен одним или несколькими шагами в <tex>G</tex>. Собрав эти последовательности шагов, получим, что <tex>S\Rightarrow _G^* w</tex>.
  
−
Итого, была построена К-С грамматика без цепных правил, эквивалентная исходной.
+
''Необходимость.'' Предположим, что <tex>w\in L(G)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\Rightarrow _{lm}^* w</tex>. Где бы в левом порождении не использовалась цепное правило, переменная в правой части становится крайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>G</tex> можно разбить на последовательность "шагов", в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг". Но по построению <tex>G_1</tex> каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, <tex>S\Rightarrow _{G_1}^* w</tex>.
 
}}
 
}}

Версия 20:37, 6 ноября 2011

Определение:
Цепное правило — правило вида [math]A\rightarrow B[/math], где [math]A[/math] и [math]B[/math] — нетерминалы.


Наличие цепных правил в грамматике может усложнять доказательства теорем и давать излишние шаги в выводах слов. Научимся удалять цепные правила из грамматики.


Определение:
Цепная пара — упорядоченная пара [math](A,B)[/math], в которой [math]A\Rightarrow ^* B[/math], используя только цепные правила.


Теорема:
Для любой КС-грамматики [math]G[/math] существует эквивалентная ей КС-грамматика [math]G_1[/math] без цепных правил.
Доказательство:
[math]\triangleright[/math]

Алгоритм удаления цепных правил из грамматики:

1) Найти все цепные пары [math]G[/math].

2) Для каждой пары [math](A,B)[/math] добавить к правилам [math]G_1[/math] все правила вида [math]A\rightarrow\alpha[/math], где [math]B\rightarrow\alpha[/math] — нецепное правило из [math]G[/math].

Найти все цепные пары можно по индукции:

Базис. [math](A,A)[/math] — цепная пара для любого нетерминала, так как [math]A\Rightarrow ^* A[/math] за ноль шагов.

Индукция. Если пара [math](A,B)[/math] — цепная, и есть правило [math]B\rightarrow C[/math], то [math](A,C)[/math] — цепная пара.

Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики [math]G[/math], и только их.

Докажем, что, если грамматика [math]G_1[/math] построена по грамматике [math]G[/math] с помощью данного алгоритма, то [math]L(G_1)=L(G)[/math], то есть [math]w\in L(G_1)[/math] тогда и только тогда, когда [math]w\in L(G)[/math].

Достаточность. Предположим, [math]S\Rightarrow _{G_1}^* w[/math]. Так как каждое правило [math]G_1[/math] эквивалентно последовательности из нуля или нескольких цепных правил [math]G[/math], за которой следует нецепное правило из [math]G[/math], то из [math]\alpha\Rightarrow _{G_1}\beta[/math] следует [math]\alpha\Rightarrow _G^*\beta[/math]. Таким образом, каждый шаг порождения в [math]G_1[/math] может быть заменен одним или несколькими шагами в [math]G[/math]. Собрав эти последовательности шагов, получим, что [math]S\Rightarrow _G^* w[/math].

Необходимость. Предположим, что [math]w\in L(G)[/math]. Тогда [math]w[/math] имеет левое порождение [math]S\Rightarrow _{lm}^* w[/math]. Где бы в левом порождении не использовалась цепное правило, переменная в правой части становится крайней слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в [math]G[/math] можно разбить на последовательность "шагов", в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой "шаг". Но по построению [math]G_1[/math] каждый из этих шагов может быть выполнен одним ее правилом. Таким образом, [math]S\Rightarrow _{G_1}^* w[/math].
[math]\triangleleft[/math]
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Удаление_цепных_правил_из_грамматики&oldid=12756»