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



         

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


Теорема 15.4.1.

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

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

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

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




Содержание  Назад  Вперед