Математическая теория формальных языков
Устранение бесполезных символов
Определение 8.1.1.
Пусть дана порождающая грамматика . Символ
называется полезным (useful), если существуют такие слова ,
и , что
и . Символ
называется бесполезным (useless), если он не является полезным. Символ
называется порождающим (generating), если существует такое слово , что . Символ
называется достижимым если существуют такие слова
и , что .
Лемма 8.1.2.
Пусть дана контекстно-свободная грамматика , в которой все символы из N являются порождающими. Пусть N' - множество всех достижимых символов грамматики G, а P' - множество тех правил из P, которые не содержат ни одного символа из множества . Тогда в контекстно-свободной грамматике
все символы из N' являются порождающими. \end{lemma}
Теорема 8.1.3.
Пусть дана контекстно-свободная грамматика
и . Тогда существуют такие множества
и , что в контекстно-свободной грамматике
нет бесполезных символов и она эквивалентна исходной грамматике.
Доказательство. На первом этапе удалим все непорождающие символы (удалим также каждое правило, содержащее хотя бы один такой символ). На втором этапе из полученной грамматики удалим все недостижимые символы (и правила, их содержащие). Согласно 8.1.2 на втором этапе ни один порождающий символ не может стать непорождающим.
Пример 8.1.4.
Рассмотрим контекстно-свободную грамматику G с правилами
Удалив четыре правила, содержащие непорождающий символ U, получим грамматику G1. В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G2
с правилами
Очевидно, что L(G) = L(G2) и грамматика G2
не содержит бесполезных символов.
Упражнение 8.1.5. Найти контекстно-свободную грамматику без бесполезных символов, эквивалентную грамматике
