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

       

Проблема бесконечности языка


Теорема 15.5.1.

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

Пример 15.5.2.

Рассмотрим контекстно-свободную грамматику G из примера 8.1.4. Чтобы выяснить, является ли язык L(G) бесконечным, удалим сначала все бесполезные символы. Затем устраним все -правила. Так как

и , то можно всюду заменить W на Z. Получится грамматика

эквивалентная исходной грамматике G. Очевидно, что эта грамматика не содержит "рекурсивных" нетерминальных символов. Следовательно, язык L(G) является конечным.

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

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



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