Проблема пустоты
Теорема: Проблема непустоты разрешима для КС-грамматики, т.е. если G - является КС-грамматикой, то существует алгоритм, позволяющий определить, справедливо ли утверждение L(G)= Æ.
Доказательство:
1. Определим, имеет ли грамматика правило вывода, вида S®e. Если да, то eÎL(G) и L(G)¹Æ.
2. Предположим, что в G нет правила S®e. Тогда построим все деревья вывода в грамматике, глубина которых n£|N|, где N - мощность множества нетерминалов. Число таких деревьев конечно. Если хотя бы одно из деревьев вывода является деревом вывода терминальной цепочки, то L(G) ¹Æ.
Вопросы и упражнения
Пусть задана грамматика G=(T, N, S, P):
S®AaB
A®baB
B®e
Является L(G) пустым, или нет?
Нерелевантные правила
Правило КС-грамматики релевантно, если существует вывод некоторой цепочки gÎL(G), в котором используется это правило. Нерелевантное правило можно исключить из грамматики и это не повлияет на язык L(G).
Как найти нерелевантные правила? Пусть есть КС-грамматика G= (T, N, S, P) и AÎN. Рассмотрим грамматику GA= (T, N, A, P). Если язык L(GA)= Æ, то невозможно вывести ни одну цепочку с помощью правил P.
Если удалить из множества правил P все, содержащие нетерминал A в левой и правой частях, то язык L(G) не изменится.
Предположим, что КС-грамматика имеет только релевантные правила. Если в грамматике G отсутствует правило вида A®e, то такая грамматика называет e-свободной КС-грамматикой.
Теорема: Пусть G= (T, N, S, P) - произвольная КС-грамматика, имеющая e-правила, тогда можно построить грамматику G’= (T, N, S, P’) с новыми правилами P’, такую что L(G’)= L(G)\{e}.
Алгоритм построения грамматики
1. Объединить в P’ все e-свободные правила.
2. Рассмотреть все нетерминалы AÎN такие,, что из них вывода пустая цепочка (так называемые e-порождающие нетерминалы). Каждому правилу pÎP’, содержащему в правой части e-порождающий нетерминал, поставим в соответствие такое правило, что в его правой части опущены (по сравнению с p) один или более e-порождающих нетерминалов. Эти правила присоединяем к P.
Вопросы и упражнения
Пусть задана грамматика G=(T, N, S, P):
S®AaB
A®baB
B®e
A®ba
Какое из правил данной грамматики нерелевантно?
Постройте эквивалентную ей e-свободную грамматику.