Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
В частности, нераспознаваемы в классе НС-грамматик следующие свойства языков: быть пустым, иметь пустое дополнение, быть конечным, иметь конечное дополнение, быть бесконтекстным, иметь бесконтекстное дополнение, быть автоматным, линейным, металиней-ным и т. п.
Следствие 2. Какова бы ни была НС-грамматика Го, не существует алгоритма, позволяющего для любой НС-грамматики распознать, эквивалентна ли она грамматике Г0. Тем более не существует алгоритма для решения общей проблемы эквивалентности НС-грамматик.
Действительно, свойство языка совпадать с L(T0) нераспознаваемо по пункту а) следствия 1.
Следствие 3. Если Lq— произвольный бесконечный язык, то не существует алгоритмов, позволяющих по произвольной НС-грамматике Г распознать:
-а) содержит ли L (Г) язык L0;
• б) является ли пересечение L0f)L(r) пустым.
Это вытекает из пункта б) следствия 1, так как свойством не содержать Lq обладают все конечные языки, а свойством иметь с L0 непустое пересечение — все языки с конечными дополнениями.
Аналогично получаем
Следствие 4. Если L0 — произвольный язык с бесконечным дополнением, то не существует алгоритмов, позволяющих по произвольной НС-грамматике Г распознать:
а) содержится ли L(r) в L0;
б) имеет ли объединение L0UL(r) пустое дополнение.
Из следствия 3 вытекает, например, нераспознавае-мость свойства содержать цепочку, содержащую вхождение Данной цепочки (соответственно начинающуюся или
§ 8.3] ИНВАРИАНТНЫЕ СВОЙСТВА НС-ГРАММАТИк. 267
оканчивающуюся вхождением данной цепочки) (ср. упражнение 4.7), из следствия 4 (в случае словаря не менее чем из двух символов)—нераспознаваемость свойства состоять только из цепочек, содержащих вхождение данной цепочки (соответственно начинающихся или оканчивающихся вхождением данной цепочки).
Другие примеры применения теоремы 8.3 см. в упражнениях 8.5 и 8.6.
Замечание. Если язык L0 конечен, то указанные в следствии 3 алгоритмы существуют, так как соответствующие свойства являются в этом случае булевыми. Аналогично для следствия 4.
Итак, мы убедились, что «естественно возникающие» не булевы свойства НС-языков оказываются, как правило, нераспознаваемыми. Возникает вопрос: быть может, распознаваемые свойства исчерпываются булевыми? Следующий пример показывает, что это не так.
Пример*). Фиксируем (произвольный) словарь V и сопоставим цепочкам в этом словаре натуральные числа способом, описанным в упражнении 1.3; цепочку, которой сопоставлено число п, будем обозначать со/г. Пусть, далее, R — произвольный рекурсивный язык в словаре V, не являющийся НС-языком **). Определим класс языков 3 следующим образом:
L е 3 = 3n [con е (L — R) & (V/ < п) (сог е L = сог е R)].
Свойство языка принадлежать 3 распознаваемо в классе НС (и НСу). В самом деле, для произвольной НС-грамматики Г в силу выбора R имеем L(T)?= R\ поэтому, проверяя последовательно для каждой цепочки со 1, со2, ..., принадлежит ли она L(T) и принадлежит ли она R, мы дойдем в конце концов до такой цепочки соп, которая принадлежит либо ?(Г) — R, либо R —
— L(T). Если первая из таких цепочек принадлежит L(T) — R, имеем Ь(Г)^3, если же она принадлежит R-L(T), то L (Г) ф. 3.
Вместе с тем свойство принадлежать 3 не булево. Действительно, если Фо = Фо(*1.............Хь)—булево
*) Указан М. И. Белецким.
**) Пример такого языка при ц(У)^2 доставляется хотя бы теоремой 2.4, если положить в ней F = S, f(n) = п. При ц(У) = ) нужно еще произвести перекодирование, как на стр. 259.
268 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
свойство и р—наибольший из номеров цепочек х±. .. ,хь, то всякие два языка L и L', для которых имеет место
равенство Lf]{col,..., сор} = Z/f]{col.сор}, либо оба
обладают свойством Ф0, либо оба не обладают. Но если q — наименьшее число, большее р и такое, что соq ф. фЯ*), то язык L == {col,..., со(<7 — 1)}Г)./? не принадлежит в то время как L' = LU{co^}е2?, и при этом Lfl{©l,..., юр} = I/fl{col..ар}.
§ 8.4. Некоторые проблемы, связанные с Б-грамматиками
При переходе от НС-грамматик к Б-грамматикам класс нераспознаваемых свойств языков сужается еще больше. Так, в классе Б-грамматик распознаваемы пустота (теорема 4.1), конечность (теорема 4.2), свойство содержать цепочку, содержащую вхождение х, или начинающуюся вхождением х, или оканчивающуюся таковым (упражнение 4.7); в классе НС-грамматик все эти свойства, как мы видели, нераспознаваемы. Однако и для Б-грамматик можно доказать нераспознаваемость довольно обширного круга свойств. Этим, а также доказательством неразрешимости в классе Б-грамматик некоторых проблем иного типа мы сейчас и займемся. Впрочем, нам удобнее будет говорить не о Б-, а об ОБ-грамматиках (хотя все результаты останутся справедливыми и для Б-грамматик; соответствующие видоизменения конструкций очевидны, и упоминать о них мы не будем).
Нам понадобится одно вспомогательное понятие, относящееся к машинам Тьюринга, и лемма, связывающая произвольные ДЭ-машины с ОБ-грамматиками.
Пусть М — Э-машина с входным алфавитом V, рабочим алфавитом W и множеством состояний Q. Положим Z= VU WU Q U{=Н=, Ф>^, где V — символ, не входящий в IWUQU{#, ф}- Ситуацию (qa,x',x",X',X") машины М назовем правильной, если х'х" — ±
