Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
{a. b), L
цепочек ап, ti = 1, 2, ..., нашлись бы две взаимозаме-щаемые; но взаимозамещаемость цепочек ah и а1 при k Ф I невозможна, так как ahbk eL и ahb! L. Дальнейшие примеры см. в упражнении 5.16.
§ 5.3. Линейные, металинейные и итерационно-линейные языки
В этом и следующем параграфах будут рассмотрены некоторые классы грамматик, промежуточные между классом ОА-грамматик и классом всех ОБ-грамматик, а также соответствующие классы МП-машин.
Начнем с рассмотрения так называемых линейных грамматик, наиболее близких к автоматным.
ОБ-грамматика называется линейной, если правая часть каждого ее правила содержит не более одного вхождения вспомогательного символа. Язык, порождаемый такой грамматикой, называется линейным языком.
Всякая ОА-грамматика, очевидно, линейна. Грамматики -примеров 5, 6, 9 и 12 из § 1.3 не автоматны, но линейны.
Пусть фиксированы основной и вспомогательный словари V и W. Рг или Рг-дерево, узлы которого помечены символами из V\J W, мы назовем линейным, если никакой его узел не подчиняет более одного узла, помеченного вспомогательным символом. Очевидно, ОБ-грамматика тогда и только тогда линейна, когда линейно каждое ее дерево вывода.
Линейные языки легко охарактеризовать в терминах машин Тьюринга, подобно тому, как это делалось выше для других классов языков. Назовем МП-машину од-нодорожечной, если множество ее Достояний можно
ЛИНЕЙНЫЕ И МЕТАЛИНЕЙНЫЕ ЯЗЫКИ
169
разбить на три попарно непересекающиеся подмножества: Qi («состояния прямого хода»), Q2 («состояния обратного хода») и Q3 («поворотные состояния») так, что: а) ни в одной инструкции не встречаются одновременно состояния из Qj и из Q2; б) если q е Q3, то q может встречаться только в инструкциях вида q'-*Aq и Bq-+q", где q'^Qu q" е Q2; в) начальное состояние принадлежит Qb а все заключительные состояния принадлежат Q2. Очевидно, в любом полном вычислении однодорожечной МП-машины направление движения меняется не более одного раза, иначе говоря,дерево вычисления линейно. [В соответствующем Д-автомате головка может двигаться только по одной «дорожке»; отсюда название «однодорожечная МП-машина». Термин «дорожка» (англ. path) обычен в работах по «предсказуемостному анализу» (см. стр. 141).]
Из лемм 4.12 и 4.13 немедленно вытекает
Теорема 5.8. а) Для любой линейной ОБ-грамматики можно построить эквивалентную ей однодорожечную Ш\-машину. б) Для любой однодорожечной МП-машины можно построить эквивалентную ей линейную ОЪ-грамматику.
Отметим некоторые частные случаи линейных грамматик.
Линейная ОБ-грамматика называется левосторонней, соответственно правосторонней, если правая часть каждого ее правила либо не содержит вхождения вспомогательного символа, либо имеет вид Вх, соответственно хВ, где х — цепочка в основном словаре. Читатель без труда докажет, что для каждой односторонней, т. е. левосторонней или правосторонней, линейной Б (ОБ)-грамматики можно построить эквивалентную ей А (ОА)-грамматику.
Линейная ОБ-грамматика называется симметричной, если правая часть каждого ее правила либо не содержит вхождения вспомогательного символа, либо имеет вид хАу, где А — вспомогательный символ и
\х\ = \у\.
Назовем МП-машину равномерной, если в любом ее вычислении между каждыми двумя следующими друг за другом перемещениями рабочей головки читается точно один входной символ. Читателю пред,о-
170 СПЕЦИАЛЬНЫЕ КЛАССЫ БЕСКОНТЕКСТНЫХ ЯЗЫКОВ [ГЛ. Б
ставляется доказать, пользуясь леммами 4.12 и 4.13, что для всякой симметричной линейной ОБ-грамматики можно построить эквивалентную ей равномерную однодорожечную МП-машину. (Обратное также справедливо.) Отсюда, в частности, следует, поскольку конечный автомат можно считать (с несущественной модификацией) частным случаем равномерной однодорожечной МП-машины, что всякий ОА-язык порождается симметричной линейной ОБ-грамматикой, и такая грамматика может быть построена по данной ОА-грамматике.
Отметим еще, что класс линейных языков эффективно замкнут относительно объединения, а также относительно пересечения с ОА-языком и умножения слева и справа на ОА-язык.
Непосредственным обобщением линейных ОБ-грам-матик являются металинейные ОБ-грамматики. Так называются грамматики, правила которых делятся на две группы: а) правила вида /->ш, где /—начальный символ и со не содержит вхождений /; б) правила вида Л-*<р, где А ф I и ф содержит не более одного вхождения вспомогательного символа, причем этот символ отличен от /. Язык, порождаемый металинейной ОБ-грамматикой, называется металинейным языком.
Из определения ясно, что каждый металинейный язык является объединением конечного числа языков, каждый из которых есть произведение нескольких линейных языков (причем линейные грамматики, порождающие эти языки, эффективно строятся по металинейной грамматике, порождающей данный язык). С другой стороны, читатель без труда докажет, что класс мета-линейных языков эффективно замкнут относительно объединения и умножения. Таким образом, класс мета-линейных языков представляет собой замыкание класса линейных языков относительно этих двух операций.
