Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Доказательство леммы 4.13. а) Вместо машины М можно рассматривать Д-автомат М,. Соответствующая ПО-грамматика будет иметь вид (К, W,E,S), где V и IF — соответственно входной и рабочий алфавиты М, Е — символ, записываемый в начале вычисления, и S строится следующим образом: (i) если головка может, записав в некоторой ячейке символ А, тотчас же спуститься этажом ниже и записать а (иначе говоря, для некоторых состояний q, q', q" имеются инструкции q' -^-Aq, q->aq"), то в S вкл<очается окрест-
. А
ность I ; (ii) если головка может, поднявшись из
• •
L ос
ячейки, где записано а, в ячейку, где записано А, тотчас же подняться еще на этаж (т. е. имеются инструкции aq'-^-q, Aq^-q"), то в S включается окрест-
. А
ность I ; (iii) если головка может, поднявшись на
один этаж из ячейки, где записано а, тотчас же спуститься снова и записать р (т. е. имеются инструкции aq'->q, q-+$q"), то в S включаются всевозможные окрестности вида
. А
/ \ ’
а Р
где А — произвольный рабочий символ; (iv) если головка может, записав в некоторой ячейке а, тотчас же подняться (т. е. имеются инструкции q'-+aq, aq->q"), то
МАШИНЫ С МАГАЗИННОЙ" ПАМЯТЬЮ
145
в S включается окрестность • a; (v) если в S включены окрестности
. Л # А • А
I и | , то включается также I ,
• • •
L ос ос J L сх j
Равенство L&(G) = Ьл(М) очевидно,
б) По ПО-грамматике G = (K, W, I, S) мы построим Д-автомат М( следующим образом. Пусть
О.
• • • • » •
, ОС, ОСр QCfr
— произвольная не одноэлементная окрестность из S символы : и : означают наличие или от-
сутствие пометок [_ и J соответственно). Сопоставим
ей 4k — 1 состояний: lx.........Ik («левые состояния»),
гх, ..., rk («правые состояния»), т1.........тк («нижние
состояния»), «1, ..., i («средние состояния») и инструкции: (1)<Х|Г, —? «j, (2)Ы[->-а2/2..(2i — 2) ыг_,->-аг/,,
(2i'—l) ..., (2k —3)ctft-,rft_i {2k—2)«*_,->
-»-агА- (Эти инструкции позволяют обходить дерево о «с перерывами»: из крайнего слева висячего узла, где ранее уже записано ai, в корень; затем во второй слева висячий узел, причем в нем пишется аг и автомат оказывается в состоянии /2; если потом головка попадает когда-нибудь в тот же узел снова и при этом автомат будет в состоянии Гг, то можно еще раз перейти в корень и оттуда в следующий висячий узел, и т.. д.) Если при этом крайний слева висячий узел о несет метку [_, то мы включаем в число сопоставляемых также всевозможные инструкции вида l'-*aih, где I' — левое состояние, сопоставленное произвольному висячему узлу с меткой А произвольной окрестности из S; если.край-, ний справа висячий узел о несет метку J, то добавляем
146 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
всевозможные инструкции вида <*лг&—где г' определяется аналогично (С помощью этих инструкций начинается, соответственно завершается, обход всего куста узла дерева из L&(G).) Далее, если N — множество всех тех чисел г = 1, ..., k, для которых в S имеются окрестности >аи то для каждого i е N мы сопоставим окрестности о еще две инструкции: ы,-1—*-аг/пг, , аi/Wiсверх того, при /eiV добавим инструкции I'-*hrriy и при AeJV--инструкции аитк-*г', где I' и г' имеют прежний смысл. (Эти инструкции будут выполняться, когда соответствующие узлы висячие.) Полученную систему инструкций обозначим Р(о). Объединение всех Р(о) будет программой Му. Непосредственно ясно, что множество деревьев, которые может обходить Ми совпадает с /,д (G).
Доказательство леммы 4.14. Пусть G — произвольная ПО-грамматика и G' — ограниченная ПО--грамматика. Равенство L(G') — L(G) будет обеспечено, если мы установим между L&(G) и L^(G') взаимно однозначное соответствие" со следующим свойством:
каждому кусту дерева из ?д (G), имеющему вид, показанный на рис. 7, а), отвечает в соответствующем дереве из L& (G') поддерево рис. 7,6), где Су, ..., Cv-2 — некоторые новые символы.
Но такое соответствие будет, как легко проверить непосредственно, иметь место, если сопоставить каждой окрестности а грамматики G систему окрестностей а' грамматики G' следующим образом:
я
В
6)
Рис. 7.
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
147
1) если а имеет вид
. В j
] или S Ч\
L /3 J & @2 1
то а' состоит из одной окрестности а.
2) Если
. В
а " ./.\ . °*3.
LA, /SpJ
то а' состоит из окрестностей
/•< , /•<:' /<агг
L/3/ Ca,J 1_Д? Са2 J L/3оЧ fip-1
(здесь и далее Саг- — новые символы).
3) Если
В ,/\ ,ргг’), >-& Рр
*) Из определения L& (О) ясно, что окрестности вида
.5 •В
I а |
ii. h
можно изъять, добавив в случае надобности некоторые новые окрестности с более чем двумя висячими вершинами.
148 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
то а' состоит из окрестностей
• В • ^ГУ 1 • СП П—1
/\ , У\ , , /\,р
• • • • « •
\~fit Cat-1 ^а2 J
(зд^сь и далее Da, е;— новые символы).
4) Если
./»П
А 4-)
то а' состоит из окрестностей
• • » • \ >•••»..
^ Lfy CasJ . Lfbp_j ftp J
• 4,- .Дв„
v Ч °>/?/ I o,/9,
• ' \ при p=3 и l при p -2.
LA? A>J L fbz J
5) Если
a= /\ ,p>2*V,
• » • • • ' '
A /j0
*) См. сноску на стр. 147. .
**) Из определения LA (G) ясно, что окрестности вида |
