Математическая теория формальных языков
Дополнение контекстно-свободного языка
Лемма 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.
Пусть . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G1 и G2
над алфавитом
узнать, верно ли, что L(G1) = L(G2).
Доказательство Утверждение следует из предыдущей теоремы и примера 1.5.16.
Теорема 16.3.9.
Пусть . Тогда не существует алгоритма, позволяющего по произвольным контекстно-свободным грамматикам G1 и G2
над алфавитом
узнать, верно ли, что .
Доказательство Очевидно, что
тогда и только тогда, когда .
Лемма 16.3.10.
Дополнение языка
является бесконечным тогда и только тогда, когда постовская система соответствия
имеет решение.
Теорема 16.3.11.
Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстно-свободной грамматике G над алфавитом
узнать, является ли бесконечным множество .
Упражнение 16.3.12.
Рассмотрим язык, порождаемый грамматикой
Содержит ли этот язык все слова из {a,b}*?
Упражнение 16.3.13.
Рассмотрим язык, порождаемый грамматикой
{a,b}*?
