Изменения

Перейти к: навигация, поиск

Нормальная форма Хомского

2 байта добавлено, 07:54, 26 октября 2011
Преобразование грамматики в нормальную форму Хомского
После пятого шага грамматика <tex> \Gamma_5 </tex> содержит только правила вида <tex> A \rightarrow B C </tex> и <tex> A \rightarrow a </tex>, где <tex> A, B, C </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал. Возможно, что также присутствует правило <tex> S_0 \rightarrow \varepsilon </tex>. Новая грамматика допускает тот же язык, что и <tex> \Gamma </tex>.
 
 
Заметим, что любую контекстно-свободную грамматику можно привести к нормальной форме Хомского. Такая форма грамматики очень удобна для работы многих алгоритмов над грамматиками, например, [[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ|алгоритм Кока-Янгера-Касами]].
271
правка

Навигация