Дополнение контекстно-свободного языка

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

Пример 16.3.2. Пусть . Тогда язык над алфавитом порождается контекстно-свободной грамматикой

Заметим, что для каждого i.

Язык является даже линейным (чтобы получить линейную грамматику, достаточно "раскрыть" вспомогательные символы A, B и Z).

Замечание 16.3.3. Лемму 16.3.1 можно доказать, явно построив контекстно-свободную грамматику (как в примере 16.3.2), а можно и вывести из теоремы 12.2.7}, проверив, что - детерминированный контекстно-свободный язык.

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

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

Доказательство. .

Лемма 16.3.6. Дополнение языка является непустым тогда и только тогда, когда постовская система соответствия имеет решение.

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

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

Доказательство Очевидно, что тогда и только тогда, когда дополнение языка L(G) является пустым.

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

Доказательство Утверждение следует из предыдущей теоремы и примера 1.5.16.

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

Доказательство Очевидно, что тогда и только тогда, когда .

Лемма 16.3.10. Дополнение языка является бесконечным тогда и только тогда, когда постовская система соответствия имеет решение.

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

Упражнение 16.3.12. Рассмотрим язык, порождаемый грамматикой

Содержит ли этот язык все слова из {a,b}^*?

Упражнение 16.3.13. Рассмотрим язык, порождаемый грамматикой

{a,b}^*?

Проблема автоматности

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

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

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

Как было установлено в упражнении 3.4.2, язык не является автоматным. Согласно теореме 3.2.1 язык не является автоматным. Следовательно, и язык не является автоматным.

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

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

Доказательство Докажем утверждение теоремы для случая . Из леммы 16.4.1 следует, что если бы проблема распознавания автоматности языка L(G) для контекстно-свободных грамматик над алфавитом была разрешима, то также была бы разрешима проблема соответствий Поста для постовских систем соответствия , где , и для всех i. Но тогда была бы разрешима проблема соответствий Поста для всех постовских систем соответствия над алфавитом {a,b} (если для некоторого i, то рассматриваемая постовская система соответствия имеет решение, а именно (i)).

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

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

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

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