Математическая теория формальных языков
Проблема пустоты языка
Теорема 15.4.1.
Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G узнать, верно ли, что .
Доказательство. Удалим из G все бесполезные символы, кроме начального символа (как в доказательстве теоремы 8.1.3). Если полученная грамматика содержит хотя бы одно правило, то .
Упражнение 15.4.2.
Является ли непустым язык, порождаемый грамматикой
