Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
и Х'Х" = фХ- для подходящих x^V,*, XeF. Записью правильной ситуации (qa, х', х", X', X") бу-
*) Если бы такого числа не нашлось, то R имел бы конечное дополнение и, значит, был бы НС-языком.
ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ
269
дем называть цепочку qax'Wх"X'VX". Для произвольного вычисления С = (S0, S1, S„) машины М будем на-
зывать его протоколом цепочку я(С) = j(S0) H^i). • • где $(Si) — запись ситуации 5г-. Множество всех протоколов машины М будем обозначать через П(М), дополнение П(М) до Z* — через 1Г(М).
Лемма 8.5. Для произвольной JXB-машины М множество П' (М) есть линейный язык, и для всякой ДЭ-машины М можно построить линейную ОЪ-грамматику, порождающую П '(М).
Предварительно докажем другую лемму.
Лемма 8.6. Пусть Э-машина М имеет инструкции только типов (i) и (iii) и для любой ее непустой входной цепочки х существует самое большее одно [х, у]-вычис-ление, причем это вычисление происходит в такой последовательности: сначала читается символ ф на входной ленте, затем (если \х\ ^ 1)—первый символ входной цепочки х, затем создается рабочая ячейка, и далее шаги типов (i) и (iii) чередуются через один, пока не будет прочитан последний символ цепочки х; после этого машина либо сразу останавливается, либо, прежде чем остановиться, делает еще один или два шага типа (iii). Пусть, кроме того, входной и рабочий алфавиты машины М представлены, соответственно в виде V= V' U W — W'l)W, где V' П V = W'[) W = 0. Для произвольных двух языков Li s V'V*, L2 s W'W* обозначим через LM(Li,L2) множество всевозможных цепочек ху таких, что х е Lu y^L2 и не существует [х, у]-вычисления машины М. Тогда для любых двух А-грамматик Г) и Гг таких, что L(Ti)s V'9*, L(T2)s W'W*, можно построить линейную ОЪ-грамматику, порождающую LM(L(Ti),
ЧГ2)).
Доказательство леммы 8.6. Поскольку для данной входной цепочки х самое большее при одном значении у, которое мы будем обозначать у(х), может существовать [х, у]-вычисление, ясно, что цепочка ху, где xeL(ri), y<=L(T2), принадлежит LM(L(Ti), L(r2)) тогда и только тогда, когда выполняется одно из четырех условий: (а) цепочки у(х) не существует; (б) \у\< <i\y(x) |; (в) Ы>Ы*)|; (г) существует такое
i= 1, ..., min(|«/|, |г/(л-)|), что t'-e слева символы цепочек у и у(х) различны. Дизъюнкция этих условий
270 НЕРАЗРЕШИМЫЕ АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ [ГЛ. 8
равносильна дизъюнкции (б') V (в') V (г'), где (б') = = (a)V(6), (в') = (а) V (в), (г') = (а) V (г). Иначе говоря, LM(L(T\), L(F2))= L'\JL"[jL"', где L', L", L'" — множества цепочек xy, xeL(ri), удовлетво-
ряющих (б'), (в') и (г') соответственно. Поэтому ввиду эффективной замкнутости класса линейных языков относительно объединения (стр. 170) нам достаточно указать способ построения линейных ОБ-грамматик для языков L', L" и L"'. В силу теорем 5.2 и 5.8 это равносильно построению однодорожечных МП-машин, допускающих указанные языки, по конечным автоматам М\ и М2, допускающим L(Ti) и /-(Гг) соответственно.
Машина М' для L' строится следующим образом: если на ее входной ленте записана цепочка ху, где x^V'9*, y^W'ffi*, то сначала она работает на входной ленте, как Ми а на рабочей — как М; прочтя х, она начинает работать на входной ленте, как М2, а на рабочей после каждого «входного» шага уничтожает одну ячейку; есАда после прочтения ху еще останутся рабочие ячейки, то машина уничтожает и их, после чего переходит в заключительное состояние; в противном случае после прочтения ху машина «ломается».
Машина М" для L" строится аналогично.
Машина М'" для L'" работает так. Имея на входной ленте ху, где х^ V'V*, г/е W'ffl*, она сначала работает так же, как М', но потом, не дойдя до конца х, переходит «в другой режим»: на входной ленте продолжает работать так же, а на рабочей не делает ничего. При этом она «запоминает» тот символ Ь, который должна была бы записать на рабочей ленте машина М (или М') сразу после прочтения содержимого той входной ячейки, которую М"' обозревает к началу работы в новом режиме; пусть к этому времени рабочая лента состоит из i ячеек (возможно, i = 0) *). Прочтя х, машина М'" снова начинает работать так же, как работала с этого момента М', пока не уничтожит всю рабочую ленту. Если к этому моменту входная цепочка будет прочитана целиком, машина ломается. В противном случае входная головка будет обозревать в данный момент i -f- 1-й слева символ цепочки у, и очередной шаг
*) Разумеется, числа i машина «знать» не может.
ПРОБЛЕМЫ, СВЯЗАННЫЕ С Б-ГРАММАТИКАМИ
271
будет состоять в следующем: как и на предыдущих шагах, машина имитирует работу М2, но одновременно проверяет, совпадает ли обозреваемый входной символ с запомненным ранее символом Ь\ если да — она ломается; если нет — продолжает работать просто как М2, и если у окажется «М2-допущенной», переходит в заключительное состояние.
Доказательство леммы 8.5. Пусть R — множество записей всевозможных ситуаций данной ДЭ-машины М. Ясно, что R есть Л-язык; соответствующая А-грамматика строится без всякого труда. Обозначим через Т множество всевозможных цепочек вида ху, где х, у ^ R и ситуация с записью у не является непосредственно достижимой из ситуации с записью х. Ввиду очевидного равенства П'(М) = R*TR* U CZR+, теоремы 5.4 и замечания на стр. 170 нам достаточно построить линейную ОБ-грамматику, порождающую Т.
