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