Изменения

|definition = Правила '''Цепное правило''' (''unit rule'') — правило вида <tex>A \to rightarrow B</tex> (, где <tex>A,</tex> и <tex>B</tex> - — нетерминалы) называются цепными.

Зачастую удобно рассматривать == Постановка задачи ==Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики без , вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], содержащая цепные правила. Требуется построить эквивалентную грамматику <tex>\Gamma'</tex>, не содержащую цепных правил. Оказывается, что верно следующее утверждение:<br>Задача удаления цепных правил из грамматики возникает при попытке её приведения к [[нормальная форма Хомского|нормальной форме Хомского]].

==Алгоритм=={{УтверждениеОпределение|statementdefinition='''Цепная пара''' (''unit pair'') — упорядоченная пара <tex>(A,B)</tex>, в которой <tex>A\Rightarrow ^* B</tex>, используя только цепные правила.}} Алгоритм удаления цепных правил из грамматики:#Найти все цепные пары в грамматике <tex>\Gamma</tex>.#Для любой контекстнокаждой цепной пары <tex>(A,B)</tex> добавить в грамматику <tex>\Gamma'</tex> все правила вида <tex>A\rightarrow\alpha</tex>, где <tex>B\rightarrow\alpha</tex> {{---свободной }} нецепное правило из <tex>\Gamma</tex>.#Удалить все цепные правила Найти все цепные пары можно по индукции: '''Базис.''' <tex>(КA,A)</tex> {{-С--}} цепная пара для любого нетерминала, так как <tex>A\Rightarrow ^* A</tex> за ноль шагов. '''Индукция.''' Если пара <tex>(A,B) </tex> {{---}} цепная, и есть правило <tex>B\rightarrow C</tex>, то <tex>(A,C)</tex> {{---}} цепная пара. Нетрудно понять, что такой алгоритм найдет все цепные правила грамматики <tex>\Gamma</tex>, и только их. ===Корректность алгоритма==={{Теорема|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики существует эквивалентная ей К, вывод, лево-С и правосторонний вывод, дерево разбора|контекстно-свободная грамматика без цепных правил]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>

Построим граф<tex>\Rightarrow </tex> <br>Покажем, что <tex>L(\Gamma) \subseteq L(\Gamma')</tex>. <br>Пусть <tex>w\in L(\Gamma)</tex>. Вершинами в нем будут нетерминальные символы, а ребро из Тогда <tex>Aw</tex> в имеет левое порождение <tex>BS\overset{*}{\underset{lm}{\Rightarrow}} w</tex> будет тогда . Где бы в левом порождении ни использовалось цепное правило, нетерминал в правой части становится крайним слева в выводимой цепочке и только тогдасразу же заменяется. Таким образом, когда есть правило левое порождение в <tex>A \to BGamma</tex>. Сделаем транзитивное замыкание для этого графа и добавим правиламожно разбить на последовательность шагов, соответствующие новым ребрамв которых ноль или несколько цепных правил сопровождаются нецепным. Заметим, что теперь любое выводимое слово можно вывестинецепное правило, перед которым нет цепных, используя не более одного образует такой шаг. Но по построению <tex>\Gamma'</tex> каждый из этих шагов может быть выполнен одним её правилом. Таким образом, <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>, то есть <tex>w\in L(\Gamma'цепного правила''' подряд. Также нетрудно понять, что новая грамматика эквивалентна старой)</tex>.

Далее<tex>\Leftarrow </tex> <br>Покажем, рассмотрим все цепные правила что <tex>A L(\to BGamma') \subseteq L(\Gamma)</tex>. <br>Пусть <tex>w\in L(\Gamma')</tex>, то есть <tex>S\overset{*}{\underset{\Gamma'}{\Rightarrow}} w</tex>. Так как каждое правило <tex>\Gamma'</tex> эквивалентно последовательности из нуля или нескольких цепных правил <tex>B\Gamma</tex> можно вывести: , за которой следует нецепное правило из <tex>B \to Gamma</tex>, то из <tex>\alpha{\underset{\Gamma'}{\Rightarrow}} \beta</tex> следует <tex>\alpha\overset{*}{\underset{\Gamma}{\Rightarrow}} \beta</tex>. Таким образом, каждый шаг порождения в <tex>\alpha_1 Gamma'</tex> может быть заменен одним или несколькими шагами в <tex>\mid Gamma</tex>. Собрав эти последовательности шагов, получим, что <tex>S\alpha_2 overset{*}{\mid underset{\dots Gamma}{\Rightarrow}} w</tex>, то есть <tex>w\mid in L(\alpha_nGamma)</tex>.

Тогда добавим следующее правило в нашу }} === Время работы алгоритма ===Данный алгоритм работает за <tex>O(\left| \Gamma \right| ^ 2)</tex>. === Пример ===Рассмотрим грамматику: <tex>\begin{array}{l l} A \to rightarrow B|a\\ B\alpha_1 rightarrow C|b\mid \alpha_2 C\mid rightarrow DD|c\dots end{array}</tex>, в которой есть два цепных правила <tex>A\rightarrow B</tex> и <tex>B\rightarrow C</tex>. # Для каждого нетерминала создадим цепную пару. Теперь множество цепных пар будет состоять из <tex>(A, A)</tex>, <tex>(B, B)</tex>, <tex>(C, C)</tex> и <tex>(D, D)</tex>.# Рассмотрим цепное правило <tex>A\mid rightarrow B</tex>. Так как существует цепная пара <tex>(A, A)</tex>, второй элемент которой совпадает с левым нетерминалом из правила,<br>добавим в множество пару <tex>(A, B)</tex>, у которой первый элемент такой же как у найденной, а второй равен правому нетерминалу из текущего правила.# Повторим второй пункт для правила <tex>B\alpha_nrightarrow 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>#* Оставшиеся цепные пары новых правил не добавят.

Заметим== См. также ==* [[Контекстно-свободные_грамматики,_вывод, что теперь любое слово можно вывести_лево-_и_правосторонний_вывод, не используя цепных правил вовсе_дерево_разбора|Контекстно-свободные грамматики]]* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]* [http://en. Поэтому удалим ихwikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]

Итого==Литература==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, была построена Кязыков и вычислений''', 2-С грамматика без цепных правиле изд. : Пер. с англ. — Москва, эквивалентная исходнойИздательский дом «Вильямс», 2002.— 528 с. : ISBN 5-8459-0261-4 (рус.) [[Категория: Теория формальных языков]]}}[[Категория: Контекстно-свободные грамматики]]