Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Формальные свойства грамматик
183
находятся за пределами возможностей конечных автоматов. L3 может порождаться контекстной грамматикой, но не может порождаться бесконтекстной. L2 может порождаться бесконтекстной и даже линейной грамматикой, но не может порождаться никакой системой счетчиков (ср. с разд. 1.4). L1 может порождаться системой счетчиков. Кроме того, язык порождается некоторой бесконтекстной грамматикой тогда и только тогда, когда он допускается некоторым автоматом PDS.
Как мы видели в разд. 3 предыдущей главы, основное свойство L2 (а именно, что он содержит вложенные зависимости) присуще и естественным языкам. He мешает отметить, что множество зависимостей такого рода, как в L3, также появляется в естественных языках. Постал (51] нашел развитую систему этого рода в языке могаук (Mohawk), в котором нз последовательности существительных произвольной длины может быть образован глагол, причем порядок элементов этой последовательности соответствует порядку последовательности существительных вне глагола. Язык, обладающий таким множеством зависимостей, выходит за пределы возможностей бесконтекстной грамматики или устройства PDS безотносительно к любым условиям, налагаемым на структурные описания (ср. разд. 5.1 предыдущей главы) и сильную порождающую способность. Такие подсистемы есть и в английском языке, хотя там они играют менее существенную роль. Так, Соломонов (1959, личное сообщение), а также Бар-Хиллел и LLIa-мир [5] указывают, что слово respectively (соответственно) дает возможность получить множества зависимостей типа L3 (например, John and Mary wrote to his and her parents, respectively — Джон и Мэри написали его и ее-родителям соответственно). Аналогично из эллиптического предложения John saw the play and so did Bill (Джон смотрел пьесу и Билл тоже) можно получить John saw the play and so did Bill see the play (Джон смотрел пьесу и Билл тоже смотрел пьесу), но не John saw the play and so did Bill read the book (Джон смотрел пьесу и Билл тоже читал книгу), и т. д.
В связи с этим можно заметить, что язык также будет находиться вне области действия бесконтекстных грамматик или автоматов PDS, если он будет обладать основным формальным свойством дополнения к L3, т.е. если он будет содержать бесконечное множество частей предложения (синтагм) Xit х.г,... и все предложения вида ixtfxjf, в которых і отлично от / (в то время как язык типа L3 содержит все предложения, в которых і совпадает с /, как в упомянутом примере языка могаук). Ho такого рода ограничения весьма распространены (см., например, работу [27 ] разд. 3.1). Так, в сравнительных предложениях мы можем иметь конструкцию: That one is wider than this one is DEEP (с сильным ударением на слове DEEP) [буквально: та (вещь) более широка, чем эта — глубока],
184
И. Хомский
но не конструкцию: *That one is wider than this one is WIDE [буквально: та (вещь) более широкая, чем эта— широка], так как последняя в обязательном порядке заменяется конструкцией: That one is wider than this one is [та (вещь) более широка, чем эта). Таким образом, для этих конструкций характерно, что повторяющийся элемент выбрасывается, а неповторяющийся получает сильное ударение. Неограниченную систему этого рода мы находим при введении групп существительного, как это видно на примере таких сравнительных предложений, как: John is more successful as a painter than Bill is as a SCULPTOR (Джон больше преуспел как художник, чем Билл как скульптор), но не: *JoV.n is more successful as a painter than Bill is as a PAINTER (Джон больше преуспел как художник, чем Билл как художник), которое при помощи обязательной трансформации выбрасывания сворачивается в предложение: John is more successful as a painter than Bill is (Джон больше преуспел как художник, чем Билл). Как н в случае наличия подсистем типа L3, эти конструкции показывают, что естественные языки превышают возможности бесконечных автоматов или устройств PDS безотносительно к любым замечаниям, касающимся сильной порождающей способности.
Как показывают рассмотрения этого рода, для того чтобы обогатить лингвистическую теорию н преодолеть слабые места грамматики непосредственных составляющих (ср. с разд. 5 предыдущей главы; впрочем, отмеченные там недостатки касаются только сильной порождающей способности), необходимо развивать теорню систем, пригодных для изучения бесконечных множеств цепочек, не входящих в область действия слабой порождающей способности теории бесконтекстных грамматик. В этих примерах, как и в примерах предыдущей главы, было бы легко установить требуемые правила в форме грамматических трансформаций и таким образом охватить лингвистические явления, выходящие за пределы теории грамматик непосредственных составляющих.
Мы уже почти полностью закончили доказательство теоремы 6 из разд. 1.6, которая утверждает, что с точки зрения слабой порождающей способности бесконтекстные грамматики точно соответствуют недетерминированным автоматам PDS. В разд. 2 мы указали, что общие системы подстановок точно соответствуют машинам Тьюринга, а в разд. 4.1, что односторонние линейные грамматики имеют точно такую же слабую порождающую способность, что и конечный автомат. Как для конечных автоматов, так и для машин Тьюринга недетерминированность не увеличивает (слабой) порождающей способности. Недавно было показано, что любой язык, допускаемый детерминированным линейно-ограниченным автоматом, является контекстным языком [36]. Курода отметил, что это доказательство распространяется и на недетерминированные ли-
