Гладкий - Формальные грамматики и языки - 1973 (947381), страница 31
Текст из файла (страница 31)
(Такие машины иногда называют счетчиковыми) 4.3!. Построить детерминированные МП-машины, допуснающие: а) язык примера 7 из $1.3; б) «язык бинарных скобочных последовательностей» (порождаемый грамматикой со схемой (7-» (П), ! — » ( ))); в) язык примера 3 из й 45; г) язык (х,йуййк«ЬХ»2, [х,, х„уои(а„..., а„); Ь«Й(аи ..., ая)). 4.32. Показать, что для всякой детерминированной МП-машины можно построить эквивалентную ей детерминированную МП-машину «без зацикливания», т.
е. такую, что для любой входной цепочки х этой машины ее (единственное) к-вычисление заканчивается [5сйй1- гепЬегЕег 1963, С!пзЬпг8 !966). 4.33. Показать, что класс языков, допускаемых детерминированными МП-машинами, эффективно замкнут относительно: (а) умно. жения, (б) итерации, (в) подстановки, (г) левого я правого веления на цепочку, (д) взятия дополнения [С!пзйнг8 — Сге!Ьасй 1966 (Ь), С)пзйнг8 1966]. [Указание.
Для (д) испольэовать упражнение 4.32.] За и е» ание. Из (д) немедленно следует, что для всякой де. терминивованной МП.машины М можно построить детерминированную МГ(-машину, распознающую язык Е(М). 4.34. Показать, что следующие языки не лопускаются детерминированными МП.машинами; а) Е', Е', ..., где Е=(хд[х«и(аь ..., аа)')(а>1); б) Е', где Š— то же, что в а); в) (к,к,йу,уй|524] к,, хь у «и(ан ..., а„)') (а>1).
[56 В.ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОИ ПАМЯТЬЮ [ГЛ. 4 Замечание. Сопоставляя упражнения 4.3[,г) и 4.34,в), ви. дим, что нласс языков, допускаемых детерминированными МП.машинами, не замкнут относительно обращения '). 4.35. Показать, что если [Г н [г — непересекающиесч алфавиты, ЕшУ4 пузырь,то: а) по детерминированной МП-машине, допускающей язын Еу, можно построить детерминированную МП-машину, допускающую Е; б) по однозначной Б-грамматине, порождающей Еу, можно построить однозначную Б грамматику, порождающую Е. 4.36.
Показать, что для всякой грамматики, левые части правил которой не содержат основных символов, а правая часть иаждого правила содержит хотя бы одно вхождение основного символа, можно построить эквивалентную ей Б-грамматику (О[пзьпгя— ОгегЬасЬ !956(а)!, ') 0 бр а щ е н и е м называется операция, сопоставляющая языку Е язык Е = (Л ) х 4м ц (а также ее результат). ГЛАВА 5 НЕКОТОРЫЕ СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ $5.1. Автоматные и обобщенные автоматные языки. Конечные автоматы В предыдущей главе мы видели, что присоединение к В-грамматикам правил вида А- Л делает класс порождаемых этими грамматиками языков в ряде отношений более естественным (достаточно вспомнить об удобстве описания с помощью МП-машин).
В еще большей степени это справедливо, как мы скоро убедимся, для А-грамматик. Поэтому их изучение мы начнем со следу[ощего определения. (ОВ-) грамматика называется о б о б ще н н о й а в- томатной грамматикой (ОА-грамматикой), если каждое ее правило имеет вид А — аВ, А — а или А-ьЛ, где А,  — вспомогательные символы и а — основной символ. Язык, порождаемый ОА-грамматикой, называется ОА-я з ы к о м. Полезно заметить, что в ОА-грамматике всякая промежуточная цепочка полвого вывода имеет вид хВ, где х — цепочка в основном словаре и  — вспомогательный символ.
Теорема Б.). Для любой ОА-грамматики Г можно построить А-грамматику Г' такую, что Е(Г') = Е(Г)— — (л). Д о к а з а т е л ь с т в о. С помощью процедуры, при-. мененной в доказательстве леммы 4.2, можно перестроить Г так, чтобы начальный символ не встречался в правых частях правил. После этого достаточно для каждой пары правил вида А — аВ, В-+Л'добавить к схеме !58 специАльные клАссы Весконтекстных языкОВ [гл. б з кп Автозьчтные и Ововщенные АатомАтные языки !88 грамматики правило А- а (если оно не содержалось там ранее) и затем изъять все правила вида А - Л.
Будем называть ОАгграмматнку с т а н д а р т н о й, если она ие имеет правил вида А — а. Для каждой ОЛ. грамматики легко построить эквивалентную ей стандартную ОА-грамматику: достаточно добавить к вспомогательному словарю новый символ К, к схеме — правило К - Л и заменить каждое правило А — а правилом А — аК Стандартные ОА-грамматики допускают следующее- очень простое и наглядное изображение. Рассмотрим мультнграф, узлами которого служат вспомогательные символы данной грамматики и для каждой пары узлов А, В нз А в В идет столько дуг, сколько грамматика имеет правил вида А- аВ; каждую из этих дуг пометим соответствующим основным символом а, Начальный символ будем называть начальным узлом, а каждый узел А, для которого имеется правило А — Л,— з а кл ю ч и тел ь н ы м. Построенный таким образом мультиграф с помеченными дугами и выделенными в множестве узлов начальным и заключительными узлами мы будем называть д и а г р а м м о й данной грамматики.
Нестандартной ОА-грамматике мы также будем сопоставлять диаграмму, совпадающую, по определению, л е ° с ",,,) «ЛФЩ. р 2 ., е а а) Ркс. 8. с диаграммой стандартной грамматики, полученной из данной указанным выше способом. На рис. 8,а) показана диаграмма стандартной ОА- грамматики со схемой (1- аА, 1- ЬА, А - дА, А - ЬС, С-' сВ;В- ЬА,С- е0,С- '1Р,В е1,1-+Л, В+Л, В-~ Л).
На рис. 8, б), в) показаны диаграммы Л-грамматик примеров 2 и 4 из $ !.3. Здесь и далее начальный узел обозначается символом 1, заключительные узлы выделяются подчеркиванием. Если Аа, Аь ..., А — путь в диаграмме грамматики Г и для каждого 1 = (, ..., л имеется дуга, идущая из Ае 1 в А; и помеченная символом а, мы будем говорить, что данный путь п р о и з в о д и т цепочку а, ... а„. Всякий путь длины О производит, по определению, цепочку Л.
Цепочка х будет, очевидно, производиться путем, начинающимся в А и оканчивающимся в В, тогда и только тогда, когда А)екхВ (~ ознаг чает здесь то же, что на сгр. !24). ' Будем называть путь Ае, ..., А ц и к л о м, если А, = А„, и п о л н ы м п у т е м, если Ас — начальный узел и А„— заключительный узел. Между полными выводами в Г и полными путями диаграммы имеется очевидное взаимно однозначное соответствие, и цепочка принадлежит 1. (Г) тогда и только тогда, когда она производится некоторым полным путем. Диаграммы позволяют, в частности, особенно просто интерпретировать для ОА-грамматик понятия н утверждения из 8 4.2.
Так, зависимость В от А означает наличие пути из А и В, бесплодность А — отсутствие пути из А в заключительный узел, неустранимость А — наличие проходящего через А полного пути, цикличность А — наличие проходящего через А цикла. Выбрасывание всех устранимых узлов сразу дает теперь приведенную грамматику; приведенная грамматика порождает конечный язык тогда и только тогда, когда ее диаграмма не содержит циклов Заметим еще, что Л ~ 1.(Г) тогда и только тогда, когда начальная вершина диаграммы является заключительной. Перейдем теперь к характеристике ОА-языков в терминах машин Тьюринга. Рассмотрим наиболее простой из мыслимых нетривиальных частных случаев Э-машины, а именно машину, ничего не делающую на рабочей ленте, иначе говоря, имеющую инструкции только вида (!) (стр.
42). Такую Э-машину мы будем называть Венечным автоматом. Можно представлять себе 'лбй специАльные клиссы Весконтекстных ЯзыкОВ [гл. 6 и Я.Ц АВТОМАТИЫЕ И ОБОБЩЕННЫЕ АВТОМАТИЫЕ ЯЗЫКИ [б[ конечный автомат как Э-машину (если угодно, МП-машину) без рабочей ленты; поэтому мы будем говоритьо; л е н т е и г о л о в к е конечного автомата, подразумевая ' входную ленту и входную головку. Конечному автомату можно сопоставить д и а г р а им у аналогично тому, как это было сделано для ОА- грамматик. Именно: узлами диаграммы будут состоя.- ния; из узла уи в узел да будет идти дуга, помеченная символом а, если а Ф ~, ф и автомат имеет инструк.. цию авиа-+ уй, узлы д„, для которых имеются инструк-.
ции вида ут ЧРг — д, будут называться н а ч а л ь н ы м и, узлы, принадлежащие [',[с, — з а к л ю ч и т ел ь н ы м и. Пример диаграммы конечного автомата представлен на рис. 9; начальные узлы обведены крумткамн, заключительный (едииственный) выделен подчеркиванием. Рис. 9. Цепочка, производимая путем, а также цикл и полный путь определяются для диаграммы автомата точно так же, как для диаграммы грамматики. Непосредственно ясно, что цепочка х производится путем, начинающимся в ди и оканчивающимся в дв, тогда и только тогда, когда для любой цепочки ген ~ $'и и подходяще- .; го символа Ь ~ [т()(ф), где )т — (входной) алфавит ав- .' томата, из ситуации (д, г, хЬ)' достижима ситуация (да, гх, Ь) *). Поэтому цепочка х производится полным путем диаграммы конечного автомата М тогда и только тогда, когда х ~ (.(М).
Автомат допускает пустую цепочку тогда и только тогда, когда пересечение множеств начальных и заключительныАузлов не пусто. ') В обоянячениях снтуяиий опущены компоненты, относящиеся к рабочей ленте. Различие между диаграммами грамматики и автомата сводится к тому, что первая имеет единственный начальный узел, чего не требуется от второй. Поэтому для всякой ОА-грамматики можно построить эквивалентный ей конечный автомат. Однако верно и обратное, поскольку для всякого конечного автомата можно построить эквивалентный ему конечный автомат с единственным начальным узлом в диаграмме: достаточно ввести новое состояние д' н новую инструкциюу[4~-+д', изъять все старые инструкции вида д,~- д, и добавить всевозможные инструкции вида д'а — да, где а и аз таковы, что старая программа содержала для некоторого у инструкции дт 4~ - ая, у а -+ да (попросту говоря, нужно добавить к диаграмме новый узел и провести из него дуги во все те узлы, в которые идут дуги из прежних начальных узлов, наметив зти дуги теми же символами); кроме того, если хотя бы один из прежних начальных узлов заключительный, то нужно объявить заключительным и новый начальный узел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
