Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
К,
к
Ь)
Рис. 10.
ОПЕРАЦИИ НАД ОА-ЯЗЫКАМИ
163
«склеивается» с начальным узлом одного из экземпляров Z)2; начальным узлом новой диаграммы будет начальный узел Du заключительными — все заключительные узлы всех экземпляров Z)2 (рис. 10,6)). Чтобы получить диаграмму ОА-грамматики, порождающей L(T)*, нужно в D «склеить» вместе начальный и все заключительные узлы (рис. 10, в)).
Чтобы построить ОА-грамматику, порождающую CL(T), построим сначала детерминированный конечный автомат М, допускающий L(T) (теоремы 5.2 и 5.3). Пусть D' — его диаграмма. D' имеет единственный начальный узел (будучи детерминированным, М может иметь только одну инструкцию вида ^ ф —*-qa). Построим новую диаграмму D" следующим образом. Все узлы D' будут узлами D", все дуги D' — дугами D" (с теми же метками). Кроме того, D" будет содержать еще один узел q'0, и из каждого узла q ?= q'0 будет идти в q'Q дуга с меткой а тогда и только тогда, когда в D' нет дуги с этой меткой, выходящей из q. Кроме того, для каждого основного символа а в D" будет дуга из q'0 в q'0 («петля») с меткой а. Других узлов и дуг в D" не будет. Единственным начальным узлом D" будет начальный узел D', заключительными узлами D" будут q'0 и все незаключительные узлы D'. Нетрудно видеть, что цепочка х в основном словаре производится каким-либо полным путем в D" тогда и только тогда, когда она не производится никаким полным путем в D'. Действительно, это очевидно, если х производится некоторым путем в D', исходящим из начального узла qi,— ведь такой путь единственен, а диаграмма D" определена так, что и в ней нет другого пути с началом qu производящего х. Если же х не производится никаким путем в D' с началом qi и z — наибольшее начало х, производимое некоторым путем = г0, ..., rs с началом qi в D', то полный путь го, ..., rs, q'0, ..., q'0 в D” будет произ-
I х \—s раз
ВОДИТЬ X.
Поскольку D" — диаграмма некоторой ОА-грамматики Г", имеем L{T") = CL{T').
Эффективная замкнутость класса ОА-грамматик относительно пересечения и вычитания следует из уже
6*
164 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. 5
лолученных результатов для объединения и взятия дополнения.
Диаграмма ОА-грамматики, порождающей х\Ь(Г), получается из диаграммы D', строившейся в процессе доказательства для CL(T), если в ней объявить начальным узлом конец пути, начинающегося в прежнем начальном узле и производящего х. (Если такой путь существует, то он единственен, а если его нет, то язык x\ L(T) пуст. Какой из этих двух случаев имеет место, легко узнать по D'.) Аналогично для L(T)lx.
Доказательство для усеченной итерации и подстановки предоставляется читателю.
Замечания. 1) Конструкции, использованные при доказательстве теоремы 5.4 для объединения, умножения и итерации, применимы, очевидно, к произвольным Э-машинам (нужно только вместо узлов диаграммы говорить о состояниях). Мы будем называть отвечающие этим конструкциям операции — и их результаты — параллельной композицией, последовательной композицией и итерацией соответственно. Ясно, что параллельная композиция М и М', последовательная композиция М и М' и итерация М допускают соответственно языки L(Af)U L(Mr), L(M)L(M’), L(M)*. Очевидным образом определяются также параллельная и последовательная композиции любого конечного числа Э-машин.
2) Из доказательства теоремы 5.4 для левого деления ясно, что ОА-язык может иметь лишь конечное число различных левых частных. То же верно, разумеется, и для правых.
Отметим еще следующий полезный факт.
Теорема 5.5. Для любой МП-машины М\ и любого конечного автомата М2 можно построить МП -машину М такую, что L(M) = L(MX)(\L(M2). Если при этом М, и М2 детерминированные, то и М можно сделать детерминированной.
Доказательство. Построим МП-машину М следующим образом. Состояниями М бУдут всевозможные упорядоченные пары (q, q'), где q — состояние М{ и q'— состояние М2. Инструкция (qa, q'^)a-*(qy, q'&) будет принадлежать программе М тогда и только тогда, когда программа Mj содержит инструкцию qaa -* qy,
ОПЕРАЦИИ НАД ОА-ЯЗЫКАМИ
165
а программа М2 — инструкцию q'^a-*q'y. Инструкциями типов (и) и (iii) будут всевозможные инструкции вида A{qa, q')~+(qp, q') й (qa, q')->A{q^ q'), где Aqa-+q^, соответственно qa -> Aq— инструкции M, и q' — произвольное состояние M2. Начальным состоянием будет (q0, где q0, q'0 — начальные состояния Mj и Af2 соответственно, заключительными состояниями—всевозможные пары (cjv q'f), где qft q'f — заключительные состояния Mi и М2 соответственно. Ясно, что так построенная машина М будет искомой.
Следствие. Для любой ОБ (Б)-грамматики Ti и любой О А (А)-грамматики Г2 можно построить ОБ (Б)-грамматику Г такую, что L(T) = L(ri) П?(Гг).
Теперь мы в состоянии получить еще одну весьма важную характеристику класса ОА-языкЬв; эта характеристика дает способ их задания, часто оказывающийся гораздо более удобным, чем ОА-грамматики и конечные автоматы.
Пусть V = {аи ..., ап} — произвольный словарь и Я (|ь ..., |n+i) — регулярное выражение без коэффи-
циентов от я -j- 1 переменных |ь ..., |n, |п+ь Выражение % (С],..., ап, А) мы будем называть регулярной формулой над V, а язык, задаваемый таким выражением (в смысле стр. 24),— регулярным языком.
