Математическая теория формальных языков
Проблемы контекстной свободности
Определение 16.5.1.
Пусть , , , где
и
для всех i. Обозначим через
язык .
Лемма 16.5.2.
Язык
является контекстно-свободным при любых и .
Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.
Лемма 16.5.3. Рассмотрим алфавит . Пусть
и , где ,
и
для всех i. Тогда язык
является контекстно-свободным в том и только том случае, когда постовская система соответствия
не имеет решений.
Доказательство. Пусть - решение постовской системы соответствия , где
для всех i. Положим
Легко проверить, что ,
и язык L0
является автоматным. Очевидно, что
Можно доказать (например, используя лемму 9.1.1), что язык
не является контекстно-свободным. Согласно теореме 9.6.1 язык
также не~является контекстно-свободным.
Обратно, если постовская система соответствия
не имеет решений, то .
Теорема 16.5.4.
Пусть . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G1 и G2
над алфавитом
узнать, является ли контекстно-свободным язык .
Доказательство. Достаточно построить по постовской системе соответствия , где ,
и для всех i выполняется ,
и , контекстно-свободную грамматику G1, порождающую язык , и контекстно-свободную грамматику G2, порождающую язык . С учетом леммы 16.5.3 неразрешимость рассматриваемой задачи сводится к неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.5.
Рассмотрим алфавит . Язык
является контекстно-свободным при любых и .
Доказательство. Положим . Язык
можно представить в виде объединения пяти контекстно-свободных языков
Теорема 16.5.6.
Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстно-свободной грамматике G над алфавитом
узнать, является ли контекстно-свободным язык .
Доказательство. Рассмотрим алфавит . Достаточно построить по постовской системе соответствия , где ,
и для всех i выполняется ,
и , контекстно-свободную грамматику G, порождающую язык . С учетом леммы 16.5.5 неразрешимость рассматриваемой задачи сводится к~неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.
Лемма 16.5.7.
Рассмотрим алфавит . Язык
является контекстным при любых и .
Теорема 16.5.8.
Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстной грамматике G над алфавитом
узнать, является ли контекстно-свободным язык L(G).
Доказательство. Достаточно построить по постовской системе соответствия , где ,
и для всех i выполняется ,
и , контекстную грамматику G, порождающую язык .
Упражнение 16.5.9.
Является ли контекстно-свободным язык , где язык L порождается грамматикой
