Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Чтобы построить М3, заметим, что следующие операции можно производить, выполняя перед каждым шагом вида (iii) шаг вида (п): а) постановку метки в некоторой ячейке (непомеченная ячейка уничтожается, и на ее месте создается помеченная); б) стирание метки (аналогично) ; в) сдвиг символа 0 на одну ячейку влево (ячейка, содержащая 0, уничтожается, на ее месте создается ячейка, содержащая символ, стоящий в соседней ячейке слева; затем головка сдвигается — шагом вида (iv) — в соседнюю слева ячейку, эта ячейка уничтожается и взамен создается новая, содержащая 0); г) сдвиг символа 0 на одну ячейку вправо (аналогично).
После сделанного замечания ясно, что М3 может работать так: (1) Всякий раз, когда М2 делает шаг вида (И), уничтожая некоторую ячейку, М3 сначала уничтожает ту же ячейку, затем создает на ее месте новую, содержащую 0, ставит в соседней слева ячейке метку, сдвигает символ 0 влево до тех пор, пока он не окажется рядом с ячейкой, уже занятой таким же символом или символом #, и, наконец, сдвигает голоьку вправо до помеченной ячейки и стирает там метку. (2) Когда М2 делает шаг вида (iii), М3 помечает обозреваемую ячейку, сдвигает головку влево до первой ячейки, занятой нулем (такая обязательно найдется!), двигает этот нуль вправо, пока он не окажется непосредственно справа от помеченной ячейки, затем (стерев предварительно метку) уничтожает его и создает на его месте нужный символ. (3) Шаги машины М2, имеющие вид (iv) и (v), воспроизводятся машиной М3 без изменения. (Что касается шагов вида (i), то можно, очевидно, считать, что М2 их не делает.) Таким образом, Мг отличается от М2 тем, что,
НЕУКОРАЧИВАЮЩИЕ ГРАММАТИКИ
87
уничтожая какую-либо ячейку, она создает взамен в левом конце ленты другую, занятую «пустым символом», а новую ячейку может создать только за счет одной из «пустых». М3 способна имитировать М2, потому что в процессе вычисления рабочая лента М2 никогда не содержит больше ячеек, чем их было вначале.
Теперь построим по М3 грамматику Tj со схемой так, как в доказательстве пункта а) теоремы 1.4 строилась по М2 грамматика Г. В силу свойства (у) машины М3 в любом полном выводе грамматики Г) за каждым применением правила вида bq^->qa следует применение правила вида qa—>eqy, поэтому мы можем заменить в Г! каждое правило вида 6<7р—><7а совокупностью всевозможных правил вида 6q^->eqy, где qa—> и полученная грамматика — обозначим ее Г2 — будет эквивалентна IY Остается заменить в Г2 каждое правило вида бq^-*eqy правилами 6q^ —>
Sleepy 8^веру> еРщу~>е<1у’ каждое правило вида <7рб->
* правилами q^fi ^бр^> ^бр^ ^ ^бр-^бр» ^бр-^бр ^ ->бЯвр, 6#в|3—>6<7р, и каждое правило вида 6<7р—><7р6 — правилами б^^бМвр, бМвр^//врМвр, //врМбр->А^врб, ^брб-><7р6, гДе ^веру> °бр. ^бр. Л4вр, Л^бр— новые символы, которые мы отнесем к вспомогательному словарю. Полученная грамматика — обозначим ее Г3 — является, очевидно, НС-грамматикой, и легко убедиться, что она эквивалентна Г2; действительно, каждое исключенное из схемы Г2 правило заменимо в выводе соответствующей системой правил Г3, и правила каждой такой системы могут применяться в полном выводе грамматики Г3 только подряд, так что вместо, них можно применить правило из Г2. Итак, L(Fi) — L(M).
Теорема 3.2, и тем самым теорема 3.1, доказана. '
Из теоремы 3.1 вытекает
Следствие. Класс языков, порождаемых неукора-чивающими грамматиками, совпадает с 9? (НС).
Теоремы 3.1 и 3.2 легко усилить следующим образом. Назовем грамматику Г, соответственно Э-машину М, грамматикой (Э-машиной) с ограниченным растяжением, если существует такое число с, что сп(5дг(п)^ сп). Тогда имеет место
88
ГРАММАТИКИ СОСТАВЛЯЮЩИХ
[ГЛ. 3
Теорема 3.2'. а) Для всякой грамматики с ограниченным растяжением можно построить эквивалентную ей Э-машину без растяжения.
б) Для всякой 3-машины с ограниченным растяжением можно построить эквивалентную ей НС-грамматику.
Утверждение а) вытекает из теоремы о сжатии выводов и пункта а) теоремы 3.2; утверждение б) — из теоремы о сжатии вычислений и пункта б) теоремы 3.2.
Из теоремы 3.2' вытекает в свою очередь
Теорема 3.1'. Для всякой грамматики с ограниченным растяжением можно построить эквивалентную ей НС-грамматику.
Следствие. Пусть {с-п} означает класс всевозможных линейных функций и п — функцию f(n) = n. Тогда = = НС).
Назовем грамматику почти неукорачивающей, если все ее незаключительные правила неукорачивающие. Справедливо следующее утверждение:
Теорема 3.3. Для всякой почти неукорачивающей грамматики можно построить эквивалентную ей НС-грамматику.
Доказательство. Пусть Г = < V, W7, /, /?") — почти неукорачивающая грамматика и xeL(F). Ввиду леммы
1.1 существует полный вывод D = (ш0....сот, .. ., ©р)
в Г такой, что сор = х и на всех шагах до m— 1-го включительно применяются неукорачивающие правила, а на всех последующих — заключительные. Поскольку при каждом применении заключительного правила появляется хотя бы одно вхождение символа, сохраняющееся до конца, имеем р — поэтому для любого
i = m, те+1, ..., р будет \х\^\ац\ — \х\-g, где g = шах (|ср|—-М), так чт0 l“i| < (ё + !) ‘ Iх!'. в т0
