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

Лемма 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 над алфавитом узнать, является ли бесконечным множество .