Гладкий - Формальные грамматики и языки - 1973 (947381), страница 34
Текст из файла (страница 34)
Ясно, что чисто стирающая МП-машина может переходить от уничтожения рабочих ячеек к их созданию, лишь уничтожив всю рабочую ленту (поскольку в крайней слева рабочей ячейке всегда пишется символ Аз, который нигде больше не может быть записан). Будем говорить далее, что МП-машина М имеет ограниченное число поворотов, если существует такое число й, что в любом полном вычислении этой машины направление движения рабочей головки изменяется не более й раз. Наименьшее из таких чисел й будем обозначать П(М); если П(М) = 1, будем пазы. вать М машиной с1поворотами. Таким образом, однодорожечная МП-машина — это чисто стирающая машина с одним поворотом, Впрочем, для любой МП-машины с одним поворотом очевидным образом строится эквивалентная ей однодорожечная. В отличие от предыдущих классов МП-машин, машины с ограниченным числом поворотов определяются не в терминах программ, а в терминах вычислений.
Однако ниже (замечание к теореме 5.11) будет показано, что по программе произвольной МП-машины М можно Распознатзь имеет ли она огРаниченное число повоРотов, и если да, найти П(М). Теперь может быть сформулирована Теорема 5.9. а) Для любой мегалинейной ОБ-грамматики можно построить эквивалентную гй чисто стирающую МП-машину с ограниченным число»4 поворотов.
б) Для любой чисто стирающей МП-маи4ины с ограниченным числом поворотов можно построить эквивалентную ей мгталингйную ОБ-грамматику. 17й спвцилльныв клдосы ввоконтвкстных языков 1гл.в З $.31 !73 линвиныя и мптдлинвпные языки Для доказательства этой теоремы нам понадобится следующая очевидная лемма, Л ем м а 5.1. Пусть М и М' — МП-машины, и пусть М» Мз, М* — их параллельная и последовательная композиции и итерация М соответственно. Тогда: а) если / М и М вЂ” чисто стирающие машины, то таковы жг М>, Мз и М*; б) если М и М' имеют ограниченное число поворотов, то это верно и для М, и М>ь причем П(М,) ~ (>пах(П(М), П(М')), П(Мт)~(П(М) + П(М'). Заметим теперь, что для машин с одним поворотом утверждение пункта а) теоремы 5.9 справедливо в силу теоремы 5.8; поэтому для общего случая оно следует из леммы 5.1.
Доказательство пункта 6) нам будет удобно ненадолго отложить. С помощью теоремы 5.9 легко указать примеры нелинейных металннейных языков (упражнение 5.26). Металннейные языки допускают естественное обобщение в двух направлениях. С одной стороны, можно рассматривать языки, допускаемые машинами с ограниченным числом поворотов, отказавшись от требования чистоты стирания, с другой — допускаемые чисто стирающими машинами без ограничения на число поворотов. Первой возможности будет посвящен следующий параграф, а сейчас мы займемся второй.
Т е о р е м а 5.10. а) Для любого бгскоэффицигнгного регулярного выражения Л (З>,..., $„, $„+>) от переменных 5» ..., 5„, 5„„> и любых и линейных ОБ-грамматик Г» ...,Г можно построить чисто стирающую МП-машину, допускающую язык л(Е(Г,),,Е(Г„),Л), 6) Для любой чисто стира>ощгй МП-машины М можно построить бгскоэффицигнтног регулярное выражение л(з>, ..., еь„, з е>) и линейно>е ОБ-грамматики Г„, .
„Г„та кис, что а (Е (Г>),..., Е (Г„), Л) = Е (М), Доказательство. а) Следует из теоремы 5.8 и леммы 5.1. 6) Пусть М вЂ” чисто стирающая МП-машина, и пусть д, дз — два произвольных состояния перехода к прямому ходу. Выбросим из программы М все инструкции, содержащие состояния .перехода к прямому ходу, кроме тех, которые содержат у« в левой части илн дз в правой, н при этом заменим >1в его «двойником»вЂ” новым состоянием д' («двойники» различных состояний различны). Начальным состоянием новой машины, которую будем обозначать М„з, объявим д„, единственным заключительным состоянием — >7'. М В является, очевидно, машиной с одним поворотом'), н для нее по теореме 5.8 можно построить эквивалентную линейную ОБ-грамматику Г„з.
Сопоставим каждой машине М в новый символ а„а и рассмотрим диаграмму О, строящуюся так: узлами ее служат состояния перехода к прямому ходу машины М вЂ” пусть это д>, ..., др! начальными и заключительными узлами будут начальное н заключительные состояния М соответственно; из а в дз идет точно одна дуга, и эта дуга помечена символом а„в, Если Ео — множество всевозможных цепочек, производимых полными путями диаграммы, то, очевидно, 1.(М)=Я(Ео! ан, а„,..., арр1Е(Мн), Е(М»),..., Е(Мрр)).
Но по диаграмме можно построить регулярное выраже-. ние, представляющее Ео (теорема 5.6). Остается заменить в этом выражении каждый символ а з на Е(Г з). В частности, если М вЂ” машина с ограниченным числом поворотов, то в диаграмме В длины путей ограничены, так что 0 не имеет циклов, и поэтому соответствующее регулярное выражение является, — точнее, может быть сделано — многочленом (замечание к теореме 5.6). Следовательно, в этом случае Е(М) 'получается нз Е(Г„з) с помощью объединения и умножения; но класс металннейных языков, как уже отмечалось, эффективно замкнут относительно этих операций. Тем самым доказана теорема 5.9, 6).
Назовем языки, допускаемые чисто стирающими МП-машинами, иге рацион но-линейными языкамии. Теорема 5.10 позволяет указать следующий «ка-' нонический вид» ОБ-грамматики, порождающей итерационно-лннейный язык: Г= ()>, 97,1,>т), где й7= й>>() 0 1«>з, 1« = )т> () >тз, причем 1«'> () 1«'з = 8; >т> состоит из правил вида А — +ВС, где А, Се= %'ь В ~ 1«>з; Яз состоит из правил вида А- от, где А я йтз и пт содержит. «) Ради этого ннм н пришлось заменить оэ «двойннком». Впро.
чем, нн сэмом деле «двойннк» необходим тол>ко прн и = й. )74 СПЕЦИАЛЬНЫЕ КЛАССЫ ЕВСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ, В не более одного вхождения символа из )17в и не содержит вхождений символов из йУЬ Такие грамматики можно назвать итера ци о и но-линейными. Из теоремы 5.10 следует также, что класс итерационно-линейных языков представляет собой замыкание класса линейных языков относительно объединения, пересечения н итерации. Существуют итерационно-линейные языки, не являющиеся металинейными (упражнение 5.27). О «допускающих возможностях» детерминированных машин рассмотренных классов см. упражнение 5.33. й 5.4.
Грамматики с ограниченной активной емкостью выводов. ОАЕВ-языки Займемся теперь изучением языков, допускаемых МП-машинами с ограниченным числом поворотов. Мы получим дзгя этих языков, подобно металинейным и итерационно-линейным, две характеристики: в терминах грамматик и в алгебраических терминах. Пусть à — грамматика с основным словарем )г и вспомогательным словарем ЧУ, и «4 ее ()г())(7)'. Назовем в активной емкостью цепочки число вхождений нее вспомогательных символов. Активной ем ко- "4 стью вывода в Г будем называть наибольшую активную емкость входящей в этот вывод цепочки *). Если существует число й, мажорирующее активные емкости всех полных выводов в Г, мы будем называть Г грамматикой с ограниченной активной емкостью выводов (ОЛЕВ-грамматикой); наименьшее из таких чисел й будет обозначаться Тв(Г).
Языки, порождаемые ОАЕВ-грамматиками, мы будем называть ОЛЕВ-я з ы к а м и. Очевидно, для приведенной ОБ-грамматики Г тогда и только тогда Те(Г) = 1, когда Г линейна. à — п Введем еще одно вспомогательное понятие. П сть — роизвольная ОБ-грамматика, Т вЂ” дерево вывода в у ть 4) и еличины фактически уже рассматривались нами.
4) Обе ат в Именно, фигурирующая в определении активной емкости грамматики (стр, 57) функция ((Г,Р,4) — вто активная емкость цепо 1(,, ) — активная емкость вывода Р. (Активная емкость Б-г ам. матнк изучается ниже, 4 72.) ость -грам. $ ал) ГРАммАтики с ОГРАниченнОЙ емкОстью ВыВОдОВ )Тз ней и Т' — Рпдерево, полученное из Т выбрасыванием всех узлов, помеченных основными символами.
Число висячих узлов дерева Т' будем называть п р и в е д е н н ы м индексом ветвления дерева Т (не ТЧ). Нетрудна видеть, что это число равно наибольшему значению активной емкости вывода, отвечающего дереву Т. (В самом деле, это наибольшее значение достигается на выводе, в котором правила, не содержащие в правых частях вспомогательных символов, применяются в последнюю очередь; а цепочка этого вывода, имеющая наибольшую активную емкость, — точнее, последняя из таких цепочек — должна «проходить» через все висячие узлы Т'.) Таким образом, ОБ-грамматика Г тогда и только тогда является ОЛЕВ-грамматикой, когда множество приведенных индексов ветвления полных выводов в Г имеет конечную наименьшую верхнюю грань; последняя, если она существует, равна (а(Г), Теперь мы можем доказать следующее утверждение.
Л ем м а 5.2. Существует алгоритм, позволяющий по любой ОБ-грамматике Г распознать, является ли она ОЛЕВ-грамматиком, и в случае положительного ответа найти )а(Г). Д о к а з а т е л ь с т в о. Назовем рангом вспомогательного символа А ОБ-грамматики Г = ()7, )(У, 1, )1) наименьшую верхнюю грань множества приведенных ин» дексов ветвления деревьев выводов в 1", начинающихся символом А и заканчивающихся цепочками в )г. Кроме того, каждому основному символу припишем ранг О. Все символы конечного ранга можно найти — и определить их ранги — следующим способом.
Определим последовательность ))уе, )е'4, ... подмножеств словаря )г() йу так: )Тга = У; если опРеделены (ьче, ..., )»ги, то )(уя+4 состоит из тех А ен В" — ()Тге ()... () йУ„), которые обладают следующим свойством; какова бы ни была последовательность Ао-ььзА44)п А,— $вАвг)„, А,,— »Ь,А,тЬ пРавил Г такая, что Ао = А и Ао ° А ~ )Тг — ()г'о() ° ...()у„), всецепочки $4, т(4 принадлежат )г'. (Это свойство, очевидно, эффективно проверяемо.) Непосредственная нндукция по а показывает, что для каждого В'„ все принадлежащие ему символы имеют конечные ранги; способ их нахождения ясен нз конструкции. Ц то же !7б СПЕЦИАЛЬНЫЕ КЛАССЫ ВЕСКОНТЕКСТНЫХ ЯЗЫКОВ (ГЛ. З время символы, не вошедшие ни в одно )(7„, если такие есть, имеют бесконечный ранг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
