Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
найдется такое «о> что q *= nod. Имеем тогда *=»
13б В-№АмМатикИ й Машины с магазинной памятью [гл. а
= Qf+d+e+n,dbh+d+m+nadcS+q = as+cbs+<,cs+<,t и для некото_
рого дерева вывода Т цепочки as+qbs+qcs+q в Г одна из составляющих соответствующей системы С будет иметь вид aq+gbq+h. Теперь мы можем, рассматривая цепочку a.s+<,bscs и рассуждая так же, как раньше (с точностью до зеркальной симметрии), найти такое дерево вывода Т' той же цепочки as+qbs+4cs+q в Г, что одна из составляющих соответствующей системы С' будет иметь вид bq+h с‘1+s. Поскольку h, h'^.s<q, составляющие aq+ebq+h и bq+h'cq+g’ пересекаются; поэтому системы С и С', а значит и деревья Т и Т', различны.
Пример 2. Пусть Lx = {хЬХЬу \х, у е {аь а2}+}, L2 = \xbyby\x, у е {аь а2}+}, L = Ц U L2. Построение Б-грамматики, порождающей L, не представляет труда. Если Г — произвольная Б-грамматика, порождающая L, то, определив s и q, как в примере 1, рассматривая цепочки а\Ьа\Ьа\+ч и а\+чЬа\Ьа\ и рассуждая в точности так же, как в предыдущем примере, мы найдем два различных дерева вывода цепочки as\+qbas\+qbasi+q.
Пример 3. Пусть L\ = {anbkanbm\k, m, п= 1, 2,...}, L2= {ahbnambn\k, m, n— 1, 2, ...}, L = L, U L2 и Г — Б-грамматика, порождающая L. Определим s и q, как в примере 1; рассмотрев цепочку asbs<Pbs+<t и рассуждая, как в предыдущих примерах, мы без труда найдем для ?цепочки / t = as+9&sas+9&s+9 такое дерево вывода, что одна из составляющих соответствующей системы будет иметь вид as^bsah+4. Применим к цепочке I теорему 4.7, положив х = as+«, у — bsy z = as+c>bs+i. Аналогично предыдущему легко видеть, что соответствующая цепочка и •или w не содержит вхождений а. Если при этом она содержится в «правой 6-зоне», то цепочка t имеет две частично пересекающиеся составляющие и, следовательно, два различных дерева вывода. Остается случай, когда и или до, так же как и v, содержится в «левой -6-зоне». Тогда цепочка ux2v или vz\W будет иметь вид Ь1, О < / s, и при подходящем п0 цепочка uni>+'x2vna+1 или yrt»+l z1sy/I“+I совпадет с цепочкой Ь1+ч. В силу замечания к теореме 4.7 отрезок цепочки tna = as+qbs+qas+qbs+4, .полученный из отрезка ag+ib*ah+ci цепочки t заменой Ь1 на б'+в, будет составляющей цепочки tn<l в некоторой
МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ
137
системе, отвечающей какому-то дереву вывода tna в Г. Таким образом, некоторое дерево вывода Т цепочки t„, дает составляющую А, начинающуюся левее кон-ц а «левой a-зоны» и заканчивающуюся «в правой а-зоне».
Теперь мы можем, рассуждая симметрично, показать, что либо цепочка t' = as+ibs+liasbs+ti имеет два различных дерева вывода, либо некоторое дерево вывода Т той же цепочки /Я| дает составлящую А', начинающуюся в «левой 6-зоне» и заканчивающуюся правее нача-л а «правой 6-зоны». Поскольку .А и А' частично пересекаются, Т Ф Т'.
Дальнейшие примеры — в упражнениях 4.16 и 4.20. (См. также упражнение 5.17,6).)
§ 4.5. Машины с магазинной памятью
Подобно тому как классу произвольных грамматик соответствует класс произвольных машин Тьюринга и классу НС-грамматик — класс машин без растяжения, для Б-грамматик также имеется отвечающий им в том же смысле тип машин Тьюринга — так называемые машины с магазинной памятью.
Э-машина называется машиной с магазинной памятью (МП-м а ш и н о й), если ее программа содержит только инструкции типов (i) — (iii) (стр. 42). Таким образом, рабочая головка МП-машины всегда находится в крайней справа ячейке; создав однажды рабочую ячейку, головка может уйти от нее (если не уничтожит efe тут же) только вправо и получает возможность «заглянуть» в нее снова лишь в тот момент, когда уничтожает ее. Чем раньше ячейка создана, тем позже она будет уничтожена и тем самым «использована»; это напоминает принцип работы магазина в автоматическом оружии, чем и объясняется название «машина с магазинной памятью».
Пример 1. Пусть М — машина с программой {?! qi^Aq2, q2a->qi, qib-*q3, Aq3-+q4, qAb-^q3,
<74ф->.<70} и единственным заключительным состоянием q0. Легко видеть, что L (М) = {anbn\п — 1, 2, ...}.
Пример 2. Язык {хк \х е {а, ..., а„}*} допускается машиной q программой {<?j ф->
138 Б-ГРАММАТИКИ И МАШИНЫ С МАГАЗИННОЙ ПАМЯТЬЮ [ГЛ. 4
<h~*Aiqt+u <h+iai-*? Qi> Qiai~>(li+n+u Aiqi+n+i^* q2n+2, Фп+га*-><7<+«+i. q2n+2$-*qo} (*' = 1. •••, «) и единственным заключительным состоянием q0.
Пример 3. Язык примера 8 из § 1.3 допускается машиной с программой {(1) q{ -*Eq2, (2) q2 # -> q2, (3) q2—>
—*? Aq3, (4)q3a-+q2, (5)q2b->q4, (6) Aq^ q2, (7) q4-*Bq5, '] (8) q5b->q7, (9) q7a->q6, (10) Bq6->q4, (11) q2a-+q6, (12) ; Eq^-^qо) и единственным заключительным состоянием^.
Дальнейшие примеры МП-машин см. в упражнении 4.22. Примеры детерминированных МП-машин см. 1 на стр. 152 и в упражнении 4.31.
Назовем МП-машину нормальной, если она имеет единственное заключительное состояние и каждое ее полное вычисление начинается записью на рабочей ленте некоторого символа Е, который уничтожается лишь на последнем шаге вычисления.
Лемма 4.11. Для любой .МП-машины можно построить эквивалентную ей нормальную МП-машину.
Доказательство. Достаточно добавить к множеству состояний данной машины два новых состояния q't и q0, объявив их соответственно начальным и заключительным вместо прежних, к рабочему алфавиту — новый символ Е и к программе — новые инструкции q[ -> Eqx и qfE -> qQ для каждого qf е Q0 (qi — прежнее начальное состояние, Qo — множество ^режних заключительных состояний).
