Гладкий - Формальные грамматики и языки - 1973 (947381), страница 33
Текст из файла (страница 33)
В заключение докажем еще одну теорему, дающую очень удобный критерий автоматности языка. Теорем а 5.7. Для того чтобы язык Е в словаре )з был ОА-языком, необходимо и достаточно, чтобы существовала согласованная с ним конгрузнция конечного индекса на )т". (Определения конгруэнции и согласованности см. ниже, стр, 3! б и 318.) Доказательство. а) Пусть Г= (1', У,1,)А)— стандартная ОА-грамматика и Е(Г) = Е. Для каждой цепочки х Ее Р» обозначим через 0(х) множество всех пар (А,В), А, В~ У, обладающих следующим свойством: в диаграмме Г существует путь из А в В, производящий х.
Положим хну, если 0(х) = 0(у). Легко видеть, что 1! — конгруэнция. Индекс 1! не превосходит числа всевозможных подмножеств множества [Рз и, следовательно, конечен. При этом хее Е тогда и только тогда, когда 0(х) содержит пару вида (1, С), где С вЂ” заключительный узел диаграммы Г. Таким образом, принадлежность х к Е вполне определяется множеством 0(х), а это означает согласованность 1! с Е. б) Пусть !т — согласованная с Е конгруэнцня конечного индекса на 1", А — произвольный В-класс и х ~ У'. Все цепочки вида гх, где г ~ А, будут, очевидно, принадлежать одному и тому же 11-классу В; мы будем говорить, что х переводит А в В. Определим теперь ОА- грамматику Г = (1', [Р,1, В) следующим образом: )Р есть множество всех В-классов; 1 — класс, содержащий Л; В состоит из всевозможных правил вида А- аВ, где а — элемент У, переводящий А в В, и вида А- Л, где А с: — Е.
Ясно, что цепочка хек Г» тогда и только тогда производится путем диаграммы Г, идущим из А в В, когда она переводит А в В. В частности, х производится полным путем, т. е. принадлежит Е(Г), тогда и только тогда, когда х переводит 1 в некоторый «заключительный» класс, а это, поскольку Л еи 1, равносильно тому, что х сама принадлежит «заключительному» классу; но объединение таких классов совпадает с Е. Из доказанной теоремы и леммы ПП.1 (см. ниже, стр, 318) вытекает !йз специАльные клАссы Бесконтекстных языков [гл.
е линенные и метАлиненные языки 16» $ к»1 Следствие. Для того чтобы язык Т. в словаре Ь' был ОА-языка»к необходимо и достаточно, чтобы отношение Ф$ имело конечный индекс. юс Теорема 5.7 и сформулированное только что следствие часто оказываются полезными, когда надо доказать, что тот или иной язык не автоматный. Рассмотрим, например, язык В = (а" Ь" ) и = 1, 2,...).
Если бы отношение (=Ь имело конечный индекс, то среди [«, ь[, с цепочек а", и = 1, 2, ..., нашлись бы две взаимозаме[цаемые; но взаимозамещаемость цепочек а' и а' при й Ф! невозможна, так как а»ЬА ~ Е и аАЬ'ф Т.. Дальнейшие примеры см. в упражнении 5йб. 3 5.3. Линейные, металинейные и итерационно-линейные языки В этом и следующем параграфах будут рассмотрены некоторые классы грамматик, промежуточные между классом ОА-грамматик и классом всех ОБ-грамматик, а также соответствующие классы МП-машин.
Начнем с рассмотрения так называемых линейных грамматик, наиболее близких к автоматным. ОБ-грамматнка называется линейной, если правая часть каждого ее правила содержит не более одного вхождения вспомогательного символа. Язык, порождаемый такой грамматикой, называется л и н е йным языком. Всякая ОА-грамматика, очевидно, линейна. Грамматики .примеров 5, 6, 9 и 12 из $1.3 не автоматвы, но линейны, Пусть фиксированы основной и вспомогательный словари [' и )г'.
Рн или Рэ-дерево, узлы которого помечены символами из Иэ'В', мы назовем ли не й н ы и, если никакой его узел не подчиняет более одного узла, помеченного вспомогательным символом. Очевидно, ОБ-грамматика тогда и только тогда линейна, когда линейно каждое ее дерево вывода. Линейные языки легко охарактеризовать в терминах машин Тьюринга, подобно тому, как это делалось выше для других 'классов языков. Назовем МП-машину одн о дар аж е ч н о й, если множество ее «остояний можно разбить на три попарно непересекающиеся подмножества: [г1 («состояния прямого хода»), О» («состояния о р братного хода») и О» («поворотные состояния» так, что: а) ни в одной инструкции не встречаются одновр- еменно состояния из [',[1 и из [гм б) если д я [гм то д может встречаться только в инструкциях вида а'- Аа н Ва- д", где д'е Оь д" я [гм в) начальное состояние принадлежит [гь а все заключительные состоянии принадлежат Яь Очевидно, в любом полном вычислении однодорожечной МП-машины направление движения меняется не более одного раза, иначе говоря, дерево вычисления линейно.
[В соответствующем Д-автомате головка может двигаться только по одной «дорожке»; отсюда название «однодорожечная МП-машина». Термин «дорожка» (англ. ра()[) обычен в работах по «предсказуемостному анализу» (см. стр. 14!).) Из лемм 4.!2 и 4.13 немедленно вытекает Теорем а 5.8. а) Для любой линейной ОБ-грим»[атики можно построить эквивалентную ей однодорожеч- МП-»[ашину. 6) Для любой однодорожечной МП- машины можно построить эквивалентную ей лин у ейн ю ОБ-гран»[атаку. Отметим некоторые частные случаи линейных грамматик. Линейная ОБ-грамматика называется л е в ос т оранней, соответственно правосторонней, если часть каждого ее правила либо не содержит правая вхождения вспомогательного символа, ли о и д меет ви Вх, соответственно хВ, где х — цепочка в основном словаре.
Читатель без труда докажет, что для каждой односторонней, т. е. левосторонпей или правосторонней, линейной Б(ОБ)-грамматики можно построить эквивалентную ей А(ОА)-грамматику. Линейная ОБ-грамматика называется си м м е тр и чной, если правая часть каждого ее правила либо не содержит вхождения вспомогательного символа, либо имеет вид х у, хАу, где А — вспомогательный символ и (х! = !у). Назовем МП-машину р а в н о м е р н о й, если в любом ее вычислении между каждыми двумя следующими друг за другом перемещениями рабочей головки читаетря точно один входной символ. Читателю ппецо- 17о специАльные клАссы еесконтекстных языков (Гл. 6 4 з.з1 линеЙные и мвтАлинеяные языки !т1 ставляется доказать, пользуясь леммами 4.12 н 4.13, что для всякой симметричной линейной ОБ-грамматики можно построить эквивалентную ей равномерную однодорожечпую МП-машину.
(Обратное также справедливо.) Отсюда, в частности, следует, поскольку конечный автомат можно считать (с несущественной модификацией) частным случаем равномерной однодорожечной МП-машины, что всякий ОА-язык порождается симметричной линейной ОБ-грамматикой, и такая грамматика может быть построена по данной ОА-грамматике. Отметим еще, что класс линейных языков эффек- . тивно замкнут относительно объединения, а также относительно пересечения с ОА-языком и умножения слева н справа на ОА-язык. Непосредственным обобщением линейных ОБ-грамматик являются метал и нейные ОБ грамм атнки.
Так называются грамматики, правила которых делятся на две группы: а) правила вида 1- ь4, где 1 — начальный символ и 4ь не содержит вхождений 1; б) правила вида А - 4р, где А ~1 и ~р содержит не более одного вхождения вспомогательного символа, причем этот символ отличен от 1. Язык, порождаемый металинейной ОБ-грамматикой, называется м е т а л и н е й н ы м я з ыкам. Из определения ясно, что каждый металинейный язык является объединением конечного числа языков, каждый из которых есть произведение нескольких линейных языков (причем линейные грамматики, порождающие эти языки, эффективно строятся по металинейной грамматике, порождающей данный язык).
С другой стороны, читатель без труда докажет, что класс мета- линейных языков эффективно замкнут относительно объединения и умножения. Таким образом, класс мета- линейных языков представляет собой замыкание класса линейных языков относительно этих двух операций. Чтобы получить «автоматную характеристику» мета- линейных языков, нам придется ввести два новых класса МП-машин. Будем называть МП-машину чисть стирающей, если множество ее состояний можно разбить на четыре попарно непересекающиеся подмножества: (г1 («состояния прямого хода»), 1~з («состояния обратного «ода»), Оз («состояния перехода к прямому ходу») и (г4 («состояния перехода к обратному ходу») так, что: а) нн в одной инструкции не встречаются одновременно состояния из О~ и из 4гз, б) если 41'ен 1;1з, то д может встречаться только в инструкциях вида Аьд" -+ ч и д-+ Азу', где дь ее 1«з 01 14 д' ее '«1 0 Я4 и Аз — выделенный рабочий символ, один и тот же во всех инструкциях этого вида и не входящий ни в какие другие инструкции; в) если а ~ О4, то а может встречаться только в инструкциях вида а'- Аа и Ва- о", где а'ее О,()ЯЗ, дь ~ Оз() 1„14; г) начальное состояние и все заключительные состояния принадлежат Яз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
