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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Цепное правило — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
+
'''Цепное правило''' (''unit rule'') — правило вида <tex>A\rightarrow B</tex>, где <tex>A</tex> и <tex>B</tex> — нетерминалы.
 
}}
 
}}
  
Наличие цепных правил в грамматике может усложнять доказательства теорем и давать излишние шаги в выводах слов. Научимся удалять цепные правила из грамматики.
+
== Постановка задачи ==
 +
Пусть  <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. <br>
 +
Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].
  
 
==Алгоритм==
 
==Алгоритм==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Цепная пара — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
+
'''Цепная пара''' (''unit pair'') — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.
 
}}
 
}}
  
 
Алгоритм удаления цепных правил из грамматики:
 
Алгоритм удаления цепных правил из грамматики:
 
+
#Найти все цепные пары в грамматике <tex>\Gamma</tex>.
1) Найти все цепные пары <tex>G</tex>.
+
#Для каждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>\Gamma</tex>.
 
+
#Удалить все цепные правила
2) Для каждой цепной пары <tex>(A,B)</tex> добавить к правилам <tex>G_1</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---}} нецепное правило из <tex>G</tex>.
 
  
 
Найти все цепные пары можно по индукции:
 
Найти все цепные пары можно по индукции:
Строка 24: Строка 25:
 
'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.
 
'''Индукция.''' Если пара <tex>(A,B)</tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара.
  
Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>G</tex>, и только их.
+
Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их.
  
==Корректность алгоритма==
+
===Корректность алгоритма===
 
{{Теорема
 
{{Теорема
|statement=Для любой [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматики]] <tex>G</tex> существует эквивалентная ей [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|КС-грамматика]] <tex>G_1</tex> без цепных правил.
+
|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>
 
|proof=
 
|proof=
 +
<tex>\Rightarrow </tex> <br>
 +
Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. <br>
 +
Пусть <tex>w\in L(\Gamma)</tex>. Тогда <tex>w</tex> имеет левое порождение <tex>S\overset{*}{\underset{lm}{\Rightarrow}} w</tex>. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в <tex>\Gamma</tex> можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma')</tex>.
 +
 +
<tex>\Leftarrow </tex> <br>
 +
Покажем, что <tex>L(\Gamma') \subseteq L(\Gamma)</tex>. <br>
 +
Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>\Gamma</tex>, за которой следует нецепное правило из <tex>\Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\overset{*}{\underset{\Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma)</tex>.
 +
 +
}}
 +
 +
=== Время работы алгоритма ===
 +
Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</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>
 +
\begin{array}{l l}
 +
    A\rightarrow B|a\\
 +
    B\rightarrow C|b\\
 +
    C\rightarrow DD|c
 +
\end{array}</tex>, в которой есть два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</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>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex> и <tex>(D, D)</tex>.
 +
# Рассмотрим цепное правило <tex>A\rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила,<br>добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
 +
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(B, B)</tex>. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex>, <tex>(D, D)</tex>, <tex>(A, B)</tex> и <tex>(B, C)</tex>.
 +
# Повторим второй пункт для правила <tex>B\rightarrow C</tex> и пары <tex>(A, B)</tex>, и получим множество <tex>\lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\rbrace</tex>.
 +
# Для каждой пары добавим в <tex>\Gamma'</tex> новые правила:
 +
#* <tex>A\rightarrow b</tex> для <tex>(A, B)</tex>
 +
#* <tex>A\rightarrow c</tex> и <tex>A\rightarrow DD</tex> для <tex>(A, C)</tex>
 +
#* <tex>B\rightarrow c</tex> и <tex>B\rightarrow DD</tex> для <tex>(B, C)</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>.
+
== См. также  ==
}}
+
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
 +
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
 +
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
  
 
==Литература==
 
==Литература==
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
 +
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Контекстно-свободные грамматики]]

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

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


Постановка задачи

Пусть [math]\Gamma[/math]контекстно-свободная грамматика, содержащая цепные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую цепных правил.
Задача удаления цепных правил из грамматики возникает при попытке её приведения к нормальной форме Хомского.

Алгоритм

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


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

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

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

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

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

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

Корректность алгоритма

Теорема:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. [math]\Gamma'[/math] — грамматика, полученная в результате применения алгоритма к [math]\Gamma[/math]. Тогда [math]L(\Gamma) = L(\Gamma').[/math]
Доказательство:
[math]\triangleright[/math]

[math]\Rightarrow [/math]
Покажем, что [math]L(\Gamma) \subseteq L(\Gamma')[/math].
Пусть [math]w\in L(\Gamma)[/math]. Тогда [math]w[/math] имеет левое порождение [math]S\overset{*}{\underset{lm}{\Rightarrow}} w[/math]. Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и сразу же заменяется. Таким образом, левое порождение в [math]\Gamma[/math] можно разбить на последовательность шагов, в которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что любое нецепное правило, перед которым нет цепных, образует такой шаг. Но по построению [math]\Gamma'[/math] каждый из этих шагов может быть выполнен одним её правилом. Таким образом, [math]S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w[/math], то есть [math]w\in L(\Gamma')[/math].

[math]\Leftarrow [/math]
Покажем, что [math]L(\Gamma') \subseteq L(\Gamma)[/math].

Пусть [math]w\in L(\Gamma')[/math], то есть [math]S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w[/math]. Так как каждое правило [math]\Gamma'[/math] эквивалентно последовательности из нуля или нескольких цепных правил [math]\Gamma[/math], за которой следует нецепное правило из [math]\Gamma[/math], то из [math]\alpha{\underset{\Gamma'}{\Rightarrow}} \beta[/math] следует [math]\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta[/math]. Таким образом, каждый шаг порождения в [math]\Gamma'[/math] может быть заменен одним или несколькими шагами в [math]\Gamma[/math]. Собрав эти последовательности шагов, получим, что [math]S\overset{*}{\underset{\Gamma}{\Rightarrow}} w[/math], то есть [math]w\in L(\Gamma)[/math].
[math]\triangleleft[/math]

Время работы алгоритма

Данный алгоритм работает за [math]O(\left| \Gamma \right| ^ 2)[/math].

Пример

Рассмотрим грамматику: [math] \begin{array}{l l} A\rightarrow B|a\\ B\rightarrow C|b\\ C\rightarrow DD|c \end{array}[/math], в которой есть два цепных правила [math]A\rightarrow B[/math] и [math]B\rightarrow C[/math].

  1. Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из [math](A, A)[/math], [math](B, B)[/math], [math](C, C)[/math] и [math](D, D)[/math].
  2. Рассмотрим цепное правило [math]A\rightarrow B[/math]. Так как существует цепная пара [math](A, A)[/math], второй элемент которой совпадает с левым нетерминалом из правила,
    добавим в множество пару [math](A, B)[/math], у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.
  3. Повторим второй пункт для правила [math]B\rightarrow C[/math] и пары [math](B, B)[/math]. Теперь множество цепных пар будет состоять из [math](A, A)[/math], [math](B, B)[/math], [math](C, C)[/math], [math](D, D)[/math], [math](A, B)[/math] и [math](B, C)[/math].
  4. Повторим второй пункт для правила [math]B\rightarrow C[/math] и пары [math](A, B)[/math], и получим множество [math]\lbrace (A, A), (B, B), (C, C), (D, D), (A, B), (B, C), (A, C)\rbrace[/math].
  5. Для каждой пары добавим в [math]\Gamma'[/math] новые правила:
    • [math]A\rightarrow b[/math] для [math](A, B)[/math]
    • [math]A\rightarrow c[/math] и [math]A\rightarrow DD[/math] для [math](A, C)[/math]
    • [math]B\rightarrow c[/math] и [math]B\rightarrow DD[/math] для [math](B, C)[/math]
    • Оставшиеся цепные пары новых правил не добавят.

См. также

Литература

  • Хопкрофт Д., Мотвани Р., Ульман Д.Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)