Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Будем говорить, что инструкция Ж машины М применима к'ситуации S = (q, х', ах", X', АХ"), если левая часть Ж содержит q и при этом: если Ж — qb-^q', то b = а, если Ж = Bq —? qr, то В = А; если Ж — q—*q'J\, то X' Ф Л; если Ж = q-+ д'П, то Я" Ф А. Будем обозначать через Р{Ж) множество записей всевозможных ситуаций машины М, к которым применима инструкция Ж, и через Ro — множество записей всевозможных ситуаций М, к которым неприменимы никакие инструкции. Как Ro, так и все 7?(Х) являются A-языками, и построение соответствующих А-грамматик очевидно. При этом Т =± [Ro П Т] U U [ЯРП П Г], где объединение берется по всем инструкциям М. Поскольку R0 Л Т= = RoR, достаточно указать способ построения линейной Б-грамматики для каждого из языков ^(Х)П Т.
Ввиду детерминированности машины М к- каждой данной ситуации может быть применима только одна инструкция. Поэтому, если и у е R, то ситуа-
ция S' с записью у тогда и только тогда не является непосредственно достижимой из ситуации S с записью х, когда S' не получается из S применением инструкции Ж. А отсюда по лемме 8.6 вытекает, что достаточно построить Э-машину М, удовлетворяющую условию этой леммы и такую, что для цепочек х^Н(Ж) и y^R тогда и ' только тогда существует [х, г/]-вычисление
272 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
машины М, когда ситуация с записью у получается из ситуации с записью х применением инструкции Ж. При этом возможны пять случаей, соответствующих возможным типам инструкций Ж. Мы рассмотрим случай Ж = Ад^-д\ предоставив остальные (вполне аналогичные) читателю. Машина М будет в этом случае, имея на входной ленте цепочку qx'Slx"X'BSlAX" (где в силу выбора типа инструкции А е W, В е W U {#}), работать следующим образом. Сначала она читает q и пишет на рабочей ленте q'. Затем до прочтения В просто переписывает входные символы на рабочую ленту. Прочтя В, она пишет на рабочей ленте V. (Подчеркнем, что это делается «недетерминированным образом»: машина может записать V после прочтения любого символа из ^ U {ф}, но если в следующей входной ячейке не окажется V, то произойдет «поломка».) Затем, прочтя на входной ленте V, она пишет на рабочей В. Далее, прочтя А, пишет на рабочей ленте символ, который на входной нёросредственно следует за А (опять «недетерминированным образом»: символ пишется наугад, н в случае несовпадения его со следующим входным символом машина ломается). Далее, читая К", машина после прочтения каждого символа пишет на рабочей ленте (как описано выше) тот символ, который на входной следует за прочитанным, а прочтя последний символ из X", переходит в специальное состояние q (если она, «не угадав», что данный символ последний, вместо перехода в q запишет что-нибудь на рабочей ленте, то на следующем шаге будет прочтен граничный маркер*) и произойдет поломка). После этого читается граничный маркер и наступает заключительное состояние. Выполнение для М условия леммы 8.6 очевидно. Итак, лемма 8.5 доказана.
Пусть теперь М — произвольная Э-машина. Обозначим через R(M) множество записей всевозможных ситуаций М, через R\{M) — множество записей всевозможных начальных ситуаций М и через Rz(M)—множество записей всевозможных ситуаций М, имеющих вид (qf, 4М, ф, А, ф у), где qf — заключительное состоя-
*) Мы можем, разумеется, считать граничные маркеры М отличными от #.
ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРДММАТИКАМИ
273
ние М. Положим, кроме того,
F (М) = И (М) П [Я, (М) (R (М)У R2 (М)];
иначе говоря, F(M) —это множество протоколов тех вычислений машины'М, с помощью которых значения аргумента вычисляемой ею функции / переводятся в значения самой /. Поскольку множество CZF(M) (обозначение Z введено на стр. 268) представимо в виде
CZF(М) = II'(М) U Cz [/?, (М)(R (М)У R2(М)],
a i?i(M) и R2(M) суть A-языки, причем А-грамматики для них строятся очевидным образом, из только что доказанной леммы непосредственно вытекает следующая Лемма 8.7. Для произвольной ДЭ-машины М множество CZF{M) есть линейный язык, и для всякой ДЭ-машины М можно построить линейную ОЪ-грам-матику, порождающую CZF(M).
Нам понадобится еще следующая простая конструкция. Пусть G = (gi, •••. gn, • • •} — счетное множество символов и а, b — произвольные символы. Для каждой цепочки ® = gil---gis положим Я (со ) = bal+ilb...
... bal+tsb; кроме того, положим Я (Л) =bab. Для каждого языка L в произвольном словаре, содержащемся в G, положим K(L) — {Я(со) |со е L}. Мы можем допустить, что для каждой рассматриваемой нами Э-машины М соответствующий словарь Z содержится в G, и рассмотреть язык Н(М) == K(F(M)). Имеет место
Лемма 8.8. Для произвольного словаря V, содержащего а и Ь, и для произвольной ДЭ-машины М множество CVH(M) есть линейный язык, и для всякого словаря V з {а, Ь} и всякой ДЭ-машины М можно построить линейную ОЪ-грамматику, порождающую CVH(M).
Доказательство. Имеем CVH(M) =CV(K(Z))*U U ((Я(2))* — Н(М)). Поскольку X(Z) конечно, для первого члена объединения по теореме 5.4 строится ОА-грамматика; второй член порождается линейной ОБ-грамматикой, схема которой получается из схемы соответствующей грамматики для CZF(M) заменой в каждом правиле каждого вхождения каждого основного символа gi вхождением цепочки bal+ib.
