Математическая теория формальных языков

       

Проблема пустоты языка


Теорема 15.4.1.

Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G узнать, верно ли, что .

Доказательство. Удалим из G все бесполезные символы, кроме начального символа (как в доказательстве теоремы 8.1.3). Если полученная грамматика содержит хотя бы одно правило, то .

Упражнение 15.4.2.

Является ли непустым язык, порождаемый грамматикой



Содержание раздела