Теория формальных грамматик - Гросс М.
Скачать (прямая ссылка):
(S1-^diSlgi I 01 : S1-*с
O2
(S2-^diS2Hi I 1 Si-^c 138
Часть II. Некоторые замечательные классы языков
Ни та, ни другая грамматика не являются неоднозначными, поскольку в каждой из них все порождаемые ими цепочки различаются между собой наличием или порядком маркеров.
Проблема пустоты пересечения языков L(Gj) и L(G2) оказывается по существу проблемой Поста: действительно, она равносильна вопросу о возможности равенства
AikCgil ... Bii = dtl ... dlkchi{ ... hik
для какой-нибудь последовательности индексов U, ¦¦¦, ik-
Рассмотрим теперь объединение языков L(G1) и L(G2); оно порождается грамматикой Glj2 с аксиомой 5:
S-I-S1
S-^S2
Gu2 : Gi •
G2
Цепочка f является неоднозначной тогда и только тогда, когда ее можно вывести двумя способами, а именно
5 -> 5, -> (через G1)
и
S-* S2-* (через G2) ->f;
узнать, возможны ли для какой-нибудь цепочки оба способа—»то опять проблема Поста.
Таким образом, проблема неоднозначности неразрешима уже для линейных грамматик с тремя вспомогательными символами. Отсюда вытекает и ее неразрешимость в общем виде.
Теорема. Проблема неоднозначности КС-грамматик неразрешима.
8.2.5. Существенная неоднозначность
Рассмотрим грамматику
S-^aSa S-*bSb " 1 S-yaaSaa S -у с
Относительно этой грамматики всякая цепочка, содержащая два последовательных вхождения символа а, неоднозначна: такую цепочку можно получить либо двукратным применением первого правила, либо однократным применением третьего.
Напротив, грамматика G'm из п. 8.2.1 порождает тот же самый язык без неоднозначности. Мы говорим, что язык Lm [— L(Qrm) Гл. VIII. Нераспознаваемые свойства КС-грамматик
139
= L(Gfl)] не является неоднозначным (или существенно неоднозначным) относительно класса минимальных линейных грамматик.
Для любого класса КС-грамматик можно поставить вопрос: существует ли такой язык, что всякая порождающая его грамматика, принадлежащая к этому классу, является неоднозначной (т. е. существует ли язык, существенно неоднозначный относительно данною класса)?
Р. Парик [1961] показал, что любая КС-грамматика, порождающая язык
Lla = {apb"arbs | р = г или q = s) = {anbqanbs} U {a"bmarbm},
является неоднозначной. (Именно, в любой КС-грамматике, порождающей этот язык, найдутся неоднозначные цепочки вида anbnanbn.) ')
§ 8.3. СУЩЕСТВЕННАЯ НЕОДНОЗНАЧНОСТЬ МИНИМАЛЬНЫХ ЛИНЕЙНЫХ языков
Цель настоящего параграфа — изучить явление существенной неоднозначности применительно к одному простому классу КС-грамматик, а именно к минимальным линейным грамматикам. Для более широких классов КС-грамматик такое изучение было бы значительно сложнее.
8.3.1. Пример существенно неоднозначного минимального линейного языка
Рассмотрим язык
Ll = IamCan I m > п > 0}.
Напомним, что линейная грамматика называется минимальной, если она имеет только один нетерминальный символ — начальный— и только одно терминальное правило вида S-* с, причем символ с встречается только в этом правиле.
Докажем, что всякая минимальная линейная грамматика, порождающая язык Lb является неоднозначной.
Любая минимальная линейная грамматика, порождающая L1, будет иметь вид
Ясно, что Pi^- qi~. в противном случае грамматика будет порождать некоторые цепочки вида атсап, где т < п. Поэтому каждое
') Проблема распознавания существенной неоднозначности КС-языка относительно класса всех КС-грамматик алгоритмически неразрешима (см. Глад-Кий [1965], Гинзбург [1966, гл. VI], Грейбах [1968]). — Прим. ред. 140
Часть II. Некоторые замечательные классы языков
правило грамматики будет принадлежать к одному из трех следующих типов:
Поскольку эти правила должны давать, в частности, цепочки ас и аса, наша грамматика обязательно содержит правила S-* -*aS, S-*aSa.
С другой стороны, ясно, что этих правил вместе с правилом S-* с достаточно для порождения Li. Посмотрим, как ведет себя содержащая их грамматика.
Пусть, например, мы хотим получить цепочку атсап. Применим Л раз правило S-*aS и fx раз правило S-*aSa; имеем А+ + р = т, fx = п.
Дерево вывода зависит от того, в каком порядке применялись правила, но различных последовательностей применений правил существует столько, сколькими способами можно выбрать п элементов из т элементов, т. е. Cm-
Итак, степень неоднозначности цепочки атсап равна Cm.
Пример. Для цепочки OiCa2 мы имеем Cl = 6 выводов, а
5 -*aPkS, pk > О, S-^apISa4I, Pj>qj> О,
с.
именно
S
а а а а с
а а
а а а а с
а
а
и т. д. Гл. VIII. Нераспознаваемые свойства КС-грамматик
141
Заметим, что Li не является существенно неоднозначным относительно класса всех линейных КС-грамматик. Действительно, приводимая ниже грамматика Gl порождает его без неоднозначности;
S~*aSa
О,
S-T-T-S-
¦аТ ¦аТ -с ¦ с
Заметим, что грамматика Gl — последовательностная.
Итак, язык может быть существенно неоднозначным относительно некоторого класса грамматик и не быть таковым относительно другого класса.
8.3.2. Достаточное условие однозначности минимальной линейной грамматики
