1632
правки
Изменения
м
rollbackEdits.php mass rollback
{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (англ. ''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержаться правила только следующего вида:
:<tex>A \rightarrow B C </tex>,
:<tex>A \rightarrow a </tex>,
:<tex>S \rightarrow \varepsilon </tex>,
где <tex> a </tex> {{---}} терминал, <tex> A, B, C </tex> {{---}} нетерминалы, <tex> S </tex> {{---}} стартовая вершина, <tex> \varepsilon </tex> {{---}} пустая строка, стартовая вершина не содержится в правых частях правил.
Таким образом, мы получили грамматику в нормальной форме Хомского, которая допускает тот же язык, что и <tex> \Gamma </tex>.
Стоит заметить, что порядок выполнения операций важен. Первое правило должно быть выполнено перед вторым, иначе время нормализации ухудшится до <tex>O(2^{\left| \Gamma \right|})</tex>. Третье правило идет после второго, потому что после удаления <tex>\varepsilon</tex>-правил, могут образоваться новые цепные правила. Также четвертое правило должно быть выполнено позже третьегои второго, так как оно может они могут порождать бесполезные символы.
При таком порядке действий размеры грамматики возрастают полиномиально.
|-
|''5. Уберём ситуации, когда в правиле встречаются несколько терминалов.''
|<tex>S\rightarrow S_{23}S_{1}</tex><br> <tex>X\rightarrow S_{23}Y|X_{1}Y</tex><br> <tex>Y\rightarrow S_{23}Y|X_{1}Y|Y_{1}Y_{1}</tex> <br> <tex>S_{1}\rightarrow XS_{2}|S_{34}X|y</tex> <br> <tex>S_{2}\rightarrow S_{34}X|y</tex> <br> <tex>S_{23}\rightarrow a</tex> <br> <tex>S_{34}\rightarrow y</tex> <br> <tex>X_{1}\rightarrow b</tex> <br> <tex>Y_{1}\rightarrow c</tex>
|}
<div style="clear:both;"></div>
==Источники информации==
* [[wikipedia:en:Chomsky normal form | Wikipedia {{---}} Chomsky normal form]]
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 280с528с. : ISBN 5-8459-0261-4 (рус.)
