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

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

Хомский Н. Формальные свойства грамматик — Москва, 1963. — 100 c.
Скачать (прямая ссылка): formalsvoystvagrammatik1963.djvu
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 .. 45 >> Следующая


Разумеется, можно рассматривать однонаправленные двунаправленные категориальные системы как порождающие г[РамМати-ки. Встает вопрос об их связях и отношениях друг с Друг0М и с
Я. Хомский

выше рассмотренными системами. Бар-Хиллел, Гайфман иШамир

13] показали следующее.

Теорема 36. Семейства однонаправленных категориальных грамматик, двунаправленных категориальных грамматик и бесконтекстных грамматик слабо эквивалентны друг другу.

Если G — двунаправленная категориальная грамматика, то существует бесконтекстная грамматика, порождающая тот же язык, что и G, н еслн G есть бесконтекстная грамматика, то существует однонаправленная категориальная грамматика, порождающая тот же язык, что и G. Несколько неожиданным следствием этого результата является тот факт, что класс однонаправленных категориальных грамматик эквивалентен по своей порождающей способности полному классу двунаправленных категориальных грамматик.

Шамнр указал недавно (личное сообщение), что для теоремы 36 существует доказательство, весьма похожее на доказательство эквивалентности бесконтекстных грамматик н автоматов PDS.

Необходимо подчеркнуть, что отношение, о котором идет речь в теореме 36,— это отношение слабой эквивалентности. Из него не ¦следует, что для любой заданной грамматики одного из этих видов .всегда найдется грамматика другого вида, дающая распределение по категориям, сравнимое по сложности или естественности, или дающая такую же систему помеченных скобок (структуру составляющих) для подцепочек. По-видимому, как раз для тех частей реальных языков, которые легко и естественно могут быть описаны при помощи бесконтекстных грамматик, соответствующее описание в терминах двунаправленной категориальной грамматики очень •быстро чересчур усложняется, а об естественном описании с помощью однонаправленной категориальной грамматики, конечно, де может быть н речи.

Системы, предложенные Ламбеком, в некоторых отношениях ¦отличаются от только что описанной; в частности, они позволяют большую свободу в приписывании категорий. Так, его правила сведения утверждают, напрнмер, что категория я одновременно является и категорией р/[а\р], так что этим нли иным путем сложность и длина последовательности символов категорий, сопоставленных цепочке, может возрастать прн применении правил приведения. Поэтому непосредственно не очевидно, как это было в ранее рассмотренных системах, что порождаемый язык представляет собой рекурсивное множество. Однако Ламбек показал, что изучаемые им системы в действительности являются разрешимыми. He известно, как связаны системы Ламбека с двунаправленными категориальными грамматиками или с бесконтекстными грамматиками, хотя можно ожидать, что эта связь окажется довольно тес-яой, возможно даже слабой эквивалентностью.
Формальные свойства грамматик

225

Привлекательность различных видов категориальных грамматик состоит в том, что они не имеют почти никаких грамматических правил, не включенных в словарь, т.е. если грамматика G дает распределение слов из конечного словаря VY по конечному числу категорий, простых или производных, то для каждой цепочки х в словаре Vt возможно определить, верно ли, что G порождает х, прн помощи вычислительного процесса, использующего правила приведення, которые одинаковы для всех грамматик заданного типа и поэтому не должны входить в состав грамматики G. Действительно, существует традиционная точка зрения, которая отождествляет грамматику с множеством грамматических свойств слов или морфем (ср. [57], стр. 149), н целесообразно будет подчеркнуть, что вышеописанный подход дает точное выражение этих понятий.

В последнее время Мэтьюз [42] исследовал обобщение теории грамматик непосредственных составляющих, прн котором допускаются некоторые типы прерванных составляющих. Продолжая следовать обозначениям, принятым в разд. 4 предыдущей главы, рассмотрим правила вида A-^cpJn ]<ра, где 0. Мы интерпретируем такое правило как в применении к цепочке ^Aav., апу , дающее цепОЧКу !(Ilf1Ct1... «„<f2Х (ГДЄ аіФе)> и В Применении К ЦепОЧКе '!/Al-,... ... am(m<n), дающее цепочку ^cp1Oi1... <*т<р2. При этих условиях бесконтекстная грамматика может рассматриваться как грамматика, имеющая только правила вида A-^vlIO ]ср2. Мэтьюз также естественным образом обобщил это понятие на случай разрывных контекстных правил. Для любой грамматики определим теперь прямой вщод, явно определенный в разд. 4.2, стр. 178, и прямую разрывную грамматику как грамматику с правилами только что описанного вида (нлн более общего контекстного разрывного типа) и с ограничением на применение правил, разрешающим только прямые выводы (ср. с разд. 4.2). Мэтьюз показал, что прямые разрывные грамматики могут порождать только бесконтекстные языки, так что это обобщение не увеличивает порождающей способности. Очевидно, то же самое верно н для обратных разрывных грамматик, которые разрешают вывод так, как это описано на стр. 178 (на каждом шаге заменяется самый правый нетерминальный символ), н в которых правило вида [ti Icp2 понимается так, что
Предыдущая << 1 .. 37 38 39 40 41 42 < 43 > 44 .. 45 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed