Гладкий - Формальные грамматики и языки - 1973 (947381), страница 32
Текст из файла (страница 32)
Итак,доказана Теорема 5.2. а) Для всякой ОА-грамматики можно построить эквивалентный ей конечный автомат. б) Для всякого конечного автомата можно построить эквивалентную ему ОЛ-грамматику. Теперь естественно заняться вопросом о взаимоотношении между детерминированными и недетерминированными конечными автоматами. Ситуация здесь су[цественно отлична от той, которую мы наблюдали для МП- машин: имеет место Т е о р е м а 5.3. Для всякого конечного автомата можно построить эквивалентный ему детерминированный конечный автомат. Д о к а з а т ел ь с т в о.
Пусть М вЂ” конечный автомат с множеством состояний [,[, начальным состоянием дь множеством заключительных состояний [гс и программой Р. Построим новый конечный автомат М' следующим образом; а) состояниями М' будут всевозможные подмножества Я; б) начальным состоянием будет (вт); в) заключительными состояниями будут те подь[ножества О, которые имеют непустые пересечения с [Зя; г) программа будет состоять из всевозможных инструкций вида А. В. Гляяляя !52 спвцилльныз аллссы взсконтакстных языков 1гл. з опв хции нлд ол-языклми Я~а-+ 1гь где Я~ а Я и Ои =(д [(Эд,еп Р) [у«а- д еббр[). Поскольку Р, и а однозначно определяют Рм автомат М' детерминирован.
Эквивалентность М' и М усматривается без труда. В 5.2. Операции над ОА-языками. Регулярные языки Теорема 5.4. Класс ОА-языков эффективно замкнут относительно операций объединения, пересечения, вычитания, взятия дополнения, умножения, итерации, усеченной итерации, подстановки, левого и правого деления на цепочку. Доказательство. Пусть Г, Гь 1» — ОА-грамматики и О, Оь О» — их диаграммы. Мы можем считать, что в каждой диаграмме в начальный узел не входит ии одна дуга.
(Это достигается применением конструкции 1 (Я~ф 10 и Рис. 1О. теоремы 5.1 с последующим построением эквивалентной стандартной ОА-грамматики, как указано на стр. !58.) Допустим, кроме того, что множества узлов О, и Ри не пересекаются. Тогда диаграмма ОА-грамматики, порождающей 1.(Г~) () 1.(Г»), получается из объединения диаграмм О~ и Р, отождествлением'(«склеиванием») их начальных узлов, причем заключительными узлами новой диаграммы будут все заключительные узлы О, и О, (рис.
10, а)). Диаграмма ОА-грамматики, порождающей 1. (Г~) 1. (Гг), получается следующим образом: берется столько разных экземпляров 0 (с~попарно непересекающимися множествами узлов), сколько заключительных узлов имеет Рь и каждый заключительный узел 0~ «склеивается» с начальным узлом одного из экземпляров 0», начальным узлом новой диаграммы будет начальный узел Оь заключительными — все заключительные узлы всех экземпляров Р, (рис. 10, б)).
Чтобы получить диаграмму ОА-грамматики, порождающей 1.(Г)*, нужно в 0 «склеить» вместе начальный и все заключительные узлы (рис. 10, в) ). Чтобы построить ОА-грамматику, порождающую С(. (Г), построим сначала детерминированный конечный автомат М, допускающий 0(Г) (теоремы 5.2 и 5.3). Пусть 0' — его диаграмма. 0' имеет единственный начальный узел (будучи детерминированным, М может иметь только одну инструкцию вида д,~-+ д„). Построим новую диаграмму О" следующим образом. Все узлы Р' будут узлами 0", все дуги 0' — дугами 0" (с теми же метками). Кроме того, Р" будет содержать еще один узел в', и из каждого узла д Ф д' будет идти в д' дуга с меткой а тогда и только тогда, когда в 0' нет дуги с этой меткой, выходящей из д, Кроме того, для каждого основного символа а в 0" будет дуга из д' в д', («петля») с меткой а.
Других узлов и дуг в 0" не будет. Единственным начальным узлом 0" будет начальный узел 0', заключительными узлами 0" будут а', и все незаключительные узлы О'. Нетрудно видеть, что цепочка х в основном словаре производится каким- либо полным путем в 0" тогда и только тогда, когда она не производится никаким полным путем в 0'. Действительно, это очевидно, если х производится некоторым путем в Р', исходящим из начального узла див ведь такой путь единственен, а диаграмма 0" определена так, что и в ней нет другого пути с началом дь производящего х. Если же х не производится никаким путем в 0' с началом а, н г — наибольшее начало х, производимое некоторым путем у~ — — гс, ..., г, с началом дг в 0', й.у-„,......д',,.... д', .с" суд р водить х.
Поскольку 0" — диаграмма некоторой ОА-грамматики 1'", имеем 0(Г") = С1. (Г'). Эффективная замкнутость класса ОА-грамматик относительно пересечения и вычитания следует из ужв а« 166 ОПЕРАЦИИ НАД ОА-ЯЗЫКАМИ Я4 СПЕЦИАЛЬНЫЕ КЛАССЫ ВЕСКОНТЕКСТНЫХ ЯЗЫКОВ !ГЛ. 3 полученных результатов для объединения и взятия дополнения. Диаграмма ОА-грамматики, порождающей х1Е(Г), получается из диаграммы 0', строившейся в процессе доказательства для СЕ(Г), если в ней объявить начальным узлом конец пути, начинающегося в прежнем начальном узле и производящего х.
(Если такой путь существует, то он единственен, а если его нет, то язык х(Е(Г) пуст. Какой из этих двух случаев имеет место, легко узнать по 0'.) Аналогично для Е(Г)/х. Доказательство для усеченной итерации и подстановки предоставляется читателю. 3 а м е ч а н и я. 1) Конструкции, использованные прн доказательстве теоремы 5.4 для объединения, умножения и итерации, применимы, очевидно, к произвольным Э-машинам (нужно только вместо узлов диаграммы говорить о состояниях). Мы будем называть отвечающие этим конструкциям операции — и их результаты — параллельной композицией, последователь'ной композицией н итерацией соответственно.
Ясно, что параллельная композиция М и М', последовательная композиция М н М' и итерация М допускают соответственно языки Е(М) 0 Е(М'), Е(М) Е(М'), Е(М) '. Очевидным образом определяются также параллельная и последовательная композиции любого конечного числа Э-машин. 2) Из доказательства теоремы 5.4 для левого деления ясно, что ОА-язык может иметь лишь конечное число различных левых частных. То же верно, разумеется, и для правых. Отметим еще следующий полезныи факт.
Теорем а 5.5. Для любой МП-машины М, и любого конечного автомата Мз можно построить МП-машину М такую, что Е(М) = Е(М!) !)Е(МЗ). Если при этом М! и Мз детерминированные, го и М можно сделать детерминированной. Доказательство. Построим МП-машину М следующим образом. Состояниями М бУдут всевозможные упорядоченные пары (Ч, Ч'), где Ч вЂ” состояние М, и ЧА — состояние Мь Инструкция (Ч, Ч„')а-«(Ч, Ч') будет принадлежать программе М тогда и только тогда, когда программа М, содержит инструкцию Ч,а-«Ч„, а программа М вЂ” инструкцию Чза-«Ч».
И стРУ ц " типов (Б) и (ш) будут всевозможные инструкции вида А(Ча Ч ) !'(Чз~ Ч ) и (Ча~ Ч ) « "4(ЧЗ Ч ) где '4Ча «Ч~р соответственно Ч, — АЧ, — инструкции М, и Ч' — произ- вольн льное состояние Мм Начальным состоянием будет ( '), где Ч, Ч' — начальные состояния М, и М соот- ветственно, заключительными состояниями — всевозмож- ные паРы !Чп Ч р (, '), где Ч Ч' — заключительные состоя- ния , и М М соответственно. Ясно, что так построенная машина М будет искомой.
Следствие. Для любой ОБ (Б)-грамматики Г, и любой ОА (А)-грамматики Гз можно построить ОБ (Б)-г амматику Г такую, что Е(Г) = Е(Г!)()Е(Гр). Теперь мы в состоянии получить еще одну -грам о н весьма важную характеристику класса ОА-языков; зта харак- способ их задания, часто оказываю- щийся гораздо более удобным, чем ОА-грамматики н конечные автоматы. Пусть У = (а!, ..., а„) — произвольный -словарь и а (в,..., $„, $„+!) — регулярное выражение без коэффи- циентов от и+ 1 переменных з„..., $„,, +!. р !, ° ° ° а а+! !. Вы ажение й(а„...,а,Л) мы будем называть регулярной ф над у, а язык, задаваемый таким выражем языком. нием (в смысле стр.
24),— р е гул яр ны м Теорема 5.5 (теорема Клини). Класс регулярных языков савла ае дает с классом непусть!х ОА-языков. оей не- лее того, по , по всякой ОА-грамматике Г, порождающе не- пустой языК можно построить регулярную ф р у задающую Е(Г), а по всякой регулярной формуле й— ОА-грамматику Г, порождающую задаваемый этой Доказательство. а) Поскольку ОА-грамматики (а ), ...
(а„), (Л) строятся тривиальным об- для языков »ап, ..., к ля задан- разом, п построение нужной ОА-грамматики для з й лярной формулы обеспечивается теор емой 5.4. но регулярн " б) Вторую половину теоремы докаж у ем инд кцией по числу э дуг диаграммы данной ст д р ан а тной ОА-грам- матики Г. сли э =, я '. Е = О, язык Е(Г) может быть непустым почки, лишь тогда, , когда он состоит из одной пустой цеп тве ждение так что в этом случае имеем д = Л.
Пусть ут р доказано для з — 1 н à — стандартная грамматика [Яь СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЪ|Х ЯЗЫКОВ [ГЛ. 6 ОПЕРАЦИИ НАД ОА-ЯЗЫКАМИ с диаграммой 0 из в дуг. Выбросим из 0 какую- либо дугу, идущую из начального узла 1 в узел В и, помеченную символом а. Полученную так диаграмму обозначим через О|, диаграмму, возникающую из О, при перенесении начального узла в В, — через Р,, диаграмму, возникающую из О, при перенесении заключительного узла в 1,— через Оз и диаграмму, возникающую из Вз при перенесении заключительного узла в . 1,— через 04 (рис. 11), (На рнс.
11 буквой К обозначен один из заключительных узлов диаграммы О, а цифрами 1, 2, 3, 4 в кружках — примеры путей в О|, Ом 0„0, соответственно.) Грамматику . с диаграммой Оь з = 1, 2, 3, 4, бу- ' в Ф дем обозначать Гь В силу индуктивного предполо- / жения можно построить регуляр- Х' ные формулы аь з = 1, 2, 3, 4, за» а ш ° з[г;[.
Всякий полный путь в О, очерка [[. видно, либо является полным путем в О|, либо представляется в виде $ат[[ат[з...ат[йаь, где а †ду (1, В), е — полный путь в з, т!ь ., т[л — полные пути в 04 (!з = О,1,...) и ~— полный путь в Р,, Ясно также, что каждый путь, представимый в таком виде, является полным путем в О. Поэтому Е(Г) = Е(1'|) ()Е(Гз) (аЕ(ГА))*аЕ(Гз), так что Е(Г) задается регулярной формулой з[| [) з[з(аиз)'ай». С л е д с т в и е.
Класс ОА-языков есть замыкание класса конечных языков относительно объединения, умножения и итерации. 3 ам еч а н не. Теорема 5.8, как ясно из ее доказательства, останется справедливой, если вместо произвольных ОА-грамматик рассматривать только такие, в диаграммах которых нет циклов (т. е.
ОА-грамматики, порождающие конечные языки), а вместо произвольных регулярных выражений — многочлеуы. П р и м е р. Языки, порождаемые грамматиками, диаграммы которых показаны на рис. 8, задаются соответственно формулами ((а () Ь) (т(()ЬсЬ)*Ьсе)*(Л() (а() 0Ь) (т(()ЬСЬ)'Ь(еЩ()с)), (а[() * ()а )'(а[() .. ()а ), а'аЬ" Ь, Дальнейшие примеры см. в упражнении 1.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
