Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Полный вычислениям нормальной МП-машины можно естественным образом сопоставить Р2-деревья, аналогичные деревьям выводов в Б-грамматике. Покажем, как это сделать.
Пусть М — нормальная МП-машина с программой R — {г и fa} и С — некоторое ее полное вычисление. Обозначим через Ni множество всех рабочих ячеек, возникающих в вычислении С; при этом ячейка считается одной и той же с момента ее возникновения до момента ее уничтожения, но если потом «на том же месте» снова возникает ячейка, то мы считаем ее другой, даже если в ней записывается тот же символ, что и в прежней. Кроме того, через No обозначим множество всех участвующих в вычислении входных ячеек. (Ячейки, занятые символами # и Ф, в N0 и Nx не входят.) Множеством узлов нашего Р2-дерева будет объединение N0 U А^.
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
139
Из рабочей ячейки а в рабочую ячейку ^ мы про* ведем дугу, если в момент возникновения ячейки р, а значит, и в продолжение всего времени ее существо-* вания, а расположена непосредственно слева от нее. Из рабочей ячейки а во входную ячейку у пойдет дуга в одном из двух случаев: 1) если последний-из «рабо* чих» шагов, предшествующих тому «входному» шагу, на котором читается содержимое есть шаг, на котором возникает а; 2) если первый из-«рабочих» шагов, следующих за шагом, на котором читается содержимое у, — тот, на котором уничтожается а. (Заметим, что эти случаи не исключают друг друга; их конъюнкция возможна, если правее а не возникает новых ячеек.) Из входных ячеек дуги исходить не будут.
Отношение <( определим так: а р, если а и р не соединены путем ива раньше появляется головка, чем в р. (Для рабочих ячеек имеется в виду первое появление головки.) . \ ;
Определим, наконец, метки в узлах и на дугах. Метка в узле, т. е. в ячейке, будет совпадать с записанным в этой ячейке символом. Дуга, идущая в рабочую ячейку р, помечается парой чисел (/,/), где i, / — номера инструкций Г{, Г), применяемых соответственно при создании и уничтожении р. Дуга, идущая во входную ячейку у> помечается числом k — номером инструкции /•&, ‘применяемой при чтении содержимого у.
Легко видеть, что полученный так «дважды, нагруженный биграф» действительно является Р2-деревом; корнем его служит крайняя слева рабочая ячейка, сохраняющаяся в силу нормальности М в продолжение всего вычисления. Мы будем называть это Р2-дерево д е-ревом вычисления С.
Дерево вычисления можно наглядно представить так. Заменим машину М машиной имеющей одну «ветвящуюся ленту» и одну головку. «Лента» Mj представляет собой бесконечное дерево, из каждого узла которого исходит счетное множество дуг, упорядоченное изоморфно натуральному ряду. Mi-вычисление строится по М-вычислению следующим образом. Если в начале Al-вычисления на рабочей ленте записываются какие-то символы, то головка идет от корня дерева по самой левой ветви (т. е. из каждого узла переходит в первый
*140 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
из подчиненных ему узлов) и пишет в ее узлах те ,же символы. Когда М начинает уничтожать рабочие ячейки, головка Му идет по той же ветви назад (ничего не стирая!); когда М снова начинает создавать рабочие ячейки, головка Mi переходит на другую ветвь, непосредственно примыкающую к прежней справа, и т. д. Когда М читает входной символ, головка Му переходит в первую незанятую ячейку, подчиненную обозреваемой, лише! там тот же символ и сразу возвращается назад. Использованная часть «ветвящейся ленты» будет Pi-де-ревом, которое мы будем называть упрощенным деревом исходного М-вычисления; если пометить дуги этого дерева номерами и парами номеров соответствующих инструкций, получится Р2-дерево, которое, очевидно, совпадает с деревом исходного М-вычисления.
«Машину с ветвящейся лентой» Му мы будем называть древообходящим автоматом (Д-автоматом), отвечающим машине М. Можно считать, что
Д-автомат имеет инструкции только двух типов: q-+aq' и qa-^-q', означающие соответственно «спуститься этажом ниже, в первую слева незанятую ячейку, и запи-{ сать там а» и «если в обозреваемой ячейке записано а, подняться этажом выше«^ (в обоих случаях нужно также изменить состояние q на q')\ при этом а может быть как рабочим, так и входным символом, и если а — Рис. 6. входной символ, то вслед за ин-
струкцией q-+aq' должна выполняться инструкция вида aq'-^q". Действительно, каждую инструкцию вида qb —* q' можно заменить парой инструкций q-+bq", bq"-+q', где q" — новое со-
стояние.
Пр и м е р. На рис. 6 изображено дерево одного из возможных полных aabbab-вычислений в машине примера 3 на стр. 138.
Упрощенное дерево полного х-вычисления позволяет сопоставить цепочке х размеченную систему составляющих в точности тем же способом, как это делается для
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
141
дерева вывода. Так, дерево рис. 6 дает для цепочки aabbab систему (?> Аа (Aab (вЬа)) Ь). (Метки неточечных составляющих указаны здесь в виде индексов при левых скобках; для точечных составляющих метками служат соответствующие входные символы. В общем случае точечные составляющие могут иметь и другие метки.)
