308
правок
Изменения
Нет описания правки
|definition =
Пусть <tex>\Gamma</tex> {{---}} [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]].
Правило <tex>A \rightarrow \beta </tex> называется '''длинным'''(англ. ''long''), если <tex>|\beta| > 2</tex>.
}}
Пусть <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> проделаем следующее:
=== Корректность алгоритма ===
{{Теорема
* ''Michael Sipser'' Introduction to the Theory of Computation. — PWS Publishing, 1997. — ISBN 0-534-94728-X. (с 107.)
* ''Michael A. Harrison'' Introduction to Formal Language Theory. — Addison-Wesley, 1978. — ISBN 978-0201029550. (с 103.)
* [[wikipedia:en:Chomsky_normal_form#Converting a grammar to Chomsky Normal Form | Wikipedia {{---}} Chomsky normal form]]
[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
