Удаление длинных правил из грамматики

Материал из Викиконспекты
Перейти к: навигация, поиск

Задача удаления длинных правил из грамматики возникает при попытке ее приведения к нормальной форме Хомского.


Определение:
Пусть [math]\Gamma[/math]контекстно-свободная грамматика. Правило [math]A \rightarrow \beta [/math] называется длинным если [math]|\beta| \gt 2[/math]


Постановка задачи

Пусть [math]\Gamma[/math]контекстно-свободная грамматика, содержащая длинные правила. Требуется построить эквивалентную грамматику [math]\Gamma'[/math], не содержащую длинных правил

Алгоритм