Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
§ 8.3. Инвариантные свойства НС-грамматик
В предыдущем параграфе мы показали, что в классе произвольных грамматик все нетривиальные свойства языков нераспознаваемы. Уже в классе НС-грамматик дело обстоит иначе. Действительно, для произвольной
ИНВАРИАНТНЫЕ СВОЙСТВА НС-ГРАММАТИК
261
цепочки х свойство языка содержать х, как уже отмечалось, распознаваемо в этом классе*). Поэтому в нем распознаваемы и такие свойства, как «содержать хотя бы одну из двух данных цепочек», «содержать одну данную цепочку и не содержать другую» и т. п. Вообще, если Ф(Ь,Х\, ..., хь) — произвольное булево выражение от предикатов «х\ е L», ..., «хи е L» (т. е. выражение, составленное из этих предикатов с помощью пропозициональных связок И, &, V, =э) и Ф0(хь хк) — свойство языка L удовлетворять условию <b(L, х\, ... ..., хь), то Фо(хь ..., хи) распознаваемо в классе НС. Такие свойства мы назовем булевыми.
Однако для некоторого весьма общего типа инвариантных свойств все же удается доказать их нерас-познаваемость в классе НС; это и будет основной целью настоящего параграфа.
Предварительно докажем несколько лемм.
Лемма 8.2. Для всякой ЛЭ-машины М, входной алфавит которой содержит символ а, можно построить такие YiC-грамматики Г?* и с одним и тем же одноэлементным основным словарем Щ, что:
а) если вычисляемая машиной М функция определена для значения аргумента, равного а, то L (rf1) =
— {bn\n^n0}, 1(Гг1)= {bn\ 1 ^п^па), где п0 —целое положительное число, зависящее от М;
б) в противном случае L{rf)=0, ь{^2) = Ь+.
Доказательство. Построим сначала по машине М ее детерминированную п. о. м. М\ (лемма 1.5). Затем построим по М\ другую ДЭ-машину М2 так, чтобы она также представляла собой п. о. м. для М и в то же время обладала тем свойством, что в случае, когда вычисляемая машиной М функция не определена, М2 работала бы вечно и при этом ее рабочая лента при достаточно долгой работе оказывалась бы сколь угодно длинной. [Это можно сделать, например, перестроив Mi так, чтобы она: а) перед каждым своим шагом добавляла к рабочей ленте справа ячейку, которая уничтожалась
*) Как и в более широком классе неукорачивающих грамматик. В отношении распознаваемости инвариантных свойств эти два класса вообще ведут себя одинаково (см. сноску на стр. 254).
262 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
бы лишь после перехода машины в «заключительное Mi-состояние»; б) в случае «безрезультатной остановки» начинала добавлять к рабочей ленте ячейку за ячейкой без конца.] Кроме того, мы будем считать, что левые части инструкций М2 не содержат заключительных состояний; это, очевидно, не уменьшает общности. В силу теоремы 3.1 достаточно построить неукорачивающие грамматики и Гг со свойствами а) и б); мы определим их следующим образом.
1) Основной и вспомогательный словари V и W и начальный символ I — общие для обеих грамматик, а именно: V = {b}, W = Z (J Q U {#, /, Q, где Z, Q — соответственно рабочий алфавит и множество состояний М2 и #. /, Со ф. Z U Q U {Ь}.
2) Схемы обеих грамматик содержат правило / qiad, где q\ — начальное состояние М2 и d — «разделительный символ» (см. определение п. о. м., стр. 45), всевозможные правила вида С0а->аС0, где aeli^, и правила, сопоставляемые инструкциям М2 следующим образом: каждой инструкции Aqa^-q^ типа (ii) сопоставляется правило Лда-»-<7рС0, каждой инструкции qa-+Aqp типа (iii) — правило qa-+Aq^, каждой инструкции ga-»-<7pJI типа (iv) — всевозможные правила вида Bqa-^-q^B, где BgZ, и каждой инструкции qa^>-q&Yl типа (v) — всевозможные правила вида qaB->Bq^, где BeZ. 3) Сверх того, схема Г! содержит всевозможные правила вида qf-^-b, где ^ — заключительное состояние Мь вида ЬВ —>bb, где Self, вида Bb-^-bb, где
и правило b-*bb, а схема Гг* — правила / —> b, I —> bb, I-^-bbb и всевозможные правила вида В-^b, где В еZ (J QU{#}•
Ясно, что если вычисляемая машиной М функция определена на а, то ситуаций машины М% достижимых из ситуации S0 = (qu А, ф ф, Л, #ad), имеется лишь конечное число, причем длины отвечающих этим ситуациям рабочих лент пробегают все натуральные числа от 2 до некоторого щ включительно; поэтому в Г? будут в этом случае выводимы из I всевозможные цепочки вида Ьк, где k ^ ti\ + 2, и только такие степени Ь, а в. Г^ — всевозможные цепочки вида Ь1, где
ИНВАРИАНТНЫЕ СВОЙСТВА НЙ-ГРАММАТИК
263
1 ^ ^ «1 + 2, и только такие степени Ь. В противном случае достижимых из So ситуаций будет бесконечно много, длины отвечающих им рабочих лент будут пробегать все натуральные числа, не меньшие 2, но ни одна из этих ситуаций не будет содержать заключительных состояний; поэтому в ff1 не будет выводима из / ни одна степень Ь, а в Гг , напротив, все степени b будут выводимы из /•
Лемма 8.3. Для любых двух НС-грамматик Г] и Гг можно построить НС-грамматику, порождающую язык
Доказательство. В силу теоремы 3.3 достаточно построить почти неукорачивающую грамматику, порождающую нужный язык. Пусть
Без ограничения общности мы можем считать, что Wi f]W2 — 0. Сопоставим каждому символу ael^i новый символ а и обозначим через Г] грамматику, полученную из Г] заменой каждого символа aeVi и каждого его вхождения в каждое правило на а. Положим
