Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Известно лишь одно нетривиальное свойство грамматик типа 3, именно то, которое устанавливается в теореме 14. Тем не менее этот класс грамматик заслуживает более пристального изучения. Похоже на то, что условие 3 дает адекватную в разумных пределах формализацию для набора лингвистических понятий, содержащегося в наиболее развитых вариантах метода непосредственных составляющих.
4. Бесконтекстные грамматики
Рассмотрим теперь класс грамматик, удовлетворяющих следующему условию.
Условие 4. Если есть правило грамматики, то ср
есть отдельная (нетерминальная) буква, a fy непуста.
Таким образом, каждое правило грамматики утверждает, что определенный нетерминальный символ может быть заменен цепочкой символов независимо от контекста, в котором он встречается. Назовем грамматику, удовлетворяющую условию 4, бесконтекстной грамматикой. Язык, порождаемый бесконтекстной грамматикой, назовем бесконтекстным языком. Отметим, что, хотя правила бесконтекстной грамматики применяются безотносительно к контексту, между элементами терминальной цепочки могут быть — и обычно бывают — довольно строгие ограничения совместной встречаемости. О бесконтекстных грамматиках уже известно довольно много. Мы даем здесь краткий набросок основных результатов, отсылая читателя при случае к более подробным исследованиям, описанным в других работах, за доказательствами и дальнейшим обсуждением.
Непосредственно очевидно, что если в условии 4 отбросить требование, чтобы tp была непуста, то порождающая способность бес-
13 Заказ № 563
170
Н. Хомский
контекстных грамматик останется неизменной (за исключением того, что будет порождаться «пустой» язык («}). Доказательство см. в работе [4]. Мы можем также, не уменьшая порождающей способности, потребовать, чтобы грамматика не содержала правила вида А-*-В [8J, так что бесконтекстные грамматики также удовлетворяют условию 3.
Хотя все бесконтекстные языки (языки типа 4) являются языками типа 3, обратное неверно.
Теорема 14. Язык #асп)г*іП dnb # есть язык типа 3, не порождаемый бесконтекстной грамматикой.
Доказательство принадлежит Париху [49]. Гораздо легче найти примеры языков типа 2 (языков, порождаемых классом общих контекстных грамматик), которые не могут порождаться бесконтекстной грамматикой. В частности, среди языков L1, Li и L3, рассмотренных в предыдущем разделе, хотя L1 и Li являются бесконтекстными языками, L3, конечно, таковым не является (ср. разд. 3 предыдущей главы).
Теорема 15. Язык L3 и язык {a^Vj являются языками типа 2, для которых не существует порождающей их бесконтекстной грамматики [8, 59, 4).
Можно получить С-маркер (ср. с разд. 3 предыдущей главы) для цепочки, порождаемой бесконтекстной грамматикой G, непосредственно путем построения новой бесконтекстной грамматики G' со словарем, состоящим из словаря грамматики G и дополнительных терминальных символов: ] и [д для любого нетерминального А грамматики G. Если G имела правило A-*-f, то G' будет иметь правило А-*1а<?]. Грамматика G' порождает цепочку х, содержащую скобки, задающие структуру составляющих соответствующей цепочки у, порождаемой грамматикой G, причем у может быть получена из х опусканием скобок. При некоторых специфических условиях скобка J может быть опущена без появления неоднозначности, давая своего рода бесскобочную систему записи. Разумеется, система скобок, налагаемая грамматикой G' на терминальную цепочку G1 в точности соответствует системе, определяемой нз деревьев, введенных в предыдущей главе. Итак, мы можем рассматривать структурное описание цепочки л: как цепочку <р в словаре V*, содержащем Kr н новые символы ] и [л для каждого А ? Vn-Тем же самым методом можно получить С-маркер в контекстной грамматике, если она удовлетворяет условию С, стр. 166. Если контекстная грамматика удовлетворяет условию С, мы говорим, что она правильно построена. Таким образом, контекстная грамматика G правильно построена тогда и только тогда, когда она обладает
Формальные свойства грамматик
171
следующим свойством: если ср, ф суть две последовательные строки законченного (#S#)-вывода в G1 то существуют единственные це-почки и ? Vn и Z1, х2, и>, такие, что <р —XiotXa и ^ = ZicuZa- Расширив словарь V так, чтобы он содержал скобки, как это было сделано выше, определим d(ср) (читай: «ср без скобок» или «дебракетизадия ср») длй любой цепочки ср в этом расширенном словаре, как цепочку, полученную опусканием всех вхождений скобок (вместе с их пометками) в цепочке ср. Теперь можно определить сильный ср-вывод ф как последовательность Cp1,.в которой Cp1=Cp, <р„=<]> и для каждого i^>n существуют цепочки C0j,a)2,(Ua,0)4,a>s и символ и, такие, что
ср;=ш1иі11сіиізш4;ср/+1 = ш1ш1і[а <u5koaw4; d(<%) = ш6 И с((и2аа>3)-^с( (ш2 и>5ш3)—
правило грамматики G. Если D—сильный (1+5#)-вывод f в G, a d(ф) есть цепочка в Vt , то й(ф) есть терминальная цепочка, порождаемая грамматикой G1 и f может считаться С-маркером, единственным образом сопоставленным этой цепочке при помощи вывода D', каждая строка которого есть дебракетизадия соответствующей строки вывода D. Далее, для каждого (#5#)-вывода D цепочки х в G существует соответствующий сильный (#6’#)-вывод, оканчивающийся цепочкой, которую можно принять за С-маркер, единственным образом сопоставленный выводом D цепочке х. Таким образом, для правильно построенных контекстных грамматик мы имеем точное определение порождения сильных С-маркеров.
