Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Теорема 29. Существуют бесконтекстные языки, которые не порождаются никакой однозначной бесконтекстной грамматикой.
Парих показал, что язык
L = \х I х = ап Ьтап Ьт или х = а" ЬтапЬт’,
п, ft', т, m' > 1), (49)
не может порождаться никакой однозначной бесконтекстной грамматикой, хотя он порождается множеством правил
S-S- AB, S-^DC,
аАа, А -» аВа,
C^ ЬСЬ, С -*¦ ьоь.
S-* Ь. В -*¦ ьв,
а, D aD.
В действительности существует линейная грамматика, эквивалентная грамматике (50). Степень неоднозначности, которой обладают цепочки в этой грамматике, равна 2. Другим примером такого языка является множество \апЬтар\п—т или п—р\. Интересная проб^ лема, остающаяся пока открытой, состоит в том, чтобы найти языки более высокой (быть может, неограниченной) степени неустранимой неоднозначности. Много важных н нерешенных вопросов можно сразу поставить в связи с вопросом о неустранимой неоднозначности, например ее масштаб, ее соотношения с разрешимостью проблемы неоднозначности, насколько богаты те грамматики, где оиа возникает (иапример, существуют ли минимальные линейные языки, которые неустранимо неоднозначны или существует ли неустранимая неоднозначность на уровне контекстных грамматик?) и т. д.
Из теоремы 29 возникают некоторые предположения. Очень интересен вопрос, почему естественные языки обладают именно такой
Формальные свойства грамматик
197
структурной неоднозначностью, а не другой. Мы можем надеяться получить ответ на этот Bongoc в следующем виде.
1. Грамматики естественных языков принадлежат некоторому классу Г порождающих процессов.
2. Язык L обладает достаточно богатыми выразительными средствами, чтобы содержать множество грамматических аппаратов Д, но не Д' (например, класс предложений Е, но не E').
3. Грамматика GfV, которая выражает Д, но не Д' (которая порождает Е, но не E ), должна быть неоднозначной, т. е. язык, который она порождает, неустранимо неоднозначен относительно Г.
Если бы удалось получить некоторое рассуждение такого рода, то оно было бы важным не только как «оправдание» существования структурной неоднозначности в L, но также и как поразительное свидетельство независимого (и потому особенно интересного) характера в пользу той общей лингвистической теории, которая претендует на выполнение условия (1). Вряд ли нужно подчеркивать, что мы далеки от возможности привести подобное рассуждение для естественного языка, но теорема 29 может представлять собой первый шаг в этом направлении.
4. 6. Бесконтекстные грамматики и конечные автоматы
Мы видели, что конечный автомат может быть представлен как односторонняя линейная грамматика и что у такого устройства гораздо более ограниченная порождающая способность, чем это может быть у бесконтекстной или даже у линейной грамматики. Мы видели также, что такие элементарные формальные свойства естественных языков, как рекурсивное вложение зависимостей, делают невозможным порождение их конечным автоматом, хотя эти свойства не исключают их из класса бесконтекстных (даже линейных) языков. Из этнх замечаний мы должны заключить, что способности носителя языка не могут быть охарактеризованы конечным автоматом. Грамматика, хранимая в мозгу, не может быть односторонней линейной грамматикой, что вовсе не удивительно; однако поведение говорящего или слушающего должно быть представимо конечным автоматом некоторого вида. Говорящий-слушающий имеет лишь конечную память, часть которой он использует для хранения правил имеющейся у него грамматики (множество правил для устройства с неограниченной памятью), а часть—использует для вычисления, фактически производя предложение или «воспринимая» его структуру и понимая его.
Приведенных соображений достаточно, чтобы показать, как важно достигнуть более полного понимания источника и объема избыточной порождающей способности бесконтекстных грамматик по сравнению с конечными автоматами (хотя бесконтекстные грамматики, как может быть доказано, не полностью адекватны граммати-
198
И. Хомский
ческому описанию естественных языков). Обратимся теперь к исследованию этой проблемы.
Посмотрим сначала, какие вопросы касаются связи бесконтекстных грамматик и ограниченно-бесконечных и конечных автоматов. В разя. 1.6 и 4.2 мы получили некоторые результаты (основанные частично на результатах, которые еще будут доказаны в данном разделе), относящиеся к этим вопросам. В частности, мы показали, что бесконтекстные языки представляют собой множества, которые допускаются классом ограниченно-бесконечных автоматов, названных нами автоматами PDS. Как было нами показано, из. этого факта следует, что существует чрезвычайно тесная связь между регулярными (односторонними линейными) языками и бесконтекстными языками. Именно расширим словарь V, из которого построены все бесконтекстные языки, до словаря V", содержащего V и а' для каждого а ? V. Определим К как множество всех цепочек над V", которые сводятся к е последовательным сокращением: аа' и а'а (т. е. обращаясь с а и а' как с взаимно обратными элементами). Положим сс(я)=а для а ? W > <f(a)=e для a?VY. Для любого языка L определим ф(і) = ср(/( Q L). Тогда для каждого регулярного языка L ф(?) является бесконтекстным языком, и каждый бесконтекстный язык определяется как Ф(?) При некотором! выборе регулярного языка L. Следовательно, семейство X1 регулярных языков преобразуется в семейство 1 бесконтекстных языков-преобразованием ф. -4—..
