Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Как было замечено выше, правильная построенность, определенная выше, не является разрешимым свойством для контекстных грамматик. Мы можем определить разрешимое свойство правильной построенности для этих грамматик следующим образом: грамматика G правильно построена, если она не имеет правила вида срЛВф-»-срЛо)Вф. В этом случае сильный вывод не обязательно однозначно определяется слабым выводом (как это будет в случае выполненного прежнего определения правильной построенности); но по-прежнему будет однозначно определяться слабым выводом в совокупности с последовательностью правил, использовавшихся при этом выводе (причем в общем случае нельзя обойтись ни без того, ни без другого). В действительности, как мы отметили в разд. 4 предыдущей главы, нетрудно выдвинуть эффективные ограничения, которые исключат подобную неопределенность, He влияя при этом на слабую порождающую способность (и влияя на сильную порождающую способность только введением некоторой добавочной и нигде более не употребляемой категоризации). Однако эти последние условия недостаточно обоснованы.
4.1. Специальные классы бесконтекстных грамматик
В этом разделе будут рассмотрены различные подклассы бесконтекстных грамматик, заданные дополнительными условиями на
13*
№
Н. Хомский
множество правил. Напоминаем, что каждое правило имеет вид А-*¦ ф, где А — отдельный нетерминальный символ, а ф — не пустая цепочка. Мы продолжаем следовать принятому ранее соглашению об обозначениях разд. 4 предыдущей главы. Напомним также, что ф-»і|) тогда и только тогда, когда существует ф-вы-вод i|). Кроме того, нетерминальный словарь Vn состоит в точности из тех символов А, которые появляются в левой части правила грамматики А -> ср.
Правило называется линейным, если оно имеет вид А^-хВу. Оно право-линейное, если имеет вид А-+хВ, лево-линейное, если имеет вид А ->-Вх. Заключительным правилом называется правило вида А -*х. В терминах этих понятий мы сейчас определим некоторые виды грамматик.
Определение 6. Грамматика G является
а) линейной, если каждое ее незаключительное правило линейно', в частности, если оно лево-линейно или право-линейно,
б) односторонней линейной, если каждое ее 'не-эаключительное правило право-линейно или каждое ее незаключительное правило лево-линейно’,
в) м е т а-л и н е й н о й, если все ее незаключительные правила либо линейны, либо имеют вид S-+у, и если, кроме того, в ней нет правила вида /4->tpS^ ни для каких A, tp, <]>;
г) нормальной, если все ее незаключительные правила имеют вид А-^-ВС, а все заключительные правила — вид Л->а;
д) последовательной, если ее нетерминальный сло-
варь может быть упорядочен как Ai,-.-,An таким образом, что для всех і, / из *-'fА/!/ следует, что ji>i-
В случае линейной грамматики, если ср есть строка некоторого (#5#)-вывода, то tp содержит не более одного нетерминального символа. Другими словами, имеется лишь одна точка, в которой вывод может ветвиться на каждом шаге. При первом же применении заключительного правила вывод заканчивается терминальной цепочкой. В мета-линейной грамматике имеется ограниченное число (не более п) точек, в которых вывод может разветвляться. Верхняя граница определяется самым длинным правилом, в котором появляется
S, т.е. максимальным числом появляющихся нетерминальных символов. Если применены п заключительных правил, вывод заканчивается терминальной цепочкой.
Односторонняя линейная грамматика представляет собой просто конечный автомат в смысле разд. 1.2 (см. работу [7]). Это совершенно ясно в случае односторонней линейной грамматики, все правила которой право-линейиые (либо заключительные). Без потери общности можно предположить, что каждое линейное правило G имеет вид A-^aB, где В — неначальный символ G, и что каждое заключительное правило G имеет вид А-*а. Пусть A1,...,An—нетер-
Формальные свойства грамматик
173
минальные символы Cr, причем A1— начальный символ. Мы можем поставить в соответствие грамматике G конечный автомат F с тем
же нетерминальным словарем, что и О, и с состояниями A1......Я~„,
где Ai—начальное состояние. Правила F образуются следующим путем. Если Al-^aAj — правило G, то тройка (a,A1, Ai ) есть правило^ (понимаемое как команда F перейти из состояния A1 в состояние Aj, когда он считывает с ленты символ а).
Если Ai-^a есть правило 0, то тройка (a, AitA1) есть правило F. Тогда GhF кончают работу, породив одну и ту же терминальную цепочку. Точно так же и обратно, правила конечного автомата непосредственно задают грамматику с только право-линейными или заключительными правилами.
Поскольку, если L — регулярный язык, то L*, состоящий из зеркально отраженных цепочек языка L (т.е. содержащий цепочку (V^alдля каждой al...an^L), также является регулярным языком, очевидно, что каждая односторонняя линейная грамматика представляет конечный автомат и что каждый конечный автомат может быть представлен как односторонняя линейная грамматика.
Нормальная грамматика — это грамматика, обычно имеющаяся в виду при обсуждении метода анализа по непосредственным составляющим, принятого в лингвистике. Заключительные правила А->-а, составляющие лексикон языка, резко отделены от множества грамматических правил А-+ВС, каждое из которых задает разложение на две составляющие.