Проблемы контекстной свободности

Определение 16.5.1. Пусть , , , где и для всех i. Обозначим через язык .

Лемма 16.5.2. Язык является контекстно-свободным при любых и .

Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.

Лемма 16.5.3. Рассмотрим алфавит . Пусть и , где , и для всех i. Тогда язык является контекстно-свободным в том и только том случае, когда постовская система соответствия не имеет решений.

Доказательство. Пусть - решение постовской системы соответствия , где для всех i. Положим

Легко проверить, что , и язык L₀ является автоматным. Очевидно, что

Можно доказать (например, используя лемму 9.1.1), что язык не является контекстно-свободным. Согласно теореме 9.6.1 язык также не~является контекстно-свободным.

Обратно, если постовская система соответствия не имеет решений, то .

Теорема 16.5.4. Пусть . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G₁ и G₂ над алфавитом узнать, является ли контекстно-свободным язык .

Доказательство. Достаточно построить по постовской системе соответствия , где , и для всех i выполняется , и , контекстно-свободную грамматику G₁, порождающую язык , и контекстно-свободную грамматику G₂, порождающую язык . С учетом леммы 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 порождается грамматикой