Гладкий - Формальные грамматики и языки - 1973 (947381), страница 28
Текст из файла (страница 28)
Поскольку,А и А' частично пересекаются, Тчи Т'. Дальнейшие примеры — в упражнениях 4.16 и 4,20. (См. также упражнение 5.!7, б).) ф 4.5. Машины с магазимной памятью Подобно тому как классу произвольных грамматик соответствует класс произвольных машин Тьюринга и классу НС-грамматик — класс машин без растяжения, для Б-грамматик также имеется отвечающий им в том же смысле тнп машин Тьюринга — так называемые машины с магазинной памятью. Э-машина называется м а ш н н о й с м а г а з и н н о й и а м я т ь ю (МП-м а ш и н о й), если ее программа содержит только инструкции типов (!) — (И) (стр. 42).
Таким образом, рабочая головка МП-машины всегда находится в крайней справа ячейке; создав однажды рабочую ячейку, головка может уйти от нее (если не уничтожит ее тут же) только вправо и получает возможность «заглянуть» в нее снова лишь в тот момент, когда уничтожает ее. Чем раньше ячейка создана, тем позже она будет уничтожена и тем самым «использована»; это напоминает принцип работы магазина в автоматическом оружии, чем и объясняется название «машина с магазинной памятью». П р и м е р 1. Пусть М вЂ” машияа с программой (ч! Чà — '41!» д!-«Адм дза-» 4)„ч»Ь-«чз А»7з — ~414» 41»Ь — «4)з. д» $-«аз) и единственным заключительным состоянием дз. Легко видеть, что й(М) =(а"Ь" ~а=1, 2, .). Пример 2. Язык (хх ~хан(а! ..., а„)') допускается машиной с программой (д! зг-+4)!» и! зг-'4)з»+з» 133 а-ГРАммАтики и мАшины с мАГАзиннОЙ пАмятью 1ГЛ. о МАШИНЫ С МАГАЗИННОИ ПАМЯТЬЮ .139 д>-+Ад,Р„д>ыаг-~ди да,— ~у+„+„А>Ч, „-Р>-+у»+о, у»о+оп> — »В+он чт»Р>Ф-»чо) (1'=1 ..., п) и единственным заключительным состоянием до.
Пример 3. Язык примера 8 из 3 1.3 допускается машиной с программой ((1) а, — Еу„(2) до 4~ - д„(3) д,. Адм (4) д,а д„(5) д,(> -+ д4, (6) Ау, —. 4„(7) а, -+ Вуи (8) Чоэ Ч> (0) Ч,а уы (10) Вдо д„(11) д,а чо, (12) Еао- ао) и единственным заключительным состоянием ао. Дальнейшие примеры МП-машин см.
в упражнении 4.22. Примеры детерминированных МП-машин см. на стр. 152 н в упражнении 4.31. Назовем МП-машину н о р м а л ь н о й, если она имеет единственное заключительное состояние и каждое ее полное вычисление начинается записью на рабочей ленте некоторого символа Е, который уничтожается лишь на последнем шаге вычисления.
Лемм а 4.11. Длл любой,МП-машины можно пас>роитв эквивалентную ей нормальную МП-машину. Д о к а з а т е л ь с т в о. Достаточно добавить к множеству состояний данной машины два новых состояния а', и ри объявив их соответственно начальным и заключительным вместо прежних, к рабочему алфавиту — новый символ Е и к программе — новые инструкции у',— »Еа, и у>Š— а для каждого а> ен Яо (а~ — прежнее начальное состояние, Яо — множество ррежннх заключительных состояний). Полныо> вычислениям нормальной МП-машины можно естественным образом сопоставить Ро-деревья, аналогичные деревьям выводов в Б-грамматике. Пока>кем, как это сделать.
Пусть М вЂ” нормальная МП-машина с программой Д = (Гь ..., Г„) и С вЂ” некоторое ее полное вычисление. Обозначим через >"1> множество всех рабочих ячеек, возникающих в вычислении С; при этом ячейка считается одной и той же с момента ее возникновения до момента ее уничтожения, но если потом «на том же месте» снова возникает ячейка, то мы считаем ее другой, даже если в ней записывается тот же символ, что и в прежней.
Кроме того, через й(о обозначим множество всех участвующих в вычислении входных ячеек. (Ячейки, занятые символами 4~ и ф, в Уо и У, не входят.) Множеством узлов нашего Ро-дерева будет объединение Мо () Жь Из рабочей ячейки а в рабочую ячейку () мы про. ведем дугу, если в момент возникновения ячейки а значит, и в продолжение всего времени ее существо.
вания, и расположена непосредственно слева от нее. Из рабочей ячейки а во входную ячейку у пойдет дуга в одном нз двух случаев: 1) если последний- из «раба. чих» шагов, предшествующих тому «входному» шагу, на котором читается содержимое у, есть шаг, на катаром возникает а; 2) если первый из.«рабочих» шагов, следующих за шагом, на котором читается содержи. мое у,— тот, на котором уничтожается а. (Заметим, что этн случаи не искл>очают друг друга; их конъюнкция возможна, если правее а не возникает новых ячеек.) Из входных ячеек дуги исходить не будут, Отношение ( определим так; и( р, если а н р не соединены путем н в и раньше появляется головка, чем в 8.
(Для рабочих ячеек имеется в виду первое появление головки.) Определим, наконец, метки в узлах н на дугах. Метка в узле, т. е. в ячейке, будет совпадать с записанным в этой ячейке символом. Дуга, идущая в рабочую ' ячейку помечается парой чисел (1',1), где 1, 1' — номера нпструкЦнй Гь Гь ПРИМЕНЯЕМЫХ СООтВЕтСтВЕННО ПРИ СОЗДаинн Н уничтожении р. Дуга, идущая во входную ячейку у, помечается числом й — номером инструкции Гм приме'- няемой при чтении содержимого у.
Легко видеть, что полученный так «дважды. нагруженный биграф» действительно является Рюдеревом; корнем его служит крайняя слева рабочая ячейка, сохраняющаяся в силу нормальности М в продолжение всего вычисления. Мы будем называть это Р»-дерево деревом вычисления С. Дерево вычисления можно наглядно представить так. Заменим машину М машиной Мь имеющей одну «ветвящуюся ленту» и одну головку. «Лента» М, представляет собой бесконечное дерево, из каждого узла которого исходит счетное множество дуг, упорядоченное изоморфно натуральному ряду.
М,-вычисление строится по М-вычислению следующим образом. Если в начале М- вычисления на рабочей ленте записываются какне-то символы, то головка М, идет от корня дерева по самой левой ветви (т. е. из каждого узла переходит в первый .!4о Б-ГРАммАтики и мАшины с мАГАзиннОЙ пАмятью !Гл. ! МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ !4! нз подчиненных ему узлов) н пишет в ее узлах те же символы. Когда М начинает уничтожать рабочие ячейки, головка М! идет по той же ветви назад (ничего ие стирая!); когда М снова начинает создавать рабочие ячейки, головка М! переходит на другую ветвь, непо- К с едственно примыкающую к прежней справа, и т. д. огда М читает входной символ, головка М! переходит в первую незанятую ячейку, подчиненную обозреваемой, пище! там тот же символ и сразу возвращается назад.
Использованная часть «ветвящейся ленты» будет Р!-деревом, которое мы будем называть у п р о щ е н н ы м д еревом исходного М-вычисления; если пометить дуги этого дерева номерами и парами номеров соответствующих инструкций, получится Р»-дерево, которое, очевидно, совпадает с деревом исходного М-вычисления. «Машину с ветвящейся лентой» М! Мы будем называть д р е в о о б х о д я щ и м а л т о м а т о м (Д - а в т ам а то м), отвечающим ма!Нине М.
Можно считать, что Д-автомат имеет инструкции только двух типов: !7- а!7' и !)а- !7', 66 означающие соответственно «спу- А ститься этажом ниже, в первую 4 5 слева незанятую ячейку, и запи« 36 сать там а» н «если в обозревае- 7,70 мой ячейке записано и, поднять- 4 ся этажом выше!Г (в обоих спу- В 6 ! чаях нужно также изменить состояние !7 на !7'); при этом а может быть как рабочим, так и а входным символом, и если а— Рас. в. входной символ, то вслед за ин- струкцией !7- и!7' должна выполняться инструкция вида а!7'- !7". Действительно, каждую инструкцию вида !)Ь- !7' можно заменить парой инструкций !7- Ьд", Ьд»- !7', где !7» — новое состояние.
П р и м е р, На рис. 6 изображено дерево одного из возможных полных ааЬЬаЬ-вычислений в машине примера 3 на стр, 138. Упрощенное дерево полного х-вычисления позволяет сопоставить цепочке х размеченную систему составляющих в точности тем же способом, как это делается для дерева вывода. Так, дерево рис. 6 дает для цепочки ааЬЬаЬ систему (в Аа(„ПЬ(БЬа)) Ь). (Метки неточечных составляющих указаны здесь в виде индексов при левых скобках; для точечных составляющих метками служат соответствующие входные символы.
В общем случае точечные составляющие могут иметь и другие метки.) Можно представлять себе работу МП-машины еще и следующим образом: при создании рабочей ячейки перед обозреваемым в данный момент входным символом ставится помеченная левая скобка — меткой служит соответствующий рабочий символ, — а при уничтожении рабочей ячейки после обозреваемого входного символа ставится правая скобка.
Таким способом мы получим скобочное изображение соответствующей размеченной системы составляющих — правда, с той особенностью, что одна составляющая может оказаться ограниченной несколькими парами скобок, и внутри некоторых пар скобок может не содержаться входных символов. Лингвистически МП-машины интерпретируются как «предсказуемостные процедуры синтаксического анализа», или «предсказуемостные анализаторы». В таком анализаторе предложение («содержимое входной ленты») просматривается слева направо, и при просмотре слова (входного символа) может вырабатываться предположение («предсказание») о его синтаксической роли (это соответствует созданию рабочей ячейки) или проверяться его совместимость с последним из уже выработанных, но еще не проверенных предположений (соответствует уничтожению рабочей ячейки).
Результатом работы анализатора является размеченная система составляющих (отвечающая дереву вычисления). Подробнее см. (Гладкий — Мельчук 1969, стр. 136 — 148,] Отметим две особенности деревьев вычисления, отличающие их от деревьев вывода. 1) Между полными вычислениями нормальной МП- машины и их деревьями имеется очевидное взаимно однозначное соответствие. 2) В то время как для всякой Б-грамматики Г существует постоянная !( такая, что ширина дерева вывода в Г никогда не превосходит !(, для деревьев вычислений в МП-машине такой постоянной может не быть (упражнение 4.24). !42 Б-ГРАммАтики и мАет!Нны с мАГАзиннОЙ пАмятью !Гл. е МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ Впрочем, для любой МП-машины можно построить эквивалентную, обладающую такой постоянной; ее даже можно сделать равной двум. Это непосредственно вытекает из доказываемых ниже лемм 4.13 и 4.14.
Докажем теперь следующую основную теорему. Теорема 4.9, а)Для всякой ОБ-грамматики можно построить эквивалентную ей МП-машину, б) Для всякой МП-машины можно построить эквивалентную ей ОБ-грамматику, Для доказательства введем некоторые понятия и обозначения. Назовем простейшей окрестностной едграмматикой с порядком*) (ПОграмматик о й) упорядоченную четверку 6 = ( р', Ф',1, Б), где и (Р— непересекающиеся конечные множества, 7 — элемент Ф' и 5 — конечное множество «окрестностей» вЂ” Рн деревьев с пометками из 1' () (Р, состоящее из «одноэтамсных» деревьев вида еА ОСГ Осе ОСА (отношение ( изображается здесь и далее отношением «левее») и «единичных» деревьев вида а; при этом метки из )т могут быть только у висячих узлов. Крайний слева висячий узел неединичного дерева может быть помечен ещее дополнительным символом 1, а крайний 'справа — символом ).
(Если висячий узел единственный, то он может нести обе дополнительные метки.) ПО-грамматика будет называться о г р а ни ч ени ойй, если в каждой ее неодноэлементной окрестности крайние слева и справа висячие узлы несут соответственно метки ) и ). Будем обозначать через йд (6) множество всевоз'можных Р;деревьев Т, удовлетворяющих следующим условиям: 1) Если з — некоторый невисячий узел Т, з,( ... (Зр — все подчиненные ему узлы и й, бь ... ..., )!р — метки при з, зь ..., з„ соответственно, то найдутся такие й, ..., ев, 1 = !1 ( тв ( ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
