Научная литература
booksshare.net -> Добавить материал -> Лингвистика -> Хомский Н. -> "Формальные свойства грамматик " -> 20

Формальные свойства грамматик - Хомский Н.

Хомский Н. Формальные свойства грамматик — Москва, 1963. — 100 c.
Скачать (прямая ссылка): formalsvoystvagrammatik1963.djvu
Предыдущая << 1 .. 14 15 16 17 18 19 < 20 > 21 22 23 24 25 26 .. 45 >> Следующая


Как было замечено выше, правильная построенность, определенная выше, не является разрешимым свойством для контекстных грамматик. Мы можем определить разрешимое свойство правильной построенности для этих грамматик следующим образом: грамматика 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), также является регулярным языком, очевидно, что каждая односторонняя линейная грамматика представляет конечный автомат и что каждый конечный автомат может быть представлен как односторонняя линейная грамматика.

Нормальная грамматика — это грамматика, обычно имеющаяся в виду при обсуждении метода анализа по непосредственным составляющим, принятого в лингвистике. Заключительные правила А->-а, составляющие лексикон языка, резко отделены от множества грамматических правил А-+ВС, каждое из которых задает разложение на две составляющие.
Предыдущая << 1 .. 14 15 16 17 18 19 < 20 > 21 22 23 24 25 26 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed