2020-05-25
119
Определение 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 порождается грамматикой
