Гладкий - Формальные грамматики и языки - 1973 (947381), страница 29
Текст из файла (страница 29)
( !А = р, что «) А — от Авторот — «доро»о». каждое дерево у31, А,'! у:! т принадлежит 5', и при этом крайний слева висячий узел первого нз этих деревьев, рассматриваемого как окрестность из 5, несет добавочную метку (', а крайний справа висячий узел последнего — метку ~, и никакие другие узлы деревьев Т; меток ( и ) не несут.
2) Если з— висячий узел Т с меткой а, то дерево а принадлежитЯ. 3) Корень Т несет метку й Будем полагать далее е,(6) = (Прре4(Т) ) Те=(.д (6)). Будем, наконец, обозначать множество всех деревьев полных выводов в ОБ-грамматике Г, соответственно всех упрощенных деревьев полных вычислений нормальной МП-машины М, через Т.д (Г), соответственно -Т.д (М).
Теорема 4.9 непосредственно вытекает из следующих трех лемм. Л е м м а 4.12. а) Для всякой ОБ-грамматики Г можно построить такую ограниченную ПО-грамматику 6, что Т.д (6) = е.д(Г) б) Для всякой ограниченной ПО-грамматики 6 можно построить такую ОБ-грамматику Г, что ~.д(Г') = Б,(6). Лемма 4.!3. а) Для всякой нормальной МП-машины М можно построить такую ПО-грамматику 6, что Т-д (6) = Т-д (М). б) Для всякой ПО-грамматики 6 можно построить такую нормальную МП-машину М, что (.,(М) = (., (6). Лемм а 4.14. 'Для всякой ПО-грамматики 6 можно построить такую ограниченную ПО-грамматику 6', что й(6') = (.(6).
Д о к а з а т е л ь с т в о л е м м ы 4.12. Для произвольной ОБ-грамматики Г =(У, )р", 1, Д) положим 6(Г)=()Г, Я7, т', О), где 3 состоит из всевозможных окрестностей вида ! се! схе сел.! 144 В-ГРАММАТИКИ И МАШИНЪ| С МАГАЗИННОИ ПАМЯТЬЮ |ГЛ. | МАШИНЫ С МАГАЗИННЯЙ' ПАМЯТЬЮ 145 таких, что А- а,а»... а» еи )!, и ° а таких, что а- Лен )! или а~к'. Ясно, что таким образом устанавливается взаимно однозначное и эффективное в 'обе стороны соответствие между ОБ«грамматиками и ограниченными ПО-грамматиками.
Равенство !А(0(Г)) =ЕА(Г) очевидно. Дока вате льство леммы 4.13. а) Вместо машины М можно рассматривать Д-автомат МР Соответствующая ПО-грамматика будет иметь внд ()Г, 1!Г,Е,5), где Г" и В' — соответственно входной и рабочий алфавиты М, Š— символ, записываемый в начале вычисления, и 5 строится следующим образом: (!) если головка может, записав в некоторой ячейке символ А, тотчас же спуститься этажом ниже н записать а (иначе говоря, для некоторых состояний |1, |!', |!" имеются инструкции |!' — А|1, |!- ад"), то в 5 включается окрест- .А ность 1; (В) если головка может, поднявшись из 1 се ячейки, где записано а, в ячейку, где записано А, тотчас же подняться еще на этаж (т.
е. имеются инструкции ад'-«д, А|! — «|!"), то в 5 включается окрест- .Й ность 1; (ш) если головка может, поднявшись на | се ) один этаж из ячейки, где записано а, тотчас же спуститься снова и записать й (т. е. имеются инструкции а|!'- и, д-«й|)"), то в 5 включаются всевозможные окрестности вида , А Г ~ | ж 8 где А — произвольный рабочий символ;(1ч) если головка может, записав в некоторой ячейке а, тотчас же подняться (т. е. имеются инструкции |!' †«а|), а|)- |!«), то в 5 включается окрестность ° а; (ч) если в 5 включены окрестности .А ° А 1 , то включается также се) 1 н 1сх1 Равенство ЕА(6)=ЕА(М) очевидно.
б) По ПО-грамматике 6 =()Г, ЧГ, ), 5) мы построим Д-автомат М, следующим образом. Пусть .А сег — произвольная не одноэлементная окрестность из 5 (й ) 1; символы ', и: означают наличие или от- сутствие пометок ( и ~ соответственно). Сопоставим ей 4й — 1 состояний: 1„..., !А («левые состояния»), Г„..., ГА («правые состояния»), п|и ..., |НА («нижние состояния»), и„..., и», («средние состояния») и инструкции: (1) а,г, -+ и„(2) и, -+ а|!»,..., (2! — 2) и,, — а|!и (2| — ! ) а,г, -+ и„..., (2я — 3) а»,ГА, — и» „(2й — 2) и»; -|-ад!м (Эти инструкции позволяют обходить дерево о «с перерывами»| из крайнего слева висячего узла, где ранее уже записано аь в корень; затем во второй слева висячий узел, причем вием пишется а» и автомат оказывается в состоянии !г., если потом головка попадает когда-нибудь в тот же узел снова и при этом автомат будет в состоянии Г|ь то можно еще раз перейти в корень и оттуда в следующий висячий узел, и т. д.) Если при этом крайний слева висячий узел о несет метку (, то мы включаем в число сопоставляемых также всевозможные инструкции вида !'- а|!ь где !' — левое состояние, сопоставленное произвольному висячему узлу с метко й А произвольной окрестности нз 5; если .край-.: ний справа висячий узел о несетметку ~, то добавляем 147 !) если а имеет вид то а' состоит из окрестностей ч Я .Г ~, Риг"), Е улу,б Рис.
7. 14б Б.ГРАммАтики и мАшины с мАГАзиннои пАмятью ~гл, а всевозможные инструкции вида алга-+г', где г' определяется аналогично 1'. (С помощью этих инструкций начинается, соответственно завершается, обход в с е г о куст а узла дерева из ЕА (6).) Далее, если М вЂ” множество всех тех чисел 1= 1, ..., й, для которых в 5 имеются окрес-ности аь то для каждого (~й( мы сопоставим окрестности о еще две инструкции: ич 1- а,лзь, . аглт,- и;; сверх того, при 1ен ЛГ добавим инструкции 1' — 11пт, и при й ев Лà — инструкции адта -+ г', где 1' и Г' имеют прежний смысл.
(Эти инструкции будут выполняться, когда соответствующие узлы висячие.) Полученную систему инструкций обозначим Р(о). Объединение всех Р(о) будет программой Мь Непосредственно ясно, что множество деревьев, которые может обходить Мь совпадает с Ед (6). Доказательство леммы 4.14. Пусть Π— произвольная ПО.грамматика и О' — ограниченная ПО- грамматика. Равенство Е(6') = Е(6) будет обеспечено, если мы установим между ЕА (6) и Ед (6') взаимно однозначное соответствие со следующим свойством: В В каждому кусту дерева из ЕА (6), имеющему вид, показанный на рис.
7, а), отвечает в соответствующем дереве из Ед (О') поддерево рис. 7, б), где Сь ..., Ср а — некоторые новые символы. Но такое соответствие будет, как легко проверить непосредственно, иметь место, если сопоставить каждой окрестности а грамматики О систему окрестностей и' грамматики О' следующим образом: МАШИНЫ С МАГАЗИННОГ ПАМЯТЬЮ .В ° В ° 8, ! „,„ / ~ Е 8 1 (. А ~гЗ то а' состоит из одной окрестности а 2) Если ° Я а - /~, с>7 ЕД 7В ,г'~, уУ 1- А Еа/-1 (-уЧг ~аг -1 " ~р-! увр (здесь и далее Сел — новые символы). 3) Если ') Из определения Ед(о) ясно, что окрестности вида .В ° В 1 и ~Р 8) можно изъять, добавив в случае яадобности некоторые новые окрестности с более чем двумя висячими вершинами. !49 !48 в-ГРАммАтики и ЯАшины с мАГАзиннои пАмятью !Гл.
з то а' состоит из окрестностей МАШИНЫ С 'МАГАЗИННОН ПАМЯТЬЮ то а' состоит из окрестностей /~ (,9, С„) (р, рг~ (.узр фр l (здссь и далее Ои, и — новые символы). ! 4) Если ° 8 ,а = / ~, риг"), Д /Зр~ то а' состоит из окрестностей прн р=З 5) Если .В а =- Г ~ т,айЛ *у!, А Лр ') Си.
сноску кз стр. !47. ° В ФФ ) Из определения Ьд(б) ясно, что окрестности виде излишни. °,()и Г аг А-l * ~~рт ° з,р, про р >,Х, П ° ПРИ ,О=Я . ! (- узг -) Г~'» " ар вьвр) при р>г Г~'', Г~ аг А ~аз-) ° .Ол при р-а'. ( Д Ю~ .3 3 а и е ч а н и я. 1) Процедуры„примененные при до. казательстве лемм 4.12, а) и 4.! 3, б), устанавливают, как легко убедиться, взаимно однозначное соответствие между множеством деревьев полных выводов ОБ-грамматики и множеством упрощенных деревьев полных вычислений эквивалентной ей МП-машины, и при этом соответствии сохраняются отвечающие деревьям цепочки основных символов. Аналогичный факт верен для процедур лемм 4.13, а), 4.12, б) и 4.14.
2) Пусть для произвольной ОБ-грамматики Г выра. жение ).с(Г) означает множество всевозможных систем составляющих для цепочек языка ! (Г), соответствующих деревьям выводов этих цепочек в Г. Аналогичный смысл придадим обозначению !.С(М), где М вЂ” МП-машина. Тогда доказательства лемм 4.12, а) и 4.!3, б) дают способ для всякой ОБ-грамматики Г построить такую МП-машину М, что !.С(М) = Т.с(Г).
Обратное, очевидно, неверно; если ширина множества !.С(М) не ограничена (т. е. не существует числа, мажорирующего ширину любой системы из !.С(М)), то ни для какой ОБ- грамматики Г равенство !.С(Г) = т'.С(М) невозможно. Но если ширина множества Т.с(М) ограничена и огравнчивающее ее число известно, то ОБ-грамматика Г, удовлетворяющая указанному равенству, может быть построена. Для этого придется несколько усложнить конструкцию пункта а) леммы 4.13, моделируя не пары соседних дуг дерева вычисления, а целые кусты — это ! 5О В-ГРАММАТИКИ И МАШИНЫ С МАГАЗИИНОй 'ПАМЯТЬЮ 1ГЛ. ° МАШИНЫ С МАГАЗИННСЕТ ПАМЯТЬЮ становится возможным ввиду ограниченности числа дуг в них; тогда отпадет надобность в лемме 4.14, т.
е. в изменении топологии дерева. Подробное проведение соответствующих построений предоставляется читателю. Вместе с результатом упражнения -4.28 это позволяет для каждой МП-машины М либо построить ОБ-грамматику Г такую, что Т.с(Г) = .= Т.с(М), либо установить, что такой грамматики нет. 3) Пусть С, — система составляющих цепочки х, отвечающая некоторому дереву вычисления МП-машины М, и С,—.система составляющих той же цепочки, отвечающая соответствующему дереву вывода в Б-грамматике, построенной по М с помощью процедур лемм 4.13, а), 4.14 и 4.!2, б).
Если у — произвольная неточечпая составляющая системы С, (точнее, соответствующая надцепочка цепочки х) и если у = г,гг ... г„где хь гг, ..., х,— составляющие, непосредственно вложенные в у, то все отрезки у = ггхг .. х„гг ...г., ;... и, зг, принадлежат С'„. При этом все неточечные составляющие систе)зы С'„могут быть получены таким способом. Сверх того, метки новых составляющих вполне определяются метками непосредственно содержащих их старых. Естественно возникает вопрос о единственгости дерева вычисления для данной входной цепочки.
По аналогии с понятием однозначной Б-грамматики напрашивается следующее определение: МП-машина М называется однозначной, если для каждой цепочки х ~ !.(М) существует единственное дерево полного хвычисления (или, что то же самое, единственное полное х-вычисление). Машины примеров 1 и 2 на стр. 137 — 138, как легко видеть, однозначны, а машины примера 3 — нет (упражнение 4.29). Что касается понятия однозначного ОБ-я з ы к а, то оно не изменится, если определить его с помощью МП- машины: имеет место Теорема 4.10.
ОБ-язык тогда и только тогда однозначен, когда существует допускающая его однозначная МП-машина. Доказательство немедленно получается из замеча. иня 1) к леммам 4.12, 4.13 и 4.14. В заключение нам остается уделить немного внимания детерминированным МП-машинам — вернее, тем Б- языкам, которые такими машинами допускаются. Ясно, прежде всего, что всякая детерминированная МП-машина однозначна, так что неоднозначные Б-языки не допускаются детерминированными МП-машинами. Но н не все однозначные Б-языкн допускаются ими.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
