Математическая теория формальных языков
Проблема бесконечности языка
Теорема 15.5.1.
Существует алгоритм, позволяющий по произвольной контекстно-свободной грамматике G узнать, является ли бесконечным язык L(G).
Пример 15.5.2.
Рассмотрим контекстно-свободную грамматику G из примера 8.1.4. Чтобы выяснить, является ли язык L(G) бесконечным, удалим сначала все бесполезные символы. Затем устраним все -правила. Так как
и , то можно всюду заменить W на Z. Получится грамматика
эквивалентная исходной грамматике G. Очевидно, что эта грамматика не содержит "рекурсивных" нетерминальных символов. Следовательно, язык L(G) является конечным.
Упражнение 15.5.3.
Является ли бесконечным язык, порождаемый грамматикой
