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



             

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


Теорема 15.5.1.

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

Пример 15.5.2.

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

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

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

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

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




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