Математическая теория формальных языков

       

Нормальные формы контекстно-свободных грамматик


Основная цель этой лекции - доказать, что каждая контекстно-свободная грамматика эквивалентна некоторой контекстно-свободной грамматике специального вида, а именно грамматике в нормальной форме Хомского (раздел 8.3). Этот факт используется дальше в доказательствах многих теорем о контекстно-свободных языках. Два вспомогательных результата, на которые опирается приведение грамматик к нормальной форме Хомского, выделены в отдельные разделы в начале лекции.

В конце лекции доказывается, что каждую контекстно-свободную грамматику можно также привести к нормальной форме Грейбах.



Содержание раздела