Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
V\\ б) R получается из объединения схем Ti и Гг добавлением правил /->/i/2, ab-+ba, ba-+a, где а и b пробегают V\ и V2 соответственно. Ясно, что при У1П1/2 = 0Г есть нужная грамматика. В противном случае следует предварительно преобразовать Г2 так же, как было сделано с Г(.
Положим теперь для произвольного языка L и произвольного п= 1,2,... -
Lin) = {х\ х <= L & I Lin) = {x\x(=L&\x\^n}
и докажем следующую лемму.
Лемма 8.4. Пусть L0, Lu L2 — НС-языки и Я” — класс языков, содержащий L0\)LX и не содержащий ни одного из языков Lo U Мп) (J L2ra). Тогда свойство принадлежать классу 9? нераспознаваемо в классе НС-грамматик.
Доказательство. Пусть А0, Лг, Л2 — НС-грам-матики, порождающие L0, L\, Z,2 соответственно.
{x\x^L(T1)&3y(y^L(T2)&\y\ = \x\)}.
264 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ.
Фиксировав символы а и Ь, рассмотрим произвольну ДЭ-машину М с входным алфавитом {а} и построим дл нее НС-грамматики Г^1 и Г\м по лемме 8.2. Затем, прит менив к грамматикам Ai и лемму 8.3, построим НС-грамматику Г', порождающую множество тех цепо чек из L], для которых в L (г?1) имеются цепочки рав* ной.длины, и аналогичную НС-грамматику Г" построй для Д2 и Гг1. Если вычисляемая машиной М функция определена для значения аргумента, равного а, т языки L (Г') и L (Г") будут, очевидно, совпадать соот ветственно с L("o) и Ь(2°\ где щ — число из леммы 8. в противном случае будет L(T') = LU L (Г") — 0. На. конец, построим НС-грамматику Г, порождающую язы L (Г0) U L (Г') U L (Г") (теорема 3.4). Язык L (Г) будет со' впадать с Lo U ь\По) U L^, если f определена для а, с Z-o (J Z-j в противном случае. Но L0\jLl^3 L0 (J Li”0' U Z,2no) ф 3!\ таким образом, неразрешимая п теореме 8.2 проблема распознавания свойства ДЭ-ма шины М с входным алфавитом {а} вычислять функ цию *), определенную для значения аргумента а, сво дится к проблеме распознавания свойства НС-грам. матики порождать язык, принадлежащий классу 3!
Замечание. Из доказательства леммы 8.4 ясно; что она остается справедливой и в несколько усиленно формулировке; именно, для произвольного словаря свойство принадлежать классу 3 нераспознаваем в классе НСу. То же верно и для последующих рассмот рений этого параграфа (исключая одну специальну1 проблему, особо оговариваемую ниже, стр. 267).
Теперь мы можем перейти к основной теореме этог параграфа.
Скажем, что языки L] и п о ч т и совпадают если они отличаются друг от друга лишь конечным чис лом элементов, т. е. их симметрическая разност (L[ — L2) U (L2 — Li) конечна. Отношение почти совпаде ния является, очевидно, эквивалентностью; классы инду, цируемого этой эквивалентностью разбиения мы будем на
*) Собственно говоря, речь должна идти о проекции этой фун ции на некоторый алфавит (который можно выбрать произвольно) но проектирование не изменяет области определения функции.
ИНВАРИАНТНЫЕ СВОЙСТВА НС-ГРАММАТИК
265
зывать пучками. Ясно, что всякий пучок, содержащий хотя бы один НС-язык, целиком состоит из НС-языков.
Теорема 8.3. Если 3? — класс языков, содержащий хотя бы один НС-язык и имеющий хотя бы с одним пучком НС-языков конечное (в частном случае пустое) пересечение, то свойство принадлежать классу 3? нераспознаваемо в классе НС-грамматик.
Доказательство. Пусть сначала пересечение Я? с пучком конечных языков бесконечно. Тогда существует пучок П, состоящий из бесконечных языков и пересекающийся с 3? по конечному множеству. Обозначим через L0 произвольный конечный язык, принадлежащий 31, через L, — пустой язык и через L — произвольный язык из П. При любом ш = 1,2, ...язык L0U L(m) также принадлежит П, и, следовательно, найдется такое р, что ни при каком п язык L0 U L(n) не_принадлежит 3?. Положив [}р) = Ь2, будем иметь L2n) = L('n), если п^р, и L2n) = Lip), если п < р; поэтому при любом п — \, 2,... получаем L0 U йп) (J Z|>n) = L0(J Йтах(п' р)) ф 3. В то же время L0[}L{ = Lq^3?. Остается применить лемму 8.4.
Пусть теперь 3? пересекается с пучком конечных языков по конечному множеству. Если при этом 3? не содержит бесконечных НС-языков, воспользуемся леммой 8.4, взяв в качестве L0 произвольный конечный язык, принадлежащий S', в качестве L] — пустой язык и в качестве Ь2— произвольный бесконечный НС-язык. В противном случае, — если существует бесконечный НС-язык L, принадлежащий 3?, — применяем ту же лемму при L0 = Bp\ Li — L, L2 = 0, где р — такое натуральное число, что ни один из языков ?<п>, где р, в
3 не входит.
Доказанная теорема позволяет легко убедиться в не-распознаваемости ряда более конкретных типов свойств. Имеют место, в частности, такие факты:
Следствие 1. В следующих случаях свойство, нетривиальное в классе НС-языков, нераспознаваемо в классе НС-грамматик:
а) если им обладает лишь конечное число НС-языков]
б) если им обладают все конечные языки, соответственно все языки с конечными дополнениями, кроме, быть может, конечного их числа;
266 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8’
в) если им обладают только Ъ-языки и, быть может, конечное число НС-языков, не являющихся Ъ-языками.
Пункт а) вытекает из того, что число пучков НС-' языков бесконечно, пункт б) —из того, что конечные языки, равно как и языки с конечными дополнениями, образуют пучок (и из нераспознаваемости отрицания нераспознаваемого свойства), пункт в) — из того, что всякий пучок, содержащий Б-язык, целиком состоит из Б-языков (в силу теорем 4.8 и 5.5).
