Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
L = S(L , А[, ..., Af J {<рп, • • •, Ф151|» • • • | {ф^ь • • •, Ф^} )•
Язык L" порождается линейной грамматикой, получ’ае-мой из Г заменой каждого правила Aj—xojt, j — 1» • • •, t;
1 = 1, Sj, правилом Aj-^-tfji и выбрасыванием всех остальных «нелинейных» правил. Но язык L может быть получен из L" последовательным применением операций Sb , Sb , Sb. (причем в качестве подставляе- :
111 112 *strts*
мых языков выступают L(rln), L(r112), ... соответственно). Ввиду индуктивного предположения и того очевидного факта, что все фд и Yцт могут быть найдены эффективно, это завершает доказательство.
О «допускающих возможностях» детерминированных машин с ограниченным чнелрм поворотов см. упражне*
ние 5.33.
\
УПРАЖНЕНИЯ
179
Замечания. 1) Из теорем 5.9 и 5.11 вытекает, что класс металинейных языков совпадает с пересечением классов итерационно-линейных и Б-ОАЕВ-языков.
2) Просмотрев доказательство теоремы 5.5, легко убедиться, что если фигурирующая там машина Mt однодорожечная, чисто стирающая или с ограниченным числом поворотов, то и машина М будет такой же. Поэтому классы линейных, металинейных, итерационно-ли-нейных и Б-ОАЕВ-языков эффективно замкнуты относительно пересечения с ОА-языками.
3) Все эти классы эффективно замкнуты также относительно гомоморфных отображений (в частности, проекций). Это непосредственно следует из определений соответствующих типов грамматик. (Действительно, в этих определениях существенно только расположение вхождений вспомогательных символов в правые части правил, а оно не изменяется при переходе от данной грамматики к грамматике для гомоморфного образа.) Справедлив, впрочем, и более общий факт, доказательство которого предоставляется читателю, — все указанные классы эффективно замкнуты относительно подстановки вместо элементарных символов любых ОА-язы-ков.
Упражнения
5.1. Построить диаграммы грамматик примеров 1 и 3, а) из § 1.3.
5.2. Показать, что для всякой А (ОА)-грамматики можно построить эквивалентную ей однозначную А (ОА)-грамматику.
5.3. Показать, что коммутативное замыкание (упражнение 3.7) A-языка может не быть A-языком (и даже Б-языком).
5.4. По конечному автомату с программой {qi% -> q2> qia~>q2, ЧФ -> q2, q2b -> <7з, q^a -> q4, q3a -> q2, q4b -> qj и заключительными состояниями qi, q% построить детерминированный конечный автомат, пользуясь конструкцией, примененной в доказательстве теоремы 5.3. Построить диаграммы обоих автоматов.
5.5. Показать, что для всякой грамматики, все правила которой имеют вид А -> аВ, аА^-В, А-> В и А -> А, где А, В — вспомогательные символы и а—основной символ, можно построить эквивалентную ей ОА-грамматику [Biichi 1964].
5.6. Показать, что всякий A-язык является проекцией подходящего стандартного A-языка. (Определение стандартного A-языка см. в § 6.5.)
5.7. Пусть V — словарь и # — символ, не принадлежащий V. Простой окрестностной грамматикой в алфавите V
180 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ (ГЛ. 5
[Шрейдер 1969] называется конечное множество S вхождений, именуемых окрестностями, символов из V в цепочки, принадлежащие множеству {Л, #} V+ {Л, #}.
Окрестность ах*а*у$, где а и (3 могут означать ф или Л, в ы-полняется для вхождения u*a*v символа а в цепочку г = uav е V*, если и и v представимы соответственно в виде и = sx, v = yt, причем, если а = #, то s = Л, и если р = #, то t = Л.
Языком, определяемым простой о кр е с т н о с тн о й грамматикой S, называется множество всех цепочек из V+, в которых для каждого вхождения символа выполняется хотя бы одна окрестность из S.
А-грамматика называется к-о пределенной (к — натуральное число), если она обладает следующим свойством: каковы бы ни были две цепочки х и у, производимые какими-либо путями ее диаграммы, если МИМО означает наибольший конец х (соответственно у), длина которого не превосходит к, то из совпадения Мл и [у\к следует совпадение последних узлов соответствующих путей.
а) Показать, что класс языков, определяемых простыми окрест -ностными грамматиками, совпадает (и притом «эффективно») с классом языков, порождаемых ft-определенными А-грамматиками (при всевозможных к).
б) Показать, что для всякой простой окрестностной грамматики можно построить эквивалентную ей простую окрестностную грамматику, все окрестности которой имеют вид ax*a#fi (а, |3 = Л, #).
в) Показать, что всякий стандартный A-язык (см. ниже, § 6.5) порождается 1-определенной А-грамматикой.
5.8. Определим конечный автомат с выходом аналогично тому, как определялась МП-машина с выходом (упражнение 4.25). Для конечного автомата с выходом М' определим язык Lo(M') точно так же, как это делалось для МП-машины с выходом. Показать, что:
а) для любого конечного автомата М можно построить такой конечный автомат с выходом М', что L0(M') = L(M)\
б) для любого конечного автомата с выходом М' можно построить такой конечный автомат М, что L(M) = Lo(M/').
5.9. Определим преобразование, осуществляемое конечным автоматом с выходом (упражнение 5.8), аналогично тому, как это делалось для МП-машин с выходом (упражнение 4.25).
