Гладкий - Формальные грамматики и языки - 1973 (947381), страница 17
Текст из файла (страница 17)
В «верхнем этаже» машина Мг будет работать, как М на входной ГРкммьтики состьвляюших [ГЛ. 3 НЕУКОРАЧИВАЮШИЕ ГРАММАТИКИ $ хм зт ленте, а в «нижнем», как М на рабочей; по окончании имитации работы М (рабочая) лента уничтожается. Далее построим машину Мь, обладающую следующими свойствами: (а) рабочий алфавит М, получается из рабочего алфавита Мь добавлением одного символа О («пустого символа»); (р) как и в Мь в М, при хан Р» из ситуации (д', Л, ~ ф, Л, 4~ х) тогда и только тогда достижима ситуация (д", Л, Щ, Л, Чр), когда к~Т.(М); (у) в любом вычислении машины Мь каждому шагу, на котором выполняется инструкция вида (ГВ), предшествует шаг, реализующий инструкцию вида (В).
Чтобы построить М,, заметим, что следующие операции можно производить, выполняя перед каждым шагом вида (Ш) шаг вида (й): а) постановку метки в некоторой ячейке (непомеченная ячейка уничтожается, и на ее месте создается помеченная); б) стирание метки (аналогично); в) сдвиг символа О на одну ячейку влево (ячейка, содержащая О, уничтожается, на ее месте создается ячейка, содержащая символ, стоящий в соседней ячейке слева; затем головка сдвигается — шагом вида (!у)— в соседнюю слева ячейку, эта ячейка уничтожается и взамен создается новая, содержащая О); г) сдвиг символа О на одну ячейку вправо (аналогично).
После сделанного замечания ясно, что Мь может работать так: (1) Всякий раз, когда М, делает шаг вида (й), уничтожая некоторую ячейку, М, сначала уничтожает ту же ячейку, затем создает на ее месте новую, содержащую О, ставит в соседней слева ячейке метку, сдвигает символ О влево до тех пор, пока он не окажется рядом с ячейкой, уже занятой таким же символом или символом чР, и, наконец, сдвигает головку вправо до помеченной ячейки и стирает там метку.
(2) Когда МР делает шаг вида (ш), М, помечает обозреваемую ячейку, сдвигает головку влево до первой ячейки, занятой нулем (такая обязательно найдется!), двигает этот нуль вправо, пока он не окажется непосредственно справа от помеченной ячейки, затем (стерев предварительно метку) уничтожает его н создает на его месте нужный символ. (3) Шаги машины Мь имеющие вид (!у) и (у), воспроизводятся машиной Мь без изменения. (Что касается шагов вида (1), то можно, очевидно, считать, что М, их не делает.) Таким образом, Мь отличается от Мз тем, что, уничтожая какую-либо ячейку, она создает взамен в левом конце ленты другую, занятую «пустым символом», а новую ячейку может создать только за счет одной из «пустых». Мь способна имитировать Мм потому что в процессе вычисления рабочая лента М» никогда не содержит больше ячеек, чем их было вначале.
Теперь построим по М, грамматику Г, со схемой Н, так, как в доказательстве пункта а) теоремы !.4 строилась по М, грамматика Г. В силу свойства (у) машины Мь в любом полном выводе грамматики Г, за каждым применением правила вида Ьв -+в, следует применение правила вида в,-+ест; поэтому мы можем заменить в Г1 каждое правило вида Ьв„- в, совокупностью всевозможных правил вида Ьв -+ест, где в,— -» ав„е= Нь и полученная грамматика — обозначим ее Г, — будет эквивалентна ГР Остается заменить в Г» каждое правило вида Ьв„-»ев правилами Ьь) — »ЬРь, ЬРь«ьт-»ЕРь«зт, ЕРь,з -+ад„, каждое правило вида д Ь-+ -»Ьда — правилами д Ь- 6ьаб 6ьаб-+6ьЬНьз 6ьЗНьа — » -«ЬНь, ЬНь -+Ьдз, и каждое правило вида Ьд„-+д Ь— правилами Ьдз-+ ЬМьь ЬМьь-+ Л1ььМь ЛГььМьз — Л ььб, ЛГььб — +даб, где Рь»ат, 6ьь Ньа Мьа Лага — новые символы, которые мы отнесем к вспомогательному словарю.
Полученная грамматика — обозначим ее Г— является, очевидно, НС-грамматикой, и легко убедиться, что она эквивалентна Гз, действительно, каждое исключенное из схемы Гь правило заменимо в выводе соответствующей системой правил Г„и правила каждой такой системы могут ' применяться в полном выводе грамматики Г, только подряд, так что вместо.
них можно применить правило из Г,. Итак, б(Г,)= А,(М). Теорема 3.2, и тем самым теорема 3.1, доказана. Из теоремы 3.1 вытекает Следствие. Класс языков, порождаемых неукорачиваюьиими грамматиками, совпадает с 2'(НС), Теоремы 3.1 и 3.2 легко усилить следующим образом. Назовем грамматику Г, соответственно Э-машину М, грамматикой (Э-м а ш и н о й) с ограниченным р а с т я ж е н и е м, если существует такое число с, что 5г(п) «" сп(ЗМ(п) ( сп). Тогда имеет место СЛОЖНОСТЬ ВЫВОДА 89 % З.а] ГРАММАТИКИ СОСТАВЛЯЮШИХ (Гл.
а 88 Теорем а 3.2'. а) Для всякой грамматики с ограниченным растяжением можно построить эквивалентную ей Э-машину бгз растяжения. б) Для всякой Э-машинь( с ограниченным растяжением можно построить эквивалентную ей НС-грамматику. Утверждение а) вытекает из теоремы о сжатии выводов и пункта а) теоремы 3.2; утверждение б) — из теоремы о сжатии вычислений и пункта б) теоремы 3.2. Из теоремы 3.2' вытекает в свою очередь Теорема 3.1'.
Для всякой грамматики с ограниченным растяжением можно построить эквивалентную ей НС-грамматику. Следствие. Пусть (с п) означает класс всевозможных линейных функций и и — функцию !(и) = п, Тогда Ы'(с л( = 2'л = 'Г (НС). Назовем грамматику почти неукорачивающе, если все ее незаключительные правила неукорачивающие. Справедливо следующее утверждение: Т ео р е м а 3.3. Для всякой почти неукорачивающей грамматики можно построить эквивалентную гй НС- грамматику.
Дока з а тел ьста о. Пусть Г = ()т, )а, К)т) — почти неукорачивающая грамматика и х ~ Е(Г). Ввиду леммы 1.1 существует полный вывод ь! = (озо, ..., ю„, ..., юр) в Г такой, что сор — — х и на всех шагах до т — 1-го включительно применяются неукорачивающие правила, а на всех последующих — заключительные. Поскольку при каждом применении заключительного правила появляется хотя бы одно вхождение символа, сохраняющееся до конца, имеем р — т ((х(; поэтому для любого 1= т, т+1, ..., р будет (х!)(со(( — !х! й, где й = шах (1(р) — (ф(), так что )со,) «= (д+ 1) (х); в то еаь я же время при 1 < 1( т имеем (ю;) <)со (. Следовательно, и(ах 1ю(1~((у+1)(х1,откуда 5г(и) =(и+1)п.
о<(<л Остается применить теорему 3.1'. Заметим, что грамматики примеров 1О и 11 из 9 1.3 неукорачнвающие, а грамматика примера 13 почти неукорачнвающая. Поэтому соответствующие языки явля- ются НС-языками. Дальнейшие примеры см. в упражнениях 3.6 н 3.19. В заключение параграфа рассмотрим вопрос о свойствах замкнутости класса Ы'(НС). Т е о р е м а 3.4. Класс .Т(НС) эффективно замкнут относительно операций объединения, пересечения, умножения, усеченной итерации и подстановки. Д о к а з а т е л ь с т в о.
Просмотр доказательства теоремы !.1 показывает, что если Г', Г", à — НС-грамматики, то соответствующие грамматики, порождающие языки Е(Г') () Т (Г") и Ь(Г')1.(Гн), будут также НС- грамматиками, грамматика, порождающая язык Е(Г') П П Ь(Га), будет почти неукорачивающей, а грамматика Г', порождающая (Ь(Г))', удовлетворяет условию Зг+(и) ( п + 2 ( Зп, Доказательство для подстановки предоставляется читателю (оно также не отличается от доказательства для произвольных грамматик). 3 а м е ч а н и я. 1) По поводу операций левого и правого деления см. упражнение 3.9. 2) Вопрос о замкнутости класса 2'(НС) относительно вычитания и взятия дополнения остается открытым.
9 3.3. Сложность вывода в неукорачивающих грамматиках и НС-грамматнках Начнем со следующего очевидного, но весьма важного замечания. Поскольку для любой неукорачивающей грамматики Г имеет место Яг(п) ( и, из леммы 2,! следует, что каждый НС-язык рекурсивен. Сверх того, в силу замечания на стр. 60 существует единый (и достаточно простой) алгоритм, позволяющий по любой неукорачивающей грамматике Г и любой цепочке х в основном словаре этой грамматики распознать, выводима ли х в Г из начального символа *).
Более того, все НС-языки не только рекурсивны, но и примитивно рекурснвны (упражнение 2.16); при этом во исех имеющихся классификациях примитивно рекурсивных языков — или, что то же самое, предикатов — по сложности вычисления (см., например, (Гт(!СЫе 1963)) ') Это верно на самом леле н Аля любой цепочка в полном словаре Г.
гьлммлтики сОсТАВЛяющих сложность вывсшл л з.з1 НС-языки занимают самые нижние ступени иерархии. Переходя к временнбй сложности, отметим прежде всего, что для любой грамматики без растяжения Г неравенства (2) и (3) из $2.! дают Аь+! сп ( Тг(п) (— где с и й — постоянные, зависящие от Г (и эффективно определяемые по Г). О возможности уточнения оценок временнбй сложности хотя бы для отдельных НС-языков известно немного, а то, что известно, получается довольно громоздкими рассуждениями; этот вопрос будет рассмотрен в следующем параграфе, а сейчас мы займемся сравнением временнйх сложностей НС-грамматик, неукорачивающих грамматик и грамматик без растяжения.
Теорема 3.5. Для любой грамматики бгз растяжения Г можно построить неукоричивиющую гролзматику Г, эквивалентную Г и такую, что Тг'(и) (~ г ° [Тг (п)1', гдг г — постоянная, эффективно опргдгляе»зая по Г. Дока з а тел ьств о, Пусть Г = ) У, Я7, 1, Я) — грамматика без растяжения. Положим Г = ()т, (Г 0 (Ть, Е), Ть, Е'), где 1з, Š— новые символы и )с' получается из Я следующим образом: а) каждое правило ф- ф ен»1, где заменяется правилом фЕ'~~ ~~~-ьф, если [ф[([ф), и правилом ф-»фЕ' ' ~е~, если [ф[) [ф1; б) добавляются новые правила lь - (ьЕ,!о - /, Еа — аЕ, аЕ-ь Еа, где а ен Р 0 (Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
