Изменения

Правило <tex>A \rightarrow \beta </tex> называется '''длинным''' (англ. ''long rule''), если <tex>|\beta| > 2</tex>.

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

Расмотрим длинное правило С каждым длинным правилом <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>, <tex>k > 2</tex>, <tex>a_i \in \Sigma \cup N</tex> <br>проделаем следующее: * Добавим в грамматику <tex>k - 2</tex> новых нетерминалов нетерминала <tex>B_1, B_2, \ldots B_{k-2}</tex> <br>. * Добавим в грамматику <tex>k-1</tex> новое правило: <br>*;<tex>A \rightarrow a_1B_1</tex> <br>*;<tex>B_1 \rightarrow a_2B_2</tex> <br>*;<tex>B_2 \rightarrow a_3B_3</tex> <br>*;<tex>\ldots </tex> <br>*;<tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex> <br>* Удалим из грамматики правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Проделаем описанную операцию с каждым длинным правилом в <tex>\Gamma</tex>.

|statement=Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]]. <tex>\Gamma'</tex> {{---}} грамматика, полученная в результате применения алгоритма к <tex>\Gamma</tex>. Тогда <tex>L(\Gamma) = L(\Gamma').</tex>

Покажем, что <tex>L(\Gamma) \subset subseteq L(\Gamma')</tex> . <br>

<tex>B_2 \rightarrow a_3B_3</tex>, <tex>\ldots </tex>, <tex>B_{k-2} \rightarrow a_{k-1}a_{k}</tex>. Получим вывод <tex>w</tex> в <tex>\Gamma'</tex> <br>.  

Покажем, что <tex>L(\Gamma') \subset subseteq L(\Gamma)</tex> <br>. Допустим, что это не так, и то есть <tex>\exists w \in L(\Gamma'), w \notin L(\Gamma)</tex>. <br> Рассмотрим вывод <tex>w</tex> в <tex>\Gamma' \cup \Gamma</tex>, минимальный по количеству примененных правил, отсутствующих в <tex>\Gamma</tex>. <br>Найдем в этом выводе первое применение некоторого правила <tex>A \rightarrow a_1A_1, a_1 \in \Sigma \cup N</tex>, которого нет в <tex>\Gamma</tex>. В ходе алгоритма это правило оно было получено из некоторого длинного правила <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>. Применим правило <tex>A \rightarrow a_1 a_2 \ldots a_k</tex> вместо <tex>A \rightarrow a_1A_1</tex>, и удалим в выводе все применения правил, полученных из <tex>A \rightarrow a_1 a_2 \ldots a_k</tex>.

Покажем, как описанный алгоритм будет работать на следующей грамматике: : <tex>S \rightarrow AB<br/tex> : <tex>S A \rightarrow ABaBcB</tex> : <tex>B \rightarrow def<br/tex>.  Для правила <tex>A \rightarrow aBcB</tex> вводим <tex> 2 </tex> новых нетерминала <tex>A_1, A_2</tex> и <tex> 3 <br/tex>новых правила: : <tex>A \rightarrow aA_1</tex>: <tex>A_1 \rightarrow BA_2</tex>: <tex>A_2 \rightarrow cB</tex>. Для правила <tex>B \rightarrow def</tex> вводим <tex> 1 </tex> новый нетерминал <tex>B_1</tex> и <tex> 2 </tex> новых правила: : <tex>B \rightarrow dB_1</tex>: <tex>B_1 \rightarrow ef</tex>. В итоге полученная грамматика <tex>\Gamma'</tex> будет иметь вид: : <tex>S \rightarrow AB</tex> : <brtex>A \rightarrow aA_1</tex> : <tex>A_1 \rightarrow BA_2</tex> : <tex>A_2 \rightarrow cB</tex> : <tex>B \rightarrow dB_1</tex> : <tex>B_1 \rightarrow ef</tex>.

Для правила <tex>A \rightarrow aBcB</tex> вводим 2 новых нетерминала <tex>A_1== См. также ==* [[Контекстно-свободные_грамматики,_вывод, A_2</tex>_лево-_и_правосторонний_вывод, и 3 новых правила: <br><tex>A \rightarrow aA_1</tex> <br><tex>A_1 \rightarrow BA_2</tex> <br>_дерево_разбора|Контекстно-свободные грамматики]]<tex>A_2 \rightarrow bB</tex> <br>* [[Нормальная форма Хомского]]

Для правила <tex>B \rightarrow def</tex> вводим 1 новый нетерминал <tex>B_1</tex>== Источники информации ==* ''Michael Sipser'' Introduction to the Theory of Computation. — PWS Publishing, и 2 новых правила: <br>1997. — ISBN 0-534-94728-X. (с 107.)<tex>B \rightarrow dB_1</tex> <br>* ''Michael A. Harrison'' Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 103.)<tex>B_1 \rightarrow ef</tex> <br>* [[wikipedia:en:Chomsky_normal_form#Converting a grammar to Chomsky Normal Form | Wikipedia {{---}} Chomsky normal form]]

В итоге, полученная грамматика <tex>\Gamma'</tex> будет иметь вид[[Категория: <br>Теория формальных языков]]<tex>S \rightarrow AB</tex> <br>[[Категория: Контекстно-свободные грамматики]] <tex>A \rightarrow aA_1</tex> <br><tex>A_1 \rightarrow BA_2</tex> <br><tex>A_2 \rightarrow bB</tex> <br><tex>B \rightarrow dB_1</tex> <br><tex>B_1 \rightarrow ef</tex> <br>[[Категория: Нормальные формы КС-грамматик]]