Гладкий - Формальные грамматики и языки - 1973 (947381), страница 35
Текст из файла (страница 35)
Действительно, если пав наибольшее из чисел п, для которых )(р„не пусты, то из всякого В ~ (У вЂ” ()го0... () )б',,) будет выводима некоторая цепочка вида ЯСТ), где С ~ ((7 — ((Ро() ... () (У„,) и $з) содержит вхождение вспомогательного символа; а поскольку то же самое имеет место для С и т. д., для любого р найдется выводимая из В цепочка, содержащая не менее р вхождений вспомогательных символов, что и обеспечивает бесконечность ранга В.
Итак, Г тогда и только тогда будет ОАЕВ-грамматикой, когда ее начальный символ содержится в одном из (У, и 1о(Г) будет равно в этом случае рангу начального символа. Легко заметить, что понятие приведенного индекса ветвления позволяет охарактеризовать н МП-машины с ограниченным числом поворотов. Именно, если определить этот индекс для дерева вычисления так же, как для дерева вывода, то он будет равен числу переходов от создания ячеек к их уничтожению, иначе — половине увеличенного на единицу общего числа поворотов. Теперь без труда получается Теорема 5.1!. а) Для любой МП-машиньс М с ограниченным числом поворотов можно построить эквивалентную ей ОБ-ОАЕВ-грамматику Г такую, что 1а(Г) = 1/2(П(М) + 1). 5) Для любой ОБ-ОАЕВ- грамматики Г можно построить эквивалентную ей МП- машину М с ограниченным числом поворотов такую, что П(М) = 21з(Г) — !. Доказательство немедленно следует из лемм 4.12 н 4.13 и того факта, что конструкция, использованная прн установлении леммы 4.14, сохраняет приведенные индексы ветвления деревьев.
3 а м е ч а н и е. Это же обстоятельство вместе с леммой 5.2 дает алгоритм, позволяющий по любой МП-машине М распознать, имеет ли она ограниченное число поворотов, и в случае положительного ответа найти П(М). .. Перейдем теперь к алгебраической характеристике ОБ-ОАЕВ-языков, Пусть У = (аь ..., ад, Ь) (й ~ 0) н, У' — произвольные словари, 1. с: — У", Е'с:-' У', н пусть каждая цепочка языка Е содержит не более одного вхождения Ь. Положим 5»(Е, Е')=5(Е; а„..., аа, Ы (ас), ..., (аа), Е'). Операцию 5ь будем называть цент. $ бэ) ГРАММАТИКИ С ОГРАНИЧЕННОП ЕМКОСТЬЮ ВЫВОДОВ (77 ральной подстановкой Е' в Е (с центром Ь). Выражение, составленное из абстрактных символов еь ..., 5 с помощью знаков центральной подстановки (с произвольными центрами), будем называть ц е н трально-подстановочным выражением от (переменных) $н ..., $,.
Например, 5,(5ы 5,(ез, 5«(йз, $,) ) ) есть центрально-подстановочное выражение. Можно определить представление языка с помощью центрально-подстановочного выражения так же, как представление с помощью многочлена нли регулярного выражения (стр. 24). Мы покажем, что класс языков, представимых с помощью центрально-подстановочных выражений от линейных языков (иначе говоря, замыкание класса линейных языков относительно центральной подстановки), «эффективно совпадает» с классом ОБ-ОАЕВ-языков.
Точнее, имеет место Теор ем а 5.12. а) Для любого центрально-подстановочного выражении йЯИ ..., Е„) и любьсх п линейных ОБ-грамматик Гн ..., Г„таких, что выражение л(Е (Г,), ..., 1. (Г„)) определено *), можно построить ОБ-ОАЕВ-грамматику Г, порождающую язык т! (Е (Г,), ... ..., 1,(Г„)), б) Для любой ОБ-ОАЕВ-грамматики Г можно построить центрально-подстановочног выражение л(~ц.... с„) и лингйныг грамматики Г„..., Г„такие, что Е (Г) = Й (Е (Г,),..., Е (Г„)). Д о к а з а т е л ь с т в о. а) Достаточно показать, что если Г, и Гз — ОБ-ОАЕВ-грамматикн и каждая цепочка языка Е(Г,) содержит не более одного вхождения символа Ь, то можно построить ОБ-ОАЕВ-грамматику Г», порождающую 5„(Е(Г,), 1.
(Г)). Но при Г, = (У, )УИ1н 17) ((= 1, 2) н ))7, П))гз = Я мы можем, очевидно, положить Г„=(У, ()7, () (У„1„)7, [Ь, 1з[ 13 );з), где )с, [Ь, 1,] получается из )(, заменой всех вхождений Ь вхождениями 1. б) При 1,(Г)=1 утверждение тривиально. Пусть оно доказано для случая 1з(Г) < Ь (й ) 1), и для данной грамматики Г=(У, )(7, 1, 1() имеет место 1,(Г) =Ь. Рассмотрим произвольныйполный вывод Е)=(соо, ..., со,) ") Это значит, что если в данном выражении для каких-либо й 1 в Е(Г~) подставляется Е(Гз) вместо символа Ь, то каждая цаяочяв языка Е(ГВ содержит яа более одного вхожлеяяя Ь, 176 специАльные клАссы весконтекстных языков [Гл. э УПРАЖНЕНИЯ 179 в Г и обозначим через гтз наибольшее число 1', для которого каждая из цепочек що, ын ..., оэ, содержит точно одно вхождение вспомогательного символа.
Пусть . Е' — множество цепочек вг для всех полных выводов в Г, А!, ..., А, — все вспомогательные символы, встре- ' чающиеся в цепочках языка Е', и А( — » оэгн ..., А, — оз ы, (1=1, ..., 1) — всевозможные правила Г с левой частью Аь содержащие в правых частях либо более одного вхождения вспомогательного символа, либо ни одного. Для произвольных 1, 1„1~(/(1, 1- 1~(зь обозначим через а(г!, ..., а;„11 все вхождения вспомогательных символов в ю)1 (очевидно, г(1.: й) и через В(н, ..., В(1, — те вспомогательные символы, вхождениями которых являются а(п, ..., а(1, соответственно. г(( Положим Г(ьп=((г,((7,В„, Й (пз=1,...,г„).
Ясно, что все Г(1 являются ОЛЕВ-грамматиками и при этом Ее(Г(1 ) ( lг. Введем новые символы Ьпп ..., Ь(ы 11 и заменим каждое вхождение ап вхождением символа Ь(, ! полученную цепочку обозначим фп. (Если го!1 не содержит вспомогательных символов, то ~р(1 совпадает с оз)1.) Положим Еж=В(Е" А " Аг~~гРП* !Р1»,) ' (фи,..., чРг,,)).: Язык Е" порождается линейной грамматикой, получаемой нз Г заменой каждого правила А(- в11, 1= 1...,, 1; 1=1, ..., З(, правилом А(- гр(1 и выбрасыванием всех остальных «нелинейных» правил. Но язык Е может быть получен из Е" последовательным применением операций Вэии Ве„и ..., Вэы (причем в качестве подставляе- .
мых языков выступают Е(Г,П), Е(Г,И)... соответственно). Ввиду индуктивного предположения и того очевидного факта, что все !р(1 и Г(г„могут быть найдены эффективно, это завершает доказательство. О «допускающих возможностях» детерминированных машин с ограниченнь)м числом поворотов см. упражнр пнр 5,ОО, 3 а меча н и я. 1) Из теорем 5.9 и 5.1! вытекает, что класс металинейных языков совпадает с пересечением классов итерационно-ли ейных и Б-ОЛЕВ-языков. 2) Просмотрев доказательство теоремы 5.5, легко убедиться, что если фигурирующая там машина М, однодорожечная, чисто стирающая или с ограниченным числом поворотов, то и машина М будет такой же.
Поэтому классы линейных, металинейных, итерационно-линейных и Б-ОЛЕВ-языков эффективно замкнуты относительно пересечения с ОЛ-языками. 3) Все эти классы эффективно замкнуты также относительно гомоморфных отображений (в частности, проекций). Это непосредственно следует из определений соответствующих типов грамматик. (Действительно, в этих определениях существенно только расположение вхождений вспомогательных символов в правые части правил, а оно не изменяется при переходе от данной грамматики к грамматике для гомоморфного образа.) Справедлив, впрочем, и более общий факт, доказательство которого предоставляется читателю, — все указанные классы эффективно замкнуты относительно подстановки вместо элементарных символов любых ОЛ-языков. эпрвж не н ня 5.1.
Построить диаграммы грамматик примеров 1 н 3, з) нз 5 !.3. 5АК Покзэвть, что для всякой А(ОА)-грзммнгнкн можно построить эквнввлентную ей однозначную А(ОА)-грзммзгнку. 5.3. Показать, что коммутвтнвное ззмыквнне (упрзжненне 3.7) А-языке может не быть А-языком (н даже В-языком). 5.4. По конечному автомату с программой (а, Яр-+аз, а,а-+аз, Чгб-эаг аеб-»Чз Чза-+Чо Чза«явь д45-+дД н ззключнтельнымн состояннямн дь дз построить детерминированный конечный автомат, пользуясь нонструкпяей, примененной в докзэзтельстве теоремы 5.3. Построить диаграммы обоих автоматов. 5,5. Показать, что для всякой грзммзтнкн, все правила нагорай имеют внд А -я аВ, аА -+ В, А — з В н А -э А где А,  — вспомогзтельные символы н а — основной символ, можно посгро~ть эквнвзлентную ей ОА-грзммзгнку [Вйсш !9641.
5.6. Показать, что всякий А-язык является проекнней подходящего стандартного А-языкз. (Определенне стандартного А-языке см. в й 6.5.) 5.7. Пусть (г — словарь н 4Р— символ, не принадлежащий (г. Простой окресгностной грамматикой в алфавите 181 УПРАЖНЕНИЯ 189 СПЕЦИАЛЬНЫЕ КЛАССЫ ЕЕСКОНТЕКСТНЫХ ЯЗЫКОВ !ГЛ. З [Шрейдер 1969) называется конечное множество 3 вхождений, име- нуемых окрестностями, символов из У в цепочки, принадлежащие множеству (Л, 4Р) У (Л ~ф) Окрестность ах»а«у[), где а и 5 могут означать чр или л, в ы- и опн не т с я для вхождения и*и*а символа а в цепочку г = иао «и У», если и и о представимы соответственно в виде и = зх, о = у1, причем, если а = 4Р, то з = Л, и если В = ~У, то ! = Л. Языком, определяемым простой окрестностной г р а и м а т и к о й 3, называется множество всех цепочек из У', в ко- торых для каждого вхождения символа выполняется хотя бы одна окрестность из 3, А-грамматика называется й-о п р е д е л е н н о й (й — натуральное число), если она обладает следующим свойством; каковы бы ни были две цепочки х и у, производимые какими.
либо путями ее диаграммы, если [х)»([у)») означает наибольший конец х (соответственно у), дли- на которого не превосходит й, то нз совпаления [х)» и [у)» следует совпадение последних узлов соответствующих путей. а) Показать, что класс языков, определяемых простыми окрест- ностными грамматиками, совпадает (и притом «эффективно») с классом языков, порождаемых А.определенными А-грамматиками (при всевозможных !г). б) Показать, что для всякой простой окрестностной грамматики можно построить эквивалентную ей простую окрестностну»о грамма- тику, все окрестности которой имеют вид ах«а»[) (а, В = Л, 4Р). в) Показать, что всякий стандартный А-язык (см.
ниже, 4 6.6) порождается 1-определенной А-грамматикой. 5.8. Определим конечный автомат с выходом аналогично тому, как определялась МП-машина с выходом (упражнение 4.25). Для конечного автомата с выходом М' определим язык Е»(М') точ- но так же, как это делалось лля МП-машины с выходом. Пока- зать, что: а) для любого конечного автомата М можно построить такой конечный автомат с выходом М', что Е«(М') = Е(М); б) для любого конечного автомата с выходом М' можно по- строить такой конечный автомат М, что Е(М) = Е»(М'), 5.9. Определим преобразование, осуществляемое конечным авто- матом с выходом (упражнение 5.8), аналогично тому, кап это дела. лось для МП-машин с выходом (упражнение 4,25).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
