Изменения
Нет описания правки
{{Определение
|definition=Грамматикой в '''нормальной форме Хомского''' (''Chomsky normal form'') называется [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная грамматика]], в которой могут содержатся правила только следующего вида:
== Пример ==
Рассмотрим грамматику для языка правильных скобочных последовательностей: <tex>S\rightarrow \varepsilon|``("S``)"|SS</tex>.
# Удалим длинные правила и получим грамматику <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A``)"|SS\\ A\rightarrow ``("S
\end{array}
</tex>.
\begin{array}{l l}
S\rightarrow \varepsilon|S'\\
S'\rightarrow A``)"|S'S'\\ A\rightarrow ``("S'|``("
\end{array}
</tex>.
# Удалим цепные правила - <tex>
\begin{array}{l l}
S\rightarrow \varepsilon|A``)"|S'S'\\ S'\rightarrow A``)"|S'S'\\ A\rightarrow ``("S'|``("
\end{array}
</tex>.
S\rightarrow \varepsilon|AB|S'S'\\
S'\rightarrow AB|S'S'\\
A\rightarrow CS'|``("\\ C\rightarrow ``("\\ B\rightarrow ``)"
\end{array}
</tex>.
== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [http://en.wikipedia.org/wiki/Chomsky_normal_form Chomsky normal form]
==Литература==
