Author: Хомский Н.  

Tags: грамматика  

Year: 1963

Text
                    с.-Ш "
ФОРМАЛЬНЫЕ СВОЙСТВА ГРАММАТИК ')
Н. Конский
Предлагаемая ниже теория лингвистической структуры, частич-
частично уже рассмотренная в предыдущей главе2), должна точно опреде-
определять класс допустимых предложений, класс допустимых грамматик
и масс допустимых структудных_.опиданий, а также должна давать
фиксированный и единообразный метод приписывания одного или
нескольких структурных описаний каждому предложению, порож-
порождаемому грамматиками допустимого класса. В предыдущей главе
нами были предложены две концепции лингвистической струк-
структуры — теория грамматик непосредственных составлятч'иу и тер-
рия трансформационных грамматику, которые обе удовлетворяют
этим минимальным требованиям. Ныло отмечено, что эмпирическая
неадекватность теории грамматик непосредственных составляющих
совершенно очевидна; поэтому не предпринималось никаких осно-
основательных попыток широкого применения ее к лингвистическим
данным. Напротив, теория трансформационных грамматик (как
о том свидетельствует все возрастающее число весьма существен-
существенных данных) может дать нам достаточно точную картину граммати-
грамматической структуры языка (см. работу [12] и библиографические ссыл-
ссылки к ней).
Тем не менее имеются серьезные основания интенсивно продол-
продолжать изучение теории грамматик непосредственных составляющих.
Как отмечено в предыдущей главе, эта теория вполне адекватно
отражает некоторые важные аспекты грамматической структуры и,
следовательно, в какой-то мере она, безусловно, является эмпири-
эмпирически мотивированной. Далее, это единственная хоть сколько-ни-
сколько-нибудь лингвистически значимая теория грамматики, которая на-
настолько проста, что возможно изучение ее абстрактных свойств.
По-видимому, углубленное изучение порождающих систем этого
вида, так же как и описываемых ими языков, является необходи-
необходимой предпосылкой любой попытки серьезно подойти к вопросам,
1) Chomsky N., Formal properties of grammars. Handbook of Mathe-
Mathematical Psychology, vol. 2, ch. 12, Wiley, 1963, 328—41S.
2) Речь идет о гл. 11 этой же книги. Русский перевод этой главы поме-
помещен в предыдущем выпуске настоящего сборника (X о м с к и й Н., Мил-
Миллер А., Введение в формальное изучение естественных языков, стр. 229).
Гл. 13 также посвящена математической лингвистике и тесно связана с гл.
11 и 12; ее перевод будет помещен в одном из следующих выпусков настоя-
настоящего сборника.— Прим. перев.
8 Заказ №. 563


122 Н. Хомский касающимся формальных свойств более богатых и гораздо более сложных систем, которые действительно позволяют надеяться дос- достигнуть эмпирической адекватности в широком масштабе. В настоя- настоящее время это та самая область, где изучение математических мо- моделей имеет наибольшие шансы оказаться плодотворным и дать зна- значительное проникновение в лингвистическую структуру н лингвис- лингвистические способности носителя языка. В соответствии с терминологией предыдущей главы мы должны различать слабую порождающую способность теории лингвистиче- лингвистической структуры (т. е. множество языков, перечисляемых граммати- грамматиками вида, определяемого этой теорией) и ее сильную порождающую способность (множество структурных описаний, перечисляемых допустимыми грамматиками). Здесь мы в основном ограничимся рассмотрением слабой порождающей способности по той простой причине, что за малым исключением это единственная область, где были получены существенные результаты математического харак- характера. В конечном счете интерес, несомненно, представляет изучение сильной порождающей способности теорий, подтвержденных и проверенных опытом, а не изучение слабой порождающей способ- способности теорий, ценность которых в лучшем случае предположительна. Важно, чтобы технические детали математического исследова- исследования не заслонили основное назначение этих теорий — лингвистиче- лингвистическую значимость и соответствие опытным данным. Мы хотим за- заполнить пробел между моделями, доступными математическому изу- изучению, и моделями, подтвержденными опытными данными, но для этого прежде всего необходимо ясно отдавать себе отчет в существо- существовании и характере этого пробела. Поэтому, в частности, было бы большой ошибкой предполагать, что богатство и сложность порож- порождающих механизмов, допускаемых какой-либо теорией, может из- измеряться слабой порождающей способностью этой теории. Дейст- Действительно, может оказаться, что корректная теория грамматик по- позволит порождать широкий класс языков, но весьма бедный класс систем структурных описаний; иначе говоря, она будет иметь вы- высокую слабую порождающую способность, но низкую сильную по- порождающую способность. Поэтому иерархия теорий, описываемая в этой работе в терминах слабой порождающей способности, ни в коем случае не должна быть интерпретирована как дающая серьез- серьезную оценку богатства и сложности предлагаемых теорий. !• Абстрактные автоматы 1-1. Отражение языковых способностей носителей языка В самом начале предыдущей главы были поставлены проблемы построения моделей, представляющих а) различные аспекты язы- языковых способностей человека, говорящего на каком-либо языке, Формальные свойства грамматик 123 и б) различные аспекты его поведения при пользовании этими спо- способностями. Вторая задача имеет дело с реальными действиями го- говорящего или слушающего — носителя данного языка; первая касается его знаний об этом языке. Психологам давно известно, что описание того, что делает организм, и описание того, что этот орга- организм знает,—далеко не всегда одно и то же ([38], стр. 553; [75], стр. 364). Порождающая грамматика, приписывающая структур- структурные описания бесконечному классу предложений, может рассмат- рассматриваться как частичная теория того, что знает взрослый носитель языка. Она ни в коей мере не ставит себе целью описывать его ре- реальные действия в качестве говорящего нли слушающего. Тем не менее вряд ли можно надеяться разработать разумную теорию ак- актуального речевого поведения иначе, как на основе серьезного и глубокого изучения того, что же знает о языке его носитель. Порождающая грамматика содержит сведения о структуре пред- предложения, в принципе присущие человеку, владеющему языком. Она показывает, как в идеальном случае, оставляя в стороне огра- ограничения памяти, внимания и т.п., этот человек понимает какое-либо предложение (если допустить, что процессы, связанные с «понима- «пониманием», могут быть описаны в пределах синтаксиса). Действительно, такие предложения, как пример 11 из предыдущей главы, совер- совершенно невозможно понять с первого прослушивания, но это не име- имеет никакого отношения к вопросу, порождаются ли эти предложения усвоенной грамматикой; точно так же неспособность человека умно- умножить в уме 18 674 на 26 521 никак не означает, что он не владеет правилами умножения. В каждом из этих случаев искусственное увеличение памяти, времени, внимания и т. п. скорее всего приведет его к единственному правильному ответу. В обоих случаях имеются задачи, которые настолько превышают возможности памяти и вни- внимания решающего субъекта, что правильный ответ никогда не бу- будет достигнут, и в обоих случаях остается единственная возмож- возможность — предположить, что рекурсивные правила, позволяющие получить правильное решение, как-то представлены в мозгу реша- решающего, несмотря на то, что (по совершенно посторонним причинам) это решение не может быть достигнуто никакими реальными дейст- действиями. В своей работе [57], которая заложила основы современного подхода к изучению языка и открыла новую эпоху в истории явы- кознания, Фердинанд де Соссюр проводит фундаментальное раз- различие между тем, что он называет языком и речью (Iangue et parole). Первый есть грамматическая и семантическая система, содержаща- содержащаяся в мозгу говорящего; вторая есть тот реальный акусти- акустический сигнал, который исходит из его органов речи и входит в его органы слуха. Соссюр выдвинул аналогию между языком и речью, с одной стороны, и некоторой симфонией и отдельным исполнением
124 Н, Хомский этой симфонии — с другой, и заметил, что ошибки или индивиду- индивидуальные особенности отдельного исполнения ничего не говорят о подлинной сущности исполняемой симфонии. Язьис, система, пред- представленная в мозгу, является о:иовным объектом психологических и лингвистических исследований, хотя мы можем судить о его при- природе н свойствах лишь иа основе изучения речи, и точно так же человек может построить для себя эту систему только путем на- наблюдений над образцами речи. Врожденная способность ребенка обучаться языку (Jaculte de langage) дает ему воэможиость почув- почувствовать и развить лингвистическую систему (язык) с помощью разнообразных наблюдений над актуальным речевым поведением (речью). Изучение других аспектов языка может быть серьезно пред- предпринято только на базе адекватных знаний о лингвистической ин- интуиции говорящего, т. е. на базе описания его языка. Этот общий подход лежит в основе нашей работы. Иногда он критикуется — если не отбрасывается —как «менталистский»1). Од- Однако аргументы, выдвигаемые против основной концепции Соссюра, не представляются иам достаточно убедительными. В этой работе мы не можем вдаваться в специальное обсуждение, но, по-видимо- по-видимому, подобные «антименталистские» аргументы, если бы они были верны, могли бы быть выдвинуты точно так же против любой по- попытки построения теорий, объясняющих наблюдаемые явления. Они просто полностью отрицают науку как интеллектуально зна- значимое явление. Отдельные «менталистские» теории могут быть бес- бесполезны или бессодержательны (так же, впрочем, как и «бихеви- «бихевиористские» или «механистические» теории), ио вовсе не потому, что они имеют' дело с «менталистскими» понятиями, не ассоциирован- ассоциированными ни с каким необходимым и достаточным операционным или «бихевиористским» критерием. Факты поведения (например, об- образцы речи, отдельные арифметические подсчеты) могут оказаться достаточными для доказательства правильности некоторой теории интеллектуальных способностей индивидуума (например, его язы- языка, его врожденной способности обучаться языку, его знания ариф- арифметики); точно так же наблюдаемое изменение цвета лакмусовой бумажки подтверждает предположение о химической структуре ве- вещества или показания измерительных приборов приводят нас к принятию или отбрасыванию какой-либо физической теории. В каж- каждом из этих случаев основная сущность теории (т.е. врожденные ') Автор противопоставляет здесь «менталистский» (mentalistic от men- mental— умственный, психический) подход «бихевиористскому» (behavioral от behavior — поведение). Ср. с определением бихевиоризма в «Философской энциклопедии» (т. I, M., 1960, стр. 170): «Бихевиоризм — господствующее направление в американской психологии XX века, отрицающее сознание как предмет психологии и считающее таковым поведение, под которым понима- понимаются телесные реакции на стимулы».— Прим. перев. Формальные свойства грамматик 125 или приобретенные лингвистические знания, арифметические спо- способности или знание арифметики, природа физического мира) не должна смешиваться с явлениями, свидетельствующими в ее поль- пользу или против нее. Название «наука о поведении» так же подходит для общего обозначения психологии, как «наука об измерениях»— для физики. Мы отходим от строго соссюровской концепции в двух направ- направлениях. Во-первых, мы совершенно не упоминаем о семантической стороне языка. Тенемногие замечания, которые могут быть сделаны по этому вопросу, лежат за пределами настоящего обзора. Во-вто- Во-вторых, наша концепция языка отличается от соссюровской в следую- следующем: мы считаем, что язык должен быть представлен как порожда- порождающий процесс, основанный на рекурсивных правилах. Соссюр, по-видимому, рассматривал' язык в основном как хранилище зна- знаков (слов, готовых предложений и т. п.) и их грамматических свойств, включая, возможно, некоторые «типы синтагм» (phrase types). Ввиду этого он не был в состоянии сколько-нибудь серьезно зани- заниматься вопросами структуры предложения и был вынужден прийти к заключению, что формирование предложений есть в основном яв- явление речи, а не языка, т. е. порождение скорее свободного творчес- творчества индивидуума, чем систематических правил. Этого по меньшей мере странного заключения можно избежать, только придя к пони- пониманию того, что "бесконечное множество элементов, отличающихся определенными типами внутренней структуры (таких, как, в част- частности, предложения естественного языка с их структурными опи- описаниями), может быть охарактеризовано при помощи -конечного ¦ рекурсивного порождающего процесса. Этот подход был почти не- неизвестен в то время, когда Соссюр читал свои лекции. Но если толь- только сформулировать понятие языка в этих терминах, то сразу же появляется надежда включить в описание языка полное определе- определение синтаксической структуры. Далее, даже существенно конечные разделы лингвистической теории, например фонология, получат теперь несколько другую формулировку, как мы коротко отметили в разд. 6 предыдущей главы. В связи с этим возникают также но- новые и важные вопросы семантического характера. Так, можно спро- спросить, как носитель языка использует эти рекурсивные механизмы, определяющие предложения и их структурные описания, иа раз- различных уровнях языка для того, чтобы с их помощью понимать предъявленные ему предложения, строить новые необходимые ему предложения, использовать отклонения от нормативной граммати- грамматической структуры в целях экспрессии или стиля и т. д. 129 J. Не выдерживает серьезной критики широко распространенная точка зрения, согласно которой наше владение языком заключается в знании фиксированного числа грамматических образцов, каждому из которых придано определенное значение, и множества знача-
126 Н. Хамский щих единиц, которые можно в них подставлять, так что значение получившегося предложения просто некоторым образом составлено из значений его компонентов. С этим видоизменением концепция Соссюра дает возможность исследования трех видов моделей, показанных на рис. 1. Устройство А — это грамматика, порождающая предложения и их структурные описания, иначе говоря, А представляет лингвис- лингвистическую интуицию говорящего, его знания о языке, его язык. Если мы хотим представить А в виде устройства со входом и выходом, то Предложение S. структурное описание; Предложение s - - Структурное описание s Лингвистические данные Грамматика Рис. I. Три типа психолингвистических моделей, основанных на соссюровской концепции языка. на вход могут подаваться натуральные числа и А может рассматри- рассматриваться как устройство, перечисляющее (в некотором порядке, ко- который сейчас для нас несуществен) бесконечное множество предло- предложений с их структурными описаниями. Здесь будет использоваться как этот подход, так и вышеописанный взгляд на А как на теорию языка. Устройство В представляет процесс восприятия, состоящий в определении структуры предложения. На входе имеется предложе- предложение s, воспринятое органами чувств, и слушатель, представленный моделью В, строит внутреннее представление — перцепт, которое мы называем структурным описанием s. Итак, устройство В пред- представляет собой модель процесса понимания предложения, если (что вовсе нетривиально) свести этот процесс к определению его грамматической структуры. Формальные свойства грамматик 127 Устройство С представляет способность обучаться языку, ина- иначе говоря, врожденные способности, дающие возможность индиви- индивидууму построить для себя механизм типа А, используя знакомство на опыте с конечной совокупностью высказываний, а также, несом- несомненно, информацию каких-то иных видов. Устройство, обратное к В, могло бы считаться моделью говоря- говорящего; действительно, еще Соссюр предложил понимать говорящего как устройство, имеющее на входе последовательность понятий и выдающего на выходе физическое сообщение. Но это положение не выдерживает критики. При современном состоянии наших знаний задача представления говорящего моделью со входами и выходами, по-видимому, не может быть четко сформулирована. Из трех только что описанных задач о построении моделей пер- первая должна быть и логически первой. Устройство типа А появля- появляется на выходе устройства типа С,т.е. является основным резуль- результатом процесса обучения. Можно также полагать, что наиболее пер- перспективный подход к проблеме построения устройства С заключа- заключается в исследовании лингвистических универсалий, структурных свойств, общих для всех порождающих грамматик. Чтобы сделать возможным овладение языком, необходимы, по-видимому, какие-то начальные ограничения на класс возможных систем, к которым по предположению принадлежат наблюдаемые явления; организм дол- должен быть заранее настроен на то, чтобы искать и идентифицировать определенные виды структурных закономерностей. Универсаль- Универсальные свойства грамматики дают возможность сделать некоторые предположения о том, какую форму могут принимать эти началь- начальные ограничения. Далее, кажется очевидным, что каждая интерес- интересная реализация устройства В, достаточно естественная и не постро- построенная полностью ad hcc, должна включать устройство А как основ- основной компонент; иначе говоря, процесс восприятия должен естест- естественно основываться на знаниях воспринимающего о структуре со- совокупности единиц, из которых построен воспринимаемый объект. Все эти соображения приводят иас к необходимости в первую оче- очередь заняться изучением природы грамматик — устройств типа А, что и будет сделано в данной главе. Заметим еще раз, что логиче- логическая первичность языка (т.е. устройства Л) есть одно из основных положений Соссюра. Основная цель теоретической лингвистики состоит в том, чтобы определить такие общие свойства устройств типов А, В и С, кото- которые окажутся эмпирически адекватными и смогут служить объяс- объяснительными теориями для различных частных случаев. Устройства В и С, моделирующие реальное поведение, должны непременно быть строго конечными, но А, которое моделирует знания носителя языка, может порождать настолько сложный и «запутанный» ком- комплекс объектов, что никакой строго конечный механизм не смог бы
128 Н. Хамский распознать или воспроизвести все его элементы. Другими словами, мы не можем на основании того факта, что содержащиеся в мозгу правила грамматики конечны, заключить, что множество порождае- порождаемых грамматических структур должно иметь тот специальный вид, с которым может иметь дело строго конечный механизм. Действи- Действительно, если Л есть грамматика естественного языка L, то очевид- очевидно, что не обязательно существует строго конечный механизм типа В, дающий на выходе правильное структурное описание тогда и только тогда, когда на вход было подано предложение языка L. В этом нет ничего удивительного или парадоксального; это не обя- обязательно следует из бесконечности языка L, но скорее из опреде- определенных структурных свойств порождающего механизма А. С этой точки зрения отдельные довольно важные положения лингвистической теории могут, по крайней мере в принципе, счи- считаться входящими в общую теорию (абстрактных) автоматов. Эта достаточно широко разработанная теория (обзор современного со- состояния см. у Мак-Нотона [45]) пока не обратила на себя должного внимания в литературе по психологии н не очень доступна для боль- большинства психологов. Поэтому мы считаем вполне уместным дать здесь обзор некоторых общеизвестных понятий и результатов (вместе с некоторыми новыми материалами) в качестве основы для более специального исследования механизмов для порождения предложений, приводимого в разд. 2—5. 1.2. Строго конечные автоматы Простейшим видом автомата является строго конечный автомат. Мы можем описать его как механизм, состоящий из блока управле- управления, считывающей головки и ленты. Блок управления содержит конечное число частей, которые могут быть установлены конечным числом различных способов. Каждая такая установка называется внутренним состоянием автомата. Лента разделена на клетки; можно считать, что она простирается неограниченно далеко как влево, так и вправо (т.е. что она бесконечна в обе стороны). Счи- Считывающая головка в каждый момент времени находится против од- одной определенной клетки на ленте и может распознавать символы О(,,аъ...,ао, составляющие конечный алфавит А (а0 играет роль еди- единичного элемента). Предполагается, что лента может двигаться только в одном направлении, скажем справа налево. Выделяется одно из состояний автомата, которое называется его начальным со- состоянием и обозначается So. Состояния автомата обозначаются ......,S,(i>0). Можно описать работу автомата следующим образом. Последо- Последовательность символовaPl, ..., apt @<^<D) из алфавита Л записа- записана в подряд идущих клетках ленты, по одному символу в каждой клетке. Предполагается, что символ #, не принадлежащий алфа- Формальные свойства грамматик 129 виту Л, занимает все клетки налево от ар, и все клетки направо от a$k. Блок управления установлен в состоянии So. Считывающая головка установлена против клетки, содержащей символ ар, . Эта начальная конфигурация машины-ленты показана на рис. 2. блок управления {в состоянии Рис. 2. Начальная конфигурация машииы-ленты. Блок управления работает так, что если он находится в неко- некотором состоянии, а считывающая головка стоит против определен- определенного символа, то он переходит в новое состояние, в то время как лента продвигается на одну клетку влево. Так, на рис. 2 блок уп- управления переходит в новое состояние S;, в то время когда лента сдвигается так, что считывающая головкя оказывается против клетки с символом ар,. Это вторая конфигурация машины-ленты. Машина продолжает работать таким образом до тех пор, пока она не будет блокирована (т.е. пока не появится такая конфигурация, для которой она не имеет дальнейшей команды) или пока она не возвратится в начальное состояние. В последнем случае, если счи- считывающая головка окажется против клетки справа от apft (в этом случае, впрочем, машина будет блокирована, поскольку в этой клетке стоит символ # ?А), мы говорим, что автомат допускает (или, что эквивалентно, порождает) цепочку #ap,...apA#. Мно- Множество цепочек, допускаемых автоматом, есть язык, допускаемый (порождаемый) этим автоматом. Итак, поведение автомата описывается конечным множеством троек A, /, k), 0<i<D, 0</, k <rc, где тройка (i, j, k) интерпре- интерпретируется как правило, говорящее, что если блок управления на- находится в состоянии S, и считывающая головка стоит против сим- символа а;, то блок управления может перейти в состояние Sk. Общая картина поведения автомата может быть представлена с помощью диаграммы состояний, состоящей из узлов, помеченных обозначе- обозначениями состояний, и ориентированных путей (стрелок), соединяю-
ISO И. Хамский щих узлы; пути помечены символами из алфавита А. В этом графе узел, помеченный S/, соединен стрелкой, помеченной а„ с узлом, помеченным Sk, в том и только том случае, если ((', /, k) есть одна из троек, описывающих поведение автомата. Пример такого графа показан на рис. 3. (Когда мы интерпретируем такие системы как грамматики, тройки играют роль грамматических правил.) Таким образом, конечный автомат может быть представлен произвольным Р и с. 3. Граф для диаграммы состояний автомата. Поведение автомата описывается тройками @,6,0), A,0,1), B,1,0), C,2,1), D,1,4),E,1,4),@,4,3),G,4,5). (8,5,4), (9,5,5), (9,5,6). Состояние So является начальным и конечным состо- состоянием: состияння Sa и S3 могли бы быть опушены (и обычно опускаются), так как они не играют никакой роли в порож- порождении предложений. конечным ориентированным графом, ребра которого помечены сим- символами из А. Идя вдоль графа от50До первого возвращения в So по разрешенным путям, мы порождаем предложение #х#, где х— цепочка, состоящая из последовательных символов, помечающих стрелки, пройденные нами в этом пути. Для наших целей несущественно представление автомата как источника, порождающего предложение символ за символом при Движении от состоягня к состоянию, или как читающего устройства, Формальные свойства грамматик 131 переходящего из состояния в состояние, когда оно воспринимает каждый последовательный символ допускаемого им предложения. Это зависит просто от интерпретации обозначений. В любом из этих двух случаев для вышеописанных систем справедливо следующее определение предложения. Определение 1. Цепочка символов х есть предложение, порождаемое конечным автоматом F, тогда и только тогда, когда существует последовательность символов (ар,,..., ар,) в алфавите автомата F и последовательность состояний (STl,..., S^r+\) авто- автомата F, такая, что: 1) Yi=Tr+i =0; 2) f, Ф0 для 1+1 3)(Рг, Y(, Y'+i) является правилом F для каждого i ^/) 4) x=#a9i... йрг #. Любое множество предложений, порождаемое конечным ачтомя- том7Т>удё"м~называть регулярным языком. Термин, более принятый в литературе для этих множеств,— это регулярные события (см. работы [30, 53]; эквивалентность различных формулировок была доказана в работах [5, 14]). Заметим, что механизм М движется влево при каждом переходе из состояния в состояние, что единичный символ а0 может занимать клетку на ленте и что команда (i, /, k) применима к М тогда и толь- только тогда, когда он находится в состоянии S} и читает символ at. Эквивалентно можно было бы условиться, что а0 не может занимать клетку на ленте, что команда («, /, k) применима, когда М находит- находится в состоянии Sj и когда либо (-0, либо М читает символ а„ и что лента движется влево только тогда, когда применяется команда (I, \, k), где 1=^=0. В этом случае команда @, /, k) может быть истол- истолкована как позволяющая переход из Sj в Sk независимо от вход- входного символа и без движения влево входной ленты. Отметим, что при такой формулировке механизм М будет блокирован, только если он находится в состоянии Sj и наблюдает символ в,, для ко- которых он не имеет команды (I, /, k), и если он, кроме того, не имеет команды @, /, k). Приводя предложения, порожденные этими или другими видами автоматов, мы обычно будем опускать граничный символ +г. Два конечных автомата эквивалентны, если они порождают один и тотже~язь1к". Автомат называется детерминированным, если не~суш.ествУвт~ДвУх команд (i, /, k) и (s, /, /), где 1гф1, и не сущест- существует команды @, /, k), где 1гф0 (т.е. пустой переход возможен только при возвращении в So). Состояние детерминированного ав- автомата однозначно определяется (за исключением возможного воз- возврата в So) цепочкой символов, воспринятой им на входе, и состоя- состоянием, с которого он начал свою работу. Имеется много результатов, относящихся к этим автоматам. Приведем без доказательства две теоремы, которые понадобятся нам в дальнейшем [13, 53].
132 Н. Хамский Теорема I. По заданным конечным автоматам Flt F2 можно построить конечные автоматы Gb Ga, G3, такие, что Gl есть де- детерминированный автомат, эквивалентный Flt G% допускает те и только те цепочки, которые отбрасывает (т. е. не допускает) Fx, а 0г допускает в точности те цепочки, которые допускает Рг или F2. Следовательно, множество всех регулярных языков в заданном алфавите А образует булеву алгебру. Заметим к случаю, что для детерминированных автоматов можно было бы вообще избежать появления «пустого» перехода, переформулировав «допустимость цепочки х» в терминах прихода устройства в одно из множества выделенных конечных состояний вместо возвращения в начальное состояние. Эти два определения остаются эквивалентными, если только допустить любое число конечных состояний. Самый важный результат, касающийся регулярных языков, — это "теорема Клини о структурной характеризации [аи]. ^та_тер- бёма~Тгвёрждает, что все (и только) регулярные языки могут быть получены из конечных языков с помощью нескольких простых ко- ретико-миожественных операции! Теорема, таким образом^ дает простой и естественный^способ представления люОого регулярного Приведем эту теорему в несколько отличной формулировке. Для заданного алфавита А определим рекурсивно понятие пред- представляющего выражения следующим образом. Определение 2. 1) Каждая конечная цепочка в алфавите А есть представляющее выражение. 2) Если Х± и Х%— представляю- представляющие выражения, то XXX2— представляющее выражение. 3) Ес- Если Х(, где 1<^ i<^i, суть представляющие выражения, тогда и (Хъ...,Хп)*— представляющее выражение. Это определение задает нам 1) некоторые представляющие вы- выражения, соответствующие цепочкам в Л, и позволяет нам образо- образовывать другие представляющие выражения путем 2) соединения их Друг с другом и 3) разделения их запятой и заключения в скобки, помеченные звездочкой. Теперь мы должны сказать, что же именно представляют эти представляющие выражения. Определение 3. 1) Конечная цепочка в А представляет самое себя (точнее, единичный класс, содержащий только эту це- цепочку). 2) Если Х1 представляет множество цепочек Ец а Х2— множество цепочек ?2, то ХХХ2 представляет множество все- всевозможных цепочек вида VW, где V?Eb a U???2. 3) Если Xit l^'-^i, представляют множества цепочек S;, то (Хг,...,Х^* представляет множество всех цепочек Ух...Ут, таких, что для каждого \<^j^.m cyuificmeyem k (\-^k<0i), такое, что Vt:? ?«. Формальные свойства грамматик 133 Заметим, что, согласно условию 3, представляющее выражение (Х!,...,Х„)* задает не порядок, в котором встречаются элементы Vj, но только п множеств, из которых они выбраны. Разобраться в смысле определения 3 лучше всего можно, рассмотрев диаграммы (а,, а,)' а,(аг) а5 сн*- д д,(аг.азГо4, я,Гяв, "-О Рис. 4. Примеры использования представляющих пырлжений. Слева — представляющие выражения, справа — диаграммы состояний. состояний или части диаграмм состояний, порождающие пред- представляемые множества цепочек. На рис. 4 случаи бив иллюстри- иллюстрируют образование соединения и операции «звездочка» (т.е. образо-
ш Н. Хомскип вание выражения (Хг Х„)*. Случайг показывает сочетание этих операций. Автомат порождает а%а3, а1аф3, ахагаф3.... Случай Э показывает еще более сложный элемент и т.д. Теперь уже может быть сформулирована следующая теорема. Теорема 2. Язык L является регулярным языком тогда и только тогда, когда существуют такие представляющие выраже- выражения Xt, где l<Ji<Ji, что L есть объединение множеств ?;, пред- представленных соответственно выражениями Хъ...,Хп [13]. Доказательство теоремы основано на том, что для любой диаг- диаграммы состояний автомата F можно построить эквивалентную ей диаграмму состояний, представляющую собой сочетание элемен- элементов, таких, как на рис. 4; из этой новой диаграммы непосредственно может быть получено представляющее выражение для языка авто- автомата F. Разумеется, в общем случае при этом получается недетер- недетерминированный автомат. Специальный интересный класс конечных автоматов состоит из автоматов, обладающих тем свойством, что состояние автомата од- однозначно определяется последними k символами входного пред- предложения. Автомат, для которого существует такое фиксированное k, называется k-ограниченным автоматом, а язык, который он по- порождает,— k-ограниченным языком. Допустим, что М есть ^-ограниченный автомат со словарем V, состоящим из D символов. Можно задать его поведение матрицей D"xD, в которой каждый столбец соответствует элементу W?V, а каждая строка — цепочке <р длины k, состоящей из элементов V. Соответствующий элемент матрицы будет равен нулю или единице в зависимости от того, допускает ли автомат элемент W, если он уже допустил цепочку <р. Каждая такая цепочка <р определяет состояние автомата. Это понятие (^-ограниченного автомата) известно в лингвистике в несколько модифицированном виде. Предположим, что элемента- элементами определяющей матрицы являются числа между нулем и едини- единицей и каждый элемент представляет собой частоту, с которой в неко- некотором тексте встречается слово, соответствующее заданному столбцу матрицы, при условии что перед этим встретились k слов, определяю- определяющие заданную строку матрицы. Эта матрица интерпретируется как описание вероятностного ^-ограниченного автомата, порождающего цепочки в соответствии с заданным множеством вероятнос- вероятностей перехода, т.е. если автомат находится в состоянии, опреде- определенном /-й строкой матрицы, что соответствует порожденной по- последовательности символов W\...Wlk , то элемент, стоящий в клет- клетке (I, /), дает вероятность того, что следующее порождаемое слово будет Wj. После того как порождено слово Wj, автомат переходит й W\Wl W П ?>1 jр j р в состояние, определяемое цепочкой W\...Wlh Wj. При ?>-1 такое Формальные свойства грамматик 135 устройство порождает так называемое приближение (?+1)-го по- порядка к тому тексту, из которого были взяты вероятности (см. ра- работы [72, 43]). Мы еще вернемся к этому понятию в разд. 1.2 сле- следующей главы1). Р и с. 5. Конечный автомат, не являющийся ^-ограниченным ни при каком k. Очевидно, не каждый конечный автомат ^-ограничен. Напри- Например, автомат с тремя состояниями, схема которого показана на рис. 5, не является ^-ограниченным ни для какого k. Однако для каждого регулярного языка /.существует 1-ограпиченный язык L* и гомоморфизм /, такой, что L—f(L*) [61 ]. Действительно, пусть L допускается детерминированным автоматом М, в котором нет пра- правила (I, /, 0) при «=/=0(ясно, что такой М всегда существует). Пусть М* имеет входной алфавит, состоящий из символов (а2, Sj), и внутренние состояния [ait Sj 1, где at есть символ из алфавита М, a Sj есть состояние М, при этом [а0, So] есть начальное состояние. Переходы автомата М* определяются переходами М по следующе- следующему принципу: если (I, j, k) есть правило автомата М, то М* может переходить из состояния [а„ S,] (при любом I) в состояние [abSk], если он наблюдает символ {aL,Sk). Пусть теперь L*—язык, допуска- допускаемый автоматом М*. Пусть / — гомоморфизм, отображающий (di, SJ) на at для всех I, /. Тогда L=f(L*) и L* есть 1-ограниченный язык. Предположим теперь, что мы сняли требование, чтобы лента всегда двигалась влево при переходе из состояния в состояние. ') См. сноску 2 на стр. 121.—Прим. red.
136 Н. Хомскип Вместо этого допустим, что направление движения ленты опреде- определяется, так же как и следующее состояние, текущим состоянием и считываемым символом. Поведение такого автомата можно описать множеством четверок (i, /, k, I), где I, j, k суть, как и раньше, ин- индексы соответствующей буквы, одного состояния и другого состоя- состояния, а / есть одно из ( + 1, 0, —1). Следуя Рабину и Скотту [531, можно интерпретировать эти четверки следующим образом. ¦1 Определение 4. Пусть (i, j, k, I) — одно из правил, оп- определяющих работу автомата М. Если его блок управления находит- находится в состоянии Sj, а его считывающая головка стоит пропив клетки, содержащей символ ah то блок управления может перейти в состоя- состояние SA, в то время как лента продвигается на I клеток влево. Такое устройство называется двусторонним автоматом. Будем рассматривать продвижение на —1 клетку влево как про- продвижение на одну клетку вправо. Можно снова сказать, что подобный механизм допускает (порож- (порождает) цепочку, точно так же как это делает конечный автомат. А именно он допускает цепочку х только при следующем условии. Пусть цепочка х записана в подряд идущих клетках ленты, а осталь- остальные клетки заняты символом #. Пусть блок управления находится в состоянии So, а считывающая головка стоит против самой левой клетки, не содержащей #. Предположим, что работа автомата про- продолжается до первого возврата в So, и в этот момент считывающая головка стоит против клетки с символом it. В этом случае счита- считается, что автомат допускает цепочку х. Можно было бы ожидать, что, ослабив требования, которым дол- должен удовлетворять конечный автомат, мы увеличили его порожда- порождающую способность. Однако дело обстоит не так, и мы имеем следую- следующую теорему [53, 731. Теорема 3. Множества порождаемые двусторонними авто- автоматами, также являются регулярными языками. Основная идея доказательства состоит в том, что автомат может избавить себя от необходимости возвращаться второй раз на любой Данный участок ленты, если он, до того как покинуть этот участок, «подумает» обо всех вопросах, которые могут быть заданы в даль- дальнейшем (их число должно быть конечно), тут же «ответит» на эги вопросы и «унесет» с собой таблицу вопросов и ответов, двигаясь вперед вдоль ленты и изменяя ответы, если это понадобится. Этот способ дает возможность построения эквивалентного односторон- одностороннего автомата, хотя и ценой увеличения числа внутренних состоя- состояний блока управления. Формальные свойства грамматик 137 1.3. Линейно-ограниченные автоматы Предположим, что двустороннему автомату разрешается писать символы на ленте при переходах из состояния в состояние. Симво- Символы, написанные на ленте, принадлежат выходному алфавиту А о — = {ao,...,ap,...,aq] (#$А0), где Ai={a!t,,..,ap\ является входным алфавитом. Чтобы описать работу автомата, нам теперь понадо- понадобится множество пятерок (i, /, k, I, m), где четверка (i. j, k, I) оп- определяет двусторонний автомат, а рассматриваемый символ a-t за- заменяется на ат (который, разумеется, может и совпадать с ог), когда автомат переходит из состояния Sj в состояние Sk. Следуя в основных чертах Майхиллу [441, имеем следующее определение. v Определение 5. Пусть (I, j, k, I, m) — одно из правил, определяющих работу автомата М. Если его блок управления нахо- находится в состоянии Sj, а его считывающая головка стоит против клетки, содержащей символ alt то блок управления может перейти в состояние Sk, в то время как лента продвигается на I клеток влево, а рассматриваемый символ at заменяется на ат. Такое устрой- устройство называется линейно-ограниченным автома- автоматом. Допустимость цепочки определяется так же, как и выше. В ли- линейно-ограниченном автомате лента используется не только в ка- качестве входа, но и в качестве памяти. Действительно, если такой автомат М имеет на входе заданную цепочку х, то в его распоряже- распоряжении имеется память, объем которой определен числом сЦх) + д, где q — заданная память блока управления, с — константа (за- (зависящая от мощности выходного алфавита), а Цх) — длина цепоч- цепочки х. Следовательно, он является простым потенциально бесконеч- бесконечным автоматом и, как мы увидим далее, может порождать и нере- нерегулярные., языки. При изучении поведения автомата иногда оказывается удобным в целях наглядности приписать ему некоторую дополнительную бо- более сложную структуру. Так, можно рассматривать какое-либо ус- устройство как состоящее из отдельных частей, воплощающих раз- различные аспекты его поведения. В частности, можно считать, что линейно-ограниченный автомат имеет две отдельные бесконечные ленты, одну исключительно для входа, другую — рабочую, причем на второй ленте имеется ровно столько клеток, доступных для за- записи, сколько занято символами входного алфавита (но не симво- символом #) на входной ленте. Можно также считать, что имеется не- несколько независимых рабочих лент этого вида. Эта модификации требуют соответственного изменения списания работы блока управ- управления, но их нетрудно описать таким образом, чтобы порождающая способность рассматриваемого класса автоматов осталась преж- прежней.
138 И. Хомский \ 4 Автомат с магазинным накопителем (устройство PDS) Рассмотрим следующий специальный класс линейно-ограиичен- ных автоматов, представляющий особый интерес. Пусть автомат М имеет две ленты, одну — входную, другую — ленту памяти. Блок управления может считывать символы с входной ленты и с ленты памяти и записывать символы на ленте памяти. Входная лента может двигаться только в одном направлении, скажем, справа на- налево. Лента памяти может двигаться в обоих направлениях. Сим- Символы входного алфавита Ai могут появляться на входной ленте, символы выходного алфавита Ао могут считываться или записы- записываться на ленте памяти; алфавиты Л; и Ао такие же, как выше. Мы предполагаем, что Ао содержит выделенный символ a$Ai , который будет использоваться только в начале и в конце работы устройства; каким способом, будет явно определено ниже. В разд. 1.4— 1.6 единичный элемент алфавитов Ао и Ai обозначается че- через е вмгсто аа. Другие символы Ао мы продолжаем обозначать at,..-Aq- Алфавиты Л/ и Л о рассматриваются как «универсальные алфавиты», независимые от конкретной машины. Мы определяем ситуацию машины как тройку (a, S(, b), где а — символ, считываемый с входной ленты, S;— состояние блока управ- управления, а Ь — символ, считываемый с ленты памяти. Каждый шаг работы зависит в общем случае от всей ситуации машины. При начальной конфигурации ленты-машины входная лента со- содержит символы ар, ,...,арк (где теперь уже (^=?0); они записаны в подряд идущих клетках ленты и ограничены с обеих сторон симво- символами #; блок управления находится в состоянии So и наблюдает самый левый символ а,з, цепочки х—а^^..щк (как па рис. 2). Рас- Рассматриваемая клетка ленты памяти содержит о, а все остальные ее клетки содержат #. Таким образом, в начальной конфигурации автомат находится в ситуации (ар, ,S0, #). Автомат продолжает свою работу способом, описанным ниже, до первого возвращения bS0. Входная цепочка х допускается автоматом, если в момент воз- возвращения как на входной ленте, так и на ленте памяти наблюдается символ #, т.е. если автомат находится в заключительной ситуации (#,S0,#). Специальное свойство этих устройств, отличающее их от линей- линейно-ограниченных автоматов общего вида, заключается в следующем. Когда лента памяти движется на одну клетку вправо, предыдущий рассмотренный символ как бы «стирается». Когда лента памяти дви- движется на k клеток влево, открывая k новых клеток, то в этих клет- клетках записываются последовательно k символов из Ао, все отлич- отличные от е. Когда лента не движется, ничто не записывается и ничто не стирается. Поэтому на каждом шаге работы машины только са- самый правый символ ленты памяти доступен для рассмотрения. Сим- Символ, записанный на ленту последним, считывается с нее первым. Формальные свойства грамматик 139 Следовательно, лента памяти обязательно будет совершенно пуста [blank] (т.е. будет содержать только #), если достигнута заключи- заключительная ситуация (#, So,#). Устройство М, которое ведет себя описанным выше образом, мы будем, следуя Ньюэллу.Шоу и Саймону [471, называть автома- автоматом с магазинной памятью или автоматом PDS (pushdown storage automaton). Эта система памяти нашла широкое применение в программировании; в частности, многие авторы отмечают, что она весьма полезна при машинном синтаксическом ярялиг"* и^к^ При- Причины этой полезности, так же как и ограничения, присущие теории таких автоматов, станут вполне ясны, когда мы увидим, что она представляет собой, в сущности, другой вариант теории бесконтек- бесконтекстных грамматик (ср. разд. 4 предыдущей главы). Отметим, что автомат PDS, возможно с недетерминированным блоком управления, есть тот самый механизм, который выполняет «предсказусмостный анализ» в смысле И. Роудес (см. работу [48]). Следовательно, и эта теория также является в основном вариантом теории бесконтекст- бесконтекстных грамматик. Перейдем теперь к явному определению работы автомата PDS. Мы предполагаем, выбирая одну из двух эквивалентных формули- формулировок, приведенных выше (стр. 127), что е не может появляться ни в клетках входной ленты, ни в клетках ленты памяти. Тогда мы расширяем определение «ситуации» так, чтобы были допустимы тройки (е, S;, b), (a, St, e) и (е, S;, e), и говорим, что, когда автомат находится в ситуации (a, St, b), он одновременно находится в си- ситуации (е, Sit b), (a, Sit ё) и (е, St, e), т.е. любая команда, примени- применимая в ситуациях (е, S;, b), (a, S( , е) и (в, St, e), будет применима, когда устройство находится в состоянии S; и рассматривает символ а на входной ленте и символ Ь на ленте памяти. Входная лента дей- действительно продвигается влево только тогда, когда применяется команда, содержащая в качестве символа на входной ленте некото- некоторое a=f=e. Определим функцию Цх) (читай: «длина х») для некоторых це- цепочек х следующим образом; М°) =—1; ^(е)=0; Цгас)—Цг) + 1, где го,- есть цепочка в алфавите Ао— (°(, A<^<7). Каждая команда автомата PDS может теперь быть задана в стандартной форме (a, S,, Ь) -» (S,-, х), A) где а^А/ , Ь?А0, х—а или х есть цепочка в алфавите Ао—1°), а / — О тогда и только тогда, когда Ь^а=х. Команда вида A) при- применима, когда механизм находится в ситуации (a, Sh b), и ее при- применение дает следующий результат: блок управления переходит в состояние Sj\ входная лента движется на X (а) клеток влево; симво- символы х печатаются последовательно в клетках, находящихся вправо
140 Н. Хомский от клетки, рассматривавшейся в предыдущий момент на ленте па- мяти (в частности, если x=ajl...ajm, то ajhпомещается в k-й клет- клетке справа от клетки, рассматривавшейся в предыдущий момент, замещая содержимое этой клетки), в то время как лента памяти движется на Цх) клеток влево. Таким образом, если x=j=a, то теперь устройство будет стоять (иа ленте памяти) против самого правого символа цепочки х; если х=е, то оно останется против Ь; если х=о, то оно будет стоять против клетки слева от Ь. Далее, мы полагаем, что содержимое каждой клетки ленты памяти правее рассматрива- рассматриваемой клетки автоматически «стирается» (т.е. заменяется на #). В каждый данный момент мы определяем содержимое леиты памя- памяти как цепочку, стоящую влево от рассматриваемого символа (включая и его), и говорим, что лента памяти содержитэту цепоч- цепочку. Точнее, если цепочка # ар, ...ар„ записана в подряд идущих клетках ленты памяти, причем аря занимает рассматриваемую клет- клетку, то цепочка ар,...ар„ есть содержимое ленты памяти. Если рас- рассматриваемый символ ленты памяти есть #, мы говорим, что лента содержит цепочку е (ее содержимое есть е) или -лента пуста. Отметим, что когда автомат М применяет команду A), входная лента движется на одну клетку влево, если афе, и не движется, если а~е. Далее, если М наблюдает # на входной ленте, команда A) применима, только если а=е. Из условия «/=0 тогда и только тогда, когда Ь= я —х» вытекает, что если М начинает работу из начальной конфигурации, то при первом возвращении в So оно не- непременно окажется в ситуации (a, So,#) при некотором а. Если а=#, автомат М находится в заключительной ситуации, иаблю- дая # на входной ленте и на ленте памяти, и, следовательно, до- допускает цепочку, записанную на входной ленте при начальной конфигурации. В действительности может еще встретиться работа «вхолостую», если имеется команда вида A) а~е=Ь и i=0, но это не повлияет на порождающую способность устройства. Мы можем считать, что устройство блокировано, когда оно достигает заключительной си- ситуации. Его лента памяти будет пуста на этом и только на этом ша- шаге работы. Можно дать более простую характеристику семейства языков, допускаемых автоматами PDS, не ссылаясь явно на манипуляции с лентами и т.п. Если заданы алфавиты Ai и Ао и символы о, опре- определим автомат PDS M как конечное множество команд вида A). Для каждого i пусть будет а-а=е, т.е. о является «правым об- обратным» элементом для каждого элемента. Конфигурация автомата М есть тройка К—(х, Sh у), где S; — состояние, х — цепочка в Л/ и у — цепочка вЛо. Примем за х еще не прочитанную часть вход- входной ленты (т.е. цепочку вправо от читаемого символа, включая и Формальные свойства грамматик 141 его), за у — содержимое ленты памяти, a S; пусть будет состояние в настоящий момент. Если / есть правило вида A), мы говорим,что конфигурация К2 следует из конфигурации Кг по правилу I, если Кг=(ау, Su zb) и Кг=(у, Sj, zbx). Автомат М допускает цепочку ш, если существует последовательность конфигураций К\ /fm, такая, что Kt=(w, So, а), Кт=-(е, So, e) и для каждого К.т имеется правило/, такое, что/Ci+1 следует из Ki по /. Автомат М допускает (порождает) язык L тогда и только тогда, когда L есть множество всех цепочек, допускаемых автоматом М. Память устройства PDS может быть представлена в терминах множества цепочек над внутренним алфавитом; при этом переход от одной внутренней конфигурации к другой будет соответствовать прибавлению и убавлению букв на правом конце цепочки, сопостав- сопоставленной данной внутренней конфигурации. Таким образом, из со- состояния, представленного цепочкой ери, возможен переход только в состояния, представленные цепочками <р или <р°Ф- Поучительно сопоставить устройство PDS, которое при этой интерпретации имеет бесконечное количество возможных состояний, с ^-ограниченным автоматом. Как было показано выше, память ^-ограниченного ав- автомата также может быть представлена в терминах множества це- цепочек над внутренним алфавитом (который в данном случае совпа- совпадает с входным алфавитом). Смена состояний /г-ограниченного ав- автомата соответствует прибавлению буквы справа к цепочке, пред- представляющей состояние, и одновременно стиранию одной буквы на левом конце цепочки. Поэтому все множество возможных состоя- состояний конечно. Устройство PDS представляет собой специальный тип линей- линейно-ограниченного автомата. Для него легко доступны многие зада- задачи, недоступные для конечного автомата, несмотря на то что оно только один раз просматривает входные данные (поскольку вход- входная лента движется только в одном направлении). Рассмотрим, на- например, задачу порождения языка Z/2, состоящего из всех цепочек вида #хсх*#, где х — непустая цепочка из а и Ь, а х*— зеркаль- зеркальное отражение цепочки х, т.е. цепочка х, записанная в обратном порядке — справа налево (ср. с языком L2 в предыдущей главе, разд. 3, стр. 246). Очевидно, что эта задача лежит за пределами воз- возможностей конечного автомата, так как число необходимых для ра- богы состояний возрастает по экспоненте, когда устройство про- просматривает и допускает последовательно символы из первой поло- половины цепочки. Наряду с этим рассмотрим автомат PDS M с входным алфавитом \а,Ь,с\, с внутренними состояниями So, Sj и S2 и следующими правилами, где а принимает значения в множе- множестве (а, Ь\:
142 Н. Хамский (а) (a, So, e)^(S1,a), (б) (а, S1,-e)->(S1, а), (в) (с, Slt <.) -+ (S2, e), (г) (а, S2, а) - (S2> о), (д) (е, Ss> а) -> (So, о). B) Блок управления имеет диаграмму состояний, показанную на рис. 6, где тройка (г, s, t) помечает стрелку, ведущую от состояния S; к состоянию Sj тогда и только тогда, когда имеется правило (r,St, s)-*(Sj, t). Очевидно, что это устройство допускает цепочку тогда и только тогда, когда она принадлежит языку L\. Например, последовательные шаги работы при порождении цепочки #abcbaif показаны на рис. 7. Очевидно, устройство PDS очень хорошо подходит для порож- порождения таких языков, как L2', которые в каком-то смысле имеют единицы (фразы), вложенные друг в друга, т.е. что-то вроде рекур- рекурсивного свойства, названного нами в предыдущей главе (разд. 3) самовставлением. В разд. 4.2 и 4.6 мы увидим, что основное свой- свойство бесконтекстных грамматик (ср. с предыдущей главой, разд. 4), отличающее их от конечных автоматов, состоит в том, что они до- допускают самовставление и симметрии в порождаемых цепочках. Следовательно, можно ожидать, что устройства с магазинной па- памятью будут полезны при построении языков с грамматиками та- такого типа. Этот класс, очевидно, содержит многие известные ис- искусственные языки (например, язык исчисления высказываний и, возможно, также многие языки программирования — см. разд. 4.8). Действительно, весьма нетрудно построить автомат PDS, ко- который будет распознавать или порождать предложения в таких сис- системах. Эттингер [48] указывает, что если оборудовать устройство PDS дополнительной выходной лентой и переделать его команды так, чтобы оно могло отображать входную цепочку на соответствен- соответственную выходную (используя при работе свою магазинную память), то можно заставить его, например, переводить формулы из обыч- обычной скобочной записи в бесскобочную запись Лукасевича и обрат- обратно. В некотором приближении бесконтекстные грамматики непо- непосредственных составляющих частично адекватны естественным языкам; вложенные фразы (самовставление) и симметрии составля- составляют одно из основных свойств естественного языка. Поэтому такие устройства, как PDS, будут полезны при решении различных задач автоматической обработки текстов на естественных языках. Устройство PDS с правилами B) является детерминированным. В случае конечных автоматов мы видим (теорема 1), что для каждо- каждого конечного автомата существует эквивалентный ему детерминиро- /е.а.а) (Ь.е.Ь) (Ь.е.Ь) Рис. 6. Диаграмма состояний для /VI. IЬ, ft, О) Началтая позиция b аШ\ ¦ ¦ ff а й # Позиция 3 .. - »# ... и* а й cl \S> б а ?\*\*\- •М- Позиция 1 • • • t ЩЬ\с\1 ... # tc а а ... Позиция 4 ... i ¦ о» сЪ ... а # So * * ... \*Шъ Позиция 2 ¦ с ... l> a ¦ ¦ S ¦ • a\b * Позиция 5 Позиция 6 Р и с. 7. Порождение цепочки #abcba# устройством PDS
H. Хамский ванный автомат. Однако для автоматов PDS это не имеет места. Так, не существует детерминированного автомата PDS, который попускал бы язык L2={xx*\x* есть зеркальное отражение х) (т.е. I состоит из цепочек, которые получаются, если выбросить сред- средний элемент с из цепочек языка Z,2'), поскольку он никак не смо- сможет узиать, когда достигается середина входной цепочки; однако I порождается недетерминированным автоматом PDS, отлича- отличающимся от устройства B) для L2' заменой правила (в) правилом (a, Su е) -» (S2, а). C) Это сводится к выбрасыванию стрелки (с, е, е)яа рис. 6 и соедине- соединению состояний Sx и Sa двумя стрелками, одна из которых помечена (а,е, а), а другая — (Ь, е, Ь). Устройство применяет команду C) тогда, когда оно «делает предположение» о том, что достигнута се- середина цепочки. Если это предположение не оправдывается, то ра- работа устройства не может закончиться допущением цепочки (точно так же, как если бы входная цепочка не принадлежала языку LJ; если предположение оправдывается и входная цепочка принадле- принадлежит языку Z.2, то работа устройства закончится допущением цг- почки. Мы допустили здесь, что следующий шаг работы устройства ча- частично определяется символом, считываемым с ленты_ памяти. Ин- Интересно изучить вопрос о том, насколько контроль со стороны лен- ленты памяти существен для устройства PDS. Рассмотрим два под- подкласса автоматов PDS, заданные следующими условиями: М есть автомат PDS без контроля, если каждое правило его имеет вид (a, Sh e)-+(Sj,x); M есть автомат PDS с ограниченным контролем, если каждое его правило имеет либо вид (a, S;, e)->(Sy, x), хфа, либо вид (a, Sf, 6)->-(S^, о). Иначе говоря, в автоматах с ограни- ограниченным контролем символ, считываемый с ленты памяти, играет роль только при определении тех шагов, при которых происходит стирание с ленты памяти. Мы видим, что устройство на рис. 6 име- имеет ограниченный контроль. В случае устройства PDS без контроля лента памяти работает лишь как счетчик. Без ограничения общ- общности можно полагать, что ее алфавит содержит лишь один сим- символ. Рассматривая эти семейства автоматов, мы приходим к следую- следующей теореме. Т е о р е м а 4. (а) Семейство автоматов PDS без контроля имеет порождающую способность существенно большую, чем семейство конечных автоматов, но существенно меньшую, чем все семейство Устройств PDS. (б) Для каждого устройства PDS существует эк- эквивалентное ему устройство PDS с ограниченным контролем. Что касается раздела (а) теоремы, то очевидно, что автомат без контроля допускает язык L^ \anbn\ (ср. с разд. 3 предыдущей Формальные свойства грамматик 145 главы), но не допускает ни языка /.2, ни языка L2'. Действительно, эти языки находятся за пределами возможностей любого устройст- устройства с конечным числом бесконечных счетчиков, показания которых независимы и изменяются фиксированным образом при переходах устройства из состояния в состояние (например, счетчик может по- показывать, сколько раз устройство прошло через данное состояние или произвело данный символ), причем решение о допущении или недопущении входной цепочки зависит от элементарных свойств показаний счетчиков (равны ли их показания; стоят ли они на нуле, как в случае магазинной памяти, и т.п.). Хотя устройство с q счет- счетчиками и k состояниями имеет потенциально бесконечную память, за р шагов оно может достигнуть только kp4 различных конфигу- конфигураций состояния н показаний счетчиков, а при прохождении пред- предложений языка Llt имеющих длину 2р, необходимо, чтобы за р переходов можно было достигнуть ^различных конфигураций (воз- (возможность пустых переходов не влияет на это замечание). Точную формулировку вышеописанных рассуждений и описание счетчико- вых устройств можно найти у Шюценберже [601. Раздел (б) теоремы 4 есть следствие некоторых результатов, которые будут установлены ниже (разд. 1.6, теорема 6). 1.5. Конечные преобразователи Допустим, что имеется устройство PDS M, удовлетворяющее до- дополнительному условию, что его лента памяти никогда не движется вправо, т.е. каждое правило М имеет вид (a, St, b)-±(Sj, x), где x=j=a. Начиная с начальной конфигурации, когда входная лента содержит последовательно символы #, ар,,...,ар , #, устройство работает в соответствии со своей программой, двигая ленту памяти влево каждый раз, когда оно печатает на этой ленте цепочку х. Предположим, что работа устройства продолжается до тех пор, пока оно не достигнет ситуации (#,S(, af ) для каких-то I, /, т.е. что оно блокируется точно в тот момент, как прочтет всю входную последовательность. На заключительном этапе леита памяти содер- содержит некоторую цепочку y=waj,и мы говорим, что устройство М преобразует цепочку ар, ,...,ар„ в цепочку у. Будем называть уст- устройство М преобразователем, который отображает входные цепоч- цепочки на выходные и соответственно входные языки на выходные. Обозначим через M(L) множество таких цепочек у, что для неко- некоторого х ? L М преобразует х в у. Заметим, что преобразователь ни- никогда не достигает конфигурации, при которой он видел бы # на ленте памяти. Следовательно, он никогда не может «допустить» входную цепочку в ранее определенном смысле. В случае преобразо- преобразователя лента памяти должна рассматриваться как выходная лента. В случае преобразователя ограничения на формулу правил ав- автомата PDS, касающиеся возврата в So, очевидно, не понадобятся. 1/а П Заказ № 563
146 И. Хомский В самом деле, можно допустить, что правило / преобразователя имеет вид (a,Sl,b)-^(SJ, х) [как в A)], где а ? At, Ь^Аокх есть це- цепочка в алфавите Ао— (о) , опуская дальнейшие ограничения. Очевидно, что лента памяти преобразователя М не оказывает существенного влияния на течение его работы; и действительно, можно построить устройство Т, которое выполняло бы то же самое преобразование, что и М, и при этом удовлетворяло бы дополни- дополнительному ограничению, что следующее состояние определяется только входным символом и настоящим состоянием. Состояния Т записываются в виде (Slt а), где S? — состояние М, a a=j=e — символ его выходного алфавита. Начальное состояние Т есть (So, о). Если М имело команду (a, Sit 6)-*(S/ , х), Т будет иметь команду [a, (Slt b), b]-t-l(SJt с), х), D) где либо х=ус, либо х=е и с=Ь. Поведение Т, очевидно, ничем не отличается от поведения М, но у Т следующий шаг работы зависит только от входного символа и настоящего состояния, т.е. Т пред- представляет собой устройство PDS без контроля. Выбрасывая ненуж- ненужное указание на символ, считываемый с ленты памяти, можно при- придать правилам Т вид (а, ?,.)-» (?,., х), E) указывающий, что когда Т находится в состоянии Е, и наблюдает символ а (если a=f=e) или не наблюдает никакого символа (если а=е) на входной ленте, оио может перейти в состояние Еу, продвинуть входную ленту на X (а) клеток влево, а ленту памяти на Цх) клеток влево, записывая х на вновь открывшихся клетках ленты (если они имеются). Каждый преобразователь можно полностью описать ди- диаграммой состояний, на которой узлы представляют состояния, а стрелка с надписью (а, х) ведет из состояния ?,в ?, тогда и толь- только тогда, когда правило E) есть одно из правил работы устройства. Предположим, что на диаграмме состояний, представляющей преобразователь М, невозможно пройти по замкнутому пути, на- начиная и кончая фиксированным узлом, если идти только по стрел- стрелкам с пометкой (е, х) для некоторого х. Точнее говоря, пусть не су- существует такой последовательности состояний (S«,,...,Sat) устрой- устройства М, что «!=<**, и для каждого ?<k существует хь такая, что (ei Sa/)-»-(S,, , лг() есть правило^. Если это условие выполнено, то число выходных цепочек, в которые может быть преобразована данная входная цепочка, -ограничено, и такое М называется огра- ограниченным преобразователем. Отображение, осуществляемое преобразователем, назовем (ко- (конечным) преобразованием. Преобразование есть отображение цепо- цепочек на цепочки (и, следовательно, языков на языки) такого рода, что оно может быть выполнено строго конечным устройством. Формальные свойства грамматик 147 Если дан ограниченный преобразователь Т, то можно, очевидно, отбросить сколько угодно команд вида (e,Si)-*(Sj, x), не изменяя осуществляемого преобразования, а просто позволив устройству при переходах из состояния в состояние печатать более длинные цепочки. И наоборот, добавив достаточное количество нигде более не употребляемых состояний и достаточно команд вида E) с а=е, можно для каждого (не обязательно ограниченного) преобразова- преобразователя Т построить преобразователь 7", осуществляющий то же ото- отображение, что и Т, но имеющий команды только вида (a, S,) -»¦ (S^b), Ь?А гц?0 Заметим, что из существования такого преобразователя Т не- немедленно вытекает возможность построения «обратного» преобразо- преобразователя Т*, который отображает цепочку у на цепочку х тогда и только тогда, когда Т отображает хна у. Для построения Т* доста- достаточно просто поменять местами входные и выходные символы в командах 7"; если, например, в команде вида E) жесть символ изАо, то надо поменять местами an х. Это сводится к замене каждой над- надписи (а, Ь) на стрелке диаграммы состояний надписью (Ь, а). Итак, для любого преобразователя Т может быть построен обратный ему преобразователь Т*, который отображает цепочку у на х тогда и только тогда, когда Т отображает х на у, и который отображает язык L на множество всех таких цепочек х, что Т отображает х на у ? L. Если Т — ограниченный преобразователь, то Т* может и не быть ограниченным. Если обратный преобразователь Т* также ог- ограничен, то Т называется преобразователем без потери информации. Общее исследование вопросов, относящихся к различным видам преобразователей, см. у Шюценберже и Хомского ([61, 691). Эффект применения преобразователей к бесконтекстным языкам будет рассмотрен в разд. 4.5. Здесь отметим только, что если Т преобразует язык L в V и L есть регулярный язык, то V также бу- будет регулярным языком. Известно также, что для каждого регуляр- регулярного языка L существует преобразователь Tl, отображающий L на фиксированный язык U (а также такой, который отображает U на L), где U — множество всех цепочек в выходном алфавите (в об- обратном случае — во входном алфавите, причем если входной алфа- алфавит состоит только из одного символа е, то преобразователь по оп- определению будет не ограниченным; в противном случае ои всегда может быть сделан ограниченным). Эти и некоторые другие связан- связанные с этими факты становятся очевидными просто из рассмотрения диаграммы состояний. 1.6. Преобразование и автоматы PDS Мы описали преобразователь в виде устройства PDS, которое никогда не сдвигает свою ленту памяти вправо, т.е. никогда не сти- стирает — ни на каком шаге вычислении. Оно переводит входную 1/а И*
148 Н. Хамский цепочку х в выходную цепочку!/. С другой стороны общего вида уст- устройство PDS использует свою ленту памяти для того, чтобы опреде- определить свои дальнейшие шаги, в частности окончательный допуск входной цепочки х. Оно заканчивает вычисление допущением х только тогда, когда при окончании содержание ленты памяти рав- равно просто е, т.е. лента памяти пуста. Следовательно, мы можем пред- представить себе общего вида устройство PDS преобразующим цепочки, которые оно получает, в пустую цепочку е, которая находится на ленте памяти, когда вычисление заканчивается допущением вход- входной цепочки. (Устройство по существу представляет характеристи- характеристическую функцию некоторого множества цепочек.) Мы намереваемся показать, как можно с каждым устройством PDS M связать преоб- преобразователь Т, построенный таким образом, что тогда н только тог- тогда, когда М допускает х (т.е. преобразует ее в ё), Т преобразует х в цепочку у, которая, в том смысле, как это мы определим, сводит- сводится к е1). Предположим, что М есть устройство PDS с входным алфавитом Ai и выходным алфавитом Ао = {е, аъ...,а11 ). Построим новое устройство М' с входным алфавитом А\ и вы- выходным алфавитом Ао, содержащим 2q+\ символов, где Ао = —Ао U {а'ь...,а,'|. Будем трактовать каждый элемент а/ в основ- основном как «правый обратный» для at. Более формально будем гово- говорить, что цепочка х сводится к у в случае, когда имеется последова- последовательность цепочек zx,...,zm (т!>1), такая, что гг—х, zm=y, и для каждого ?<т_имеются цепочки wt, wt и щ ?Ао, такие, что г,= = wt a$t a'p; wt и zul—wlwi . Другими словами, х сводится к у, если х=у или если у может быть образована из х последователь- последовательным стиранием подцепочек aja/. Мы говорим, что цепочка х блокирована, если x=yazal'w, где z сводится к е и либо уа сводится к е, либо а ?Ао— |е."(). Если х блокирована, то для всех v, xv она блокирована и не сводится к е. Мы говорим, что лента памяти блокирована, если цепочка, которую она содержит, блокирована. Новое устройство М' представляет собой автомат PDS, кото- который никогда не сдвигает вправо свою ленту памяти. Оно будет по- построено таким образом, что если М не допускает х, то М' с х иа входе заканчивает работу либо прежде чем прочтет х, либо с бло- блокированной лентой памяти; если же М допускает х, то М' будет работать так, что когда оно прочтет всю цепочку х, лента памяти не будет блокирована, т.е. ее содержание будет сводиться к е. Состояния М' будут обозначаться теми же символами, что и со- Результаты этого раздела н разд. 4.2 получены во время совместной ра- w т-т т.» .-. тг.._ ... П11 ГЛЛ~Д...„,.„Л .. ~~,.о ') результаты ЭТОГО раздела н разд. t.i получены аи bjjcua шпгасиния ра- работы с М. П. Шюценберже. Краткое изложение см. [11 ]. Обобщения и отно- относящиеся к ним результаты см. в работах [64, 65, 67]. Формальные свойства грамматик 149 ответствующие состояния М, и So снова будет начальным состоя- состоянием. Предположим, что К и К'— конфигурации машины-ленты для М к М' соответственно, удовлетворяющие следующим условиям: К достижимо из начальной конфигурации М. Цепочка ш, содержа- содержащаяся на ленте памяти устройства М' в К', сводится к цепочке у, содержащейся на ленте памяти устройства М ъ К. Кроме того, ес- если уфе, то w=zak для некоторого k (т.е. она имеет нештриховаи- ный символ на правом конце). Устройства М и М' наблюдают одну и ту же клетку идентичных входных лент и находятся в одном и том же внутреннем состоянии. В этом случае мы говорим, что К и К' согласованы. Заметим, что когда К а К' согласованы, тогда либо М закончило работу с пустой лентой памяти в (этом случае содер- содержимое ленты памяти М' есть za* ', которое сводится к е), либо М и М' находятся в одной и той же ситуации. Правила в М' определяются правилами в М следующим спо- способом. Пусть ф, St, a,) -» (S,, *) F) есть правило в М. Если хфа, то М' также имеет правило F). Предположим, что х=а. Тогда, если а* —о (в этом случае /=0), то М' будет иметь правило G), а если ац —о, то М' будет иметь правило (8) для каждого г (l^r-^q); G) (8) (Ь, S,, о) -». (So, a'), (b, S,, ak)-+(SJr a'ka'rar). Предположим теперь, что Ki и /С2— конфигурации М, а /(У— конфигурация М', которая согласована с Kv Конфигурация /Сх ие является заключительной, и правило F) в М переводит его из конфигурации Ki в /С2. Ясно, что если хфа в правиле F), то пра- правило в М', соответствующее F), будет переводить М' из К.\ в конфигурацию /С2', которая согласована с /С2- Предположим теперь, что х=а в правиле F). Так как Ki по предположению не является заключительной конфигурацией, то М в Кх должно содержать на ленте памяти цепочку уак для неко- некоторого k. Либо у—е, либо y~zar для некоторого г. Предположим, что у=е. Тогда должно быть аА=о н /=0 в пра- правиле F). Следовательно, М' имеет соответствующее правило G), которое переводит его из /С/ в конфигурацию Кг'¦ Но Ki согласо- согласована с Id, и, таким образом, содержимое ленты памяти М' в Ki должно быть ta, где t сводится к е. Применением правила G) М' переводится в К\, где содержимое ленты памяти равно tea', которое сводится к е. Следовательно, Кг согласуется с Кг- Предположим, что i/=zar. Тогда правило F) переводит М в 10 Заказ К! 563
ISO H. Хамский Хг> в котором леита памяти содержит га,. Так как Кг' согласована с /fj, то содержимое ленты памяти М' в Кг' должно равняться це- цепочке ta, uak, где t сводится к г, а и к е. По построению М' имеет правило (8), соответствующее правилу F); оно переводит М' в Кг', которое идентично Кг в отношении входной ленты и внутрен- внутреннего состояния и в котором лента памяти содержит tar иак ar'ar, что сводится к га, =i/ и Кг согласована с Кг'- В каждом случае мы видим, что если правило F) переводит М из Кг в Кг, то М' имеет правила, переводящие его из Кг' (согласо- (согласованной с Кг) в Ki (согласованную с Кг)- Предположим, что Ki—снова конфигурация М, не являющая- являющаяся заключительной, Кг'— согласованная конфигурация М, что правило /' в М' переводит ЛГ в конфигурацию Кг' и что нет прави- правила в М, переводящего его в конфигурацию Кг, которая согласована с Кг • Ясно, что /' не было выведено (с помощью ранее данной кон- конструкции) из некоторого правила М, имеющего такой же вид, как правило F), где х=^а. Таким образом, мы можем предположить, что /есть правило вида G) или (8) и что /' было получено описанным способом из правила /: {b,St, ak)-+(Sj, о). В любом случае, так как Кг и Кг' согласованы и ни одно из них не является заключи- заключительной конфигурацией, лента памяти М в Кг должна содержать цепочку уак, где у=е или y=zas для некоторого s, и лента памяти М' в Ki' должна содержать цепочку шА, где v сводится к у. Предположим, что /'— правило G). Тогда ак=я и содержимое ленты памяти М' в Кг' есть изо'. Устройство М' заканчивает ра- работу в состоянии So с лентой памяти, содержащей цепочку, которая сводится к у; но так как в(=ак) не может быть напечатана на ленте памяти ни на каком шаге М и так как содержимое ленты памяти М в Кг есть i/a, обязательно у=е. Итак, / переводит М из Кг в кон- конфигурацию Кг, которая согласуется с К?' вопреки предположению. Остается предположить, что /' есть правило (8). Тогда содержа- содержание, ленты памяти М' в Кг' есть vaka'k аг'си, что сводится к уака'ка'гаг и в свою очередь к уа/аг. Если у=е, то лента памяти М' блокирована в Кг'• Предположим, что y = zas. Тогда / перево- переводит М в конфигурацию Кг, в которой лента памяти содержит zas. Предположим, что s—r. Тогда содержание ленты памяти М' в Кг', которое сводится к yar'ar=zafl'' tar, сводится далее к zar=zas. Но в этом случае Кг и Кг' согласованы вопреки предположению. .Следовательно, гфз. Но в этом случае лента памяти М' в.Кг' сно- ва блокирована. Следовательно, в любом случае, если /' есть пра- правило (8), она блокирована. Как мы видели, если лента памяти в какой-то момент блокиру- блокируется, то она остается блокированной в течение всей работы устрой- устройства. Следовательно, если /' применено, то устройство М' не мо- может достичь конфигурации, в которой лента памяти сводится к е Формальные свойства грамматик 15) Коротко говоря, М' делает предположение, что после «стира- «стирания» акфа, перейдя в конфигурацию Кг, устройство М будет на- наблюдать на ленте памяти символ а,. Исходя из этого, оно пишет а'ка'\аг на своей ленте памяти, так что оно теперь тоже наблюдает на ленте памяти а„ «стерев» при этом и ак (знаком а'к), и о, (зна- (знаком а',). Если предположение было правильным, то новая конфи- конфигурация М' согласована с Кг', если оно было неверно, то лента па- памяти М' блокирована и работа М никогда ие закончится с лентой памяти,, содержащей цепочку, которая сводится к е. Но М и М' имеют идентичные начальные конфигурации, если они имеют идентичные входные ленты. Следовательно, если М до- допускает х, то возможно, что М' будет работать, начиная из своей начальной конфигурации с входом х, и закончит работу в ситуа- ситуации (#, So, я') с цепочкой у иа ленте памяти, которая сводится к е. А если М не допускает*, то никакой возможный процесс работы М' из его начальной конфигурации с цепочкой х на входной ленте не может закончиться в ситуации (#, Sj, а) для некоторого а с це- цепочкой, сводящейся к е в качестве содержимого ленты памяти. (За- (Заметим, что содержимое ленты памяти в М' может быть сведено к е тогда и только тогда, когда М' напечатало о' и вернулось в So по правилу, аналогичному 7.) Заметим также, что М' есть устройство PDS, которое никогда не сдвигает свою ленту памяти вправо (никогда не «стирает»). Мы уже показали в разд. 1.5, как в соответствии с каждым устройством та- такого рода мы можем построить эквивалентный преобразователь, ко- который работает независимо от содержимого своей ленты памяти. Пусть Т — преобразователь, построенный из М' таким способом, как это описано в разд. 1.5. Тогда М допускает* тогда и только тог- тогда, когда Т преобразует х в цепочку у, которая сводится к е. Таким образом, мы имеем следующий общий результат. Теорема 5. Если задано устройство PDS M, то можно по- построить преобразователь Т, такой, что М допускает х тогда и только тогда, когда Т преобразует х в цепочку у, сводящуюся к е. Предположим теперь, что L (М) — язык, допускаемый устрой- устройством FDS, обозначенным через М; Т — соответствующий преобра- преобразователь, существование которого гарантируется теоремой 5; К — множество цепочек в еыходном алфавите Т, которые сводятся к е; UI— множество всех цепочек в выходном алфавите Т и Т'— обрат- обратный преобразователь, который отображает х на у в случае, если Т отображает у на *. Тогда ЦМ)=Т'(К ftT(Ui)). Но Ui — регуляр- регулярный язык и, как мы заметили в разд. 1.5, из этого следует, что Т (Ui) тоже регулярный язык. Легко также показать, что К— бесконтекст- бесконтекстный ягык (см. разд. 4 предыдущей главы). 10*
152 И. Хомский В разд. 4.6 мы покажем, что пересечение бесконтекстного языка и регулярного языка является бесконтекстным языком и что ко- конечный преобразователь переводнт бесконтекстный язык в другой бесконтекстный язык. Поэтому ЦМ) есть бесконтекстный язык. В теореме 17 разд. 4.2 мы увидим, что для каждого бесконтекст- бесконтекстного языка существует порождающее его устройство PDS с огра- ограниченным контролем (см. разд. 1.4). Из этих результатов мы можем заключить следующее. Теорема 6. Следующие три положения эквивалентны: а) L допускается некоторым устройством PDS; б) L допускается некоторым устройством PDS с ограниченным контролем [см. теорему 4 FI; в) L —бесконтекстный язык. 1.7. Другие виды ограниченно-бесконечных'автоматов Область ограниченно-бесконечных автоматов имеет огромный потенциальный интерес не только для теории порождающих про- процессов, но также, по-видимому, и для психологии, так как релевант- релевантные психологические модели, представляющие знание и способ- способности организма, как можно ожидать, не будут ни строго конеч- конечными, ни неограниченно-бесконечными в смысле устройств, изуче- изучением которых мы займемся в разд. 1.8. Однако исследование этой области было предпринято совсем недавно, и известны пока лишь немногие начальные результаты. Ритчи [54] исследовал иерархию устройств, обладающих следующим общим свойством: на нижнем уровне иерархии находятся конечные автоматы, а на каждом сле- следующем уровне объем памяти, находящийся в распоряжении уст- устройства, является функцией длины входа, причем эта функция мо- может быть вычислена устройством предыдущего уровня. Ямада [781 изучал случай автоматов «реального времени», которые подчинены условию, что допустимое число шагов работы определяется длиной входа (обзор некоторых его результатов см. в работе [451). Шюценберже [65, 68] развил теорию конечных автоматов, снаб- снабженных множеством счетчиков, которые могут изменять состояния в соответствии с простыми арифметическими условиями на каждом шаге работы. Он [63 ] также связал некоторые из этих результатов с общей теорией бесконтекстных грамматик (см. разд. 4.7). Устрой- Устройства, рассмотренные в разд. 2 и 3, являются ограниченно-бесконеч- ограниченно-бесконечными автоматами, и представляется разумным предсказать, что именно в этой форме математическое изучение грамматик, наконец, найдет свою естественную форму. '/.5. Машины, Тьюринга Каждое устройство М рассмотренного вида характеризуется тем свойством, что объем времени и пространства, которые оно исполь- Формальные свойства грамматик 153 зует для решения какой-либо отдельной задачи(например, при до- допущении или отбрасывании определенных входов) является в неко- некотором смысле заранее заданным. В действительности, наиболее глу- глубокие и наиболее далеко идущие математические, исследования в теории автоматов касаются устройств, которые не обладают этим свойством. Такие устройства, называемые машинами Тьюринга, мы теперь коротко рассмотрим. . : Мы получим машину Тьюринга, если возьмем линейно0грани- ченный автомат, заданный в определении 5, и добавим к его прави- правилам пятерки {#, j, k, I, m), где \фО, имеющие свойства, описанные в определении 5. Эти правила позволяют устройству исполЬЗовать не ограниченные заранее куски ленты влево и вправо в гтоцсссе вычислений, так как символ # может быть заменен теперь на сим- символ алфавита. Обычно также требуют, чтобы эти устройства были детерминированными в том смысле, что для заданной конфигурации машины-ленты имеется лишь один возможный ход; если (i, jt ^ />m) и (I, j, k', /', m') являются правилами, то k—k', l=V n'm'=m'. Можно сказать, что машина Тьюринга допускает (порождает) це- цепочку при условиях, в основном аналогичных поставленным выше. А именно мы пишем на ленте символы цепочки 9 B подряд идущих клетках, а остальную часть бесконечной ленты считаем заполненной символом #. Мы устанавливаем блок управления в состояние So со считывающей головкой, стоящей против самого левого символа ъф # • Если устройство проработало до первого возвращения в St< T0 мы говорим, что машина допускает (порождает) <р. Кроме того' после- последовательность символов, которые теперь стоят на ленте меящу сим- символами #, образует цепочку ф, которую можно назвать Выходом машины. Мы можем, иначе говоря, рассматривать это устройство как частичную функцию, которая переводит f в ф при поставленных условиях. Полученные таким способом устройства своим поведением пол- полностью отличаются от автоматов, рассмотренных в разд. 12 1.7. Так, например, не существует общего способа определить по задан- заданному входу, остановится ли устройство или же будет работать до бесконечности. Далее, не существует общего способа определить путем систематического исследования правил устройства, iiaK дол- долго оно будет работать, если оно допускает входную цепочку, или какой кусок ленты будет использован, прежде чем будет получен ответ. Не существует единого и систематического способа опреде- определения по изучению правил машины Тьюринга, даст ли она вооб- вообще когда-нибудь выходной символ, будет ли ее выход (или мно- множество, которое она допускает) конечным или бесконечным; также невозможно в общем случае определить при помощи некоторого практического приема, будут ли два таких устройства выдавать когда-либо одинаковый выход или же допускать одно и то ае мно-
162 Н. Хомский Формальные свойства грамматик 16S Условие 1. Если tp-vty есть правило G, то существуют не- ненулевые символы а1,...,ат, Ьъ..., Ь„, где т-^п, такие, что у=а1... ...ат и <\( = ЬХ...ЬЛ. Иначе, условие 1 предполагает, что если у-+$ есть правило G, то ф не короче у. Грамматика, удовлетворяющая условию 1, назы- называется грамматикой типа 1. В дальнейшем для каждого условия i, которое будет выдвигать- выдвигаться, мы будем называть грамматику, удовлетворяющую этому усло- условию, грамматикой типа t, язык, порождаемый грамматикой типа i, мы будем называть языком типа i. Самые общие системы под- подстановок считаются грамматиками типа 0. Условия, которые мы будем рассматривать, расположены в порядке возрастающей стро- гостн.т.е. для каждого t грамматика типа i+1 всегда будет удовлет- удовлетворять условию для грамматики типа I, но будет такая грамматика типа I, которая не будет удовлетворять условию типа i+1. Условие 1 налагает существенное ограничение на порождающую способность грамматики. Поскольку для вывода в грамматике типа 1 верно, что каждая строка имеет по меньшей мере такую же длину, как и предыдущая, очевидна следующая теорема. Теорема8. Каждый язык типа 1 представляет собой рекур- рекурсивное множество. Действительно, если задана G — грамматика типа 1 и цепочка х, то лишь конечное число выводов (тех, последние строки которых не длиннае х) должно быть просмотрено, прежде чем мы решим, по- порождается ли х грамматикой G. Однако не все рекурсивные языки порождаются грамматиками типа 1, как непосредственно показы- показывает рассуждение диагональным методом1). Хотя грамматики типа 1 порождают только рекурсивные мно- множества, в некотором смысле онн близки к тому, чтобы порождать любые рекурсивно-перечислимые множества. Для простоты рассуж- рассуждений ограничимся множествами целых положительных чисел (без потери общности), поскольку любое множество конечных цепочек может быть эффективно закодировано множеством целых положи- положительных чисел. Обратимся снова к описанию машины Тьюринга, данному в. разд. 1.8. Рассмотрим машину Тьюринга с алфавитом A, е], где е — единичный элемент (т.е. клетка, содержащая е, рассматрива- рассматривается как пустая, а замена 1 иа е рассматривается как стирание). Можно предположить, что каждая отдельная машина М работает следующим образом: на входе имеется последовательность 1'„ i>l (т.е. i последовательных вхождений 1, окаймленных с обоих сторон бесконечными цепочками символов tt). Машина М начинает ') См. прим. 2 к стр. 285 русского перевода работы [8].— Прим. пере». работу в начальном состоянии So, находясь против самого левого- вхождения 1 на ленте, и продолжает до тех пор, пока не закончит ее в выделенном заключительном состоянии Sf. К этому моменту на ленте содержится цепочка <f, окаймленная символами #, при- причем <р содержит j вхождений символа 1 и k вхождений символа е. Можно перестроить М так, что она не приде! в состояние Sf , пока не будет />1, и без потери общности можно предположить, что, когда М пришла в состояние Sf , она находится против самого ле- левого символа, отличного от #, и что все вхождения 1 предшеству- 1 ют всем вхождениям е (проще говоря, мы всегда можем добавить к любой машине М добавочный компонент, который автоматически переведет ее в эту заключительную конфигурацию, после того как она закончит свою работу). Тогда выходом М, если только М дости- достигает состояния Sf , начиная с выхода 1', будет цепочка V е*(/^1, &>0). Мы уже видели (разд. 1.2), что для некоторых (а может быть, и для всех) входов М никогда не закончит свою работу и что не- невозможен алгоритм, определяющий по правилам М, закончит ли она работу при заданном входе и даже есть ли такой вход, при ко- котором она закончит работу. Если М кончает работу при входе 1' с выходом Vek, то мы говорим, что М отображает число t в число /. Это описание носит самый общий характер, и любая машина Тью- Тьюринга, представляющая частичную функцию (т.е. функцию,которая может не быть определена для некоторых элементов области зада- задания этой функции), отображающую целые положительные числа на целые положительные числа, может быть описана таким обра- образом. Хорошо известно, что область определения так описанной машины Тьюринга есть ргкурсивно-перечислимое множество и что каждое рекурсивно-перечислимое множество является областью определения для некоторой машины Тьюринга. Заметим, что такая машина Тьюринга никогда не пишет символа #, хотя она может читать и стирать этот символ (расширяя тем са- самым кусок ленты, доступный для вычислений). Следовательно,, если М при входе 1' кончает работу с выходом Vek, то /-)-?>(. Далее, непосредственно видно, что если, подобно тому как описано в разд. 2, мы построим множество правил подстановки, точно отра- отражающее поведение М, то эти правила будут составлять моногенную грамматику G типа 1. Условие 1 будет выполнено в силу того, что- кусок ленты, используемой к данному моменту, никогда не умень- уменьшается. Если М получает выход Vek при входе 1' , то G выдаст (#501'#)-вывод, заканчивающийся цепочкой #SfW*#, и обрат- обратно. Хотя М может перечислять любое рекурсивно-перечислимое множество (как область определения представляемой ею функции), множество выходов, которые она порождает, рекурсивно. Предположим теперь, что мы выбираем машину Тьюринга и сопоставляем ей грамматику G только что описанным способом.
.164 Н. Хомскип Допустим далее, что мы строим грамматику G*, которая содержит все правила G, и еще следующие четыре правила для порождения «начальных цепочек», необходимых для G: А1. -S.1, -S.1. A2) :Эти правила позволяют дать законченный (#5#)-вывод каждой це- цепочки вида #SO1<#, где ?>1, и только таких цепочек. Следова- Следовательно, полная грамматика G* будет давать законченный (#5#)-вы- вод цепочки #<?# тогда и только тогда, когда <p=S; V'ek (/>1), п для некоторого i, M при заданном входе 1' заканчивает работу с выходом \'ek. Итак, для произвольной машины Тьюринга, перечис- .ляющей рекурсивно-перечислимое множество ? в качестве своей области определения, мы можем построить грамматику типа 1, которая порождает те и только те цепочки вида ^S^ <рф#, для ко- которых ср^Ё, а ф есть цгпочка символов е (длина которой, впро- впрочем, определяется цепочкой ср, где <р? Е). Известно, что проблема распознавания для произвольной машины Тьюринга, является ли •ее область определения пустой, конечной или бесконечной, алгорит- алгоритмически неразрешима. Следовательно, соответствующие проблемы .для грамматик типа 1 также алгоритмически неразрешимы. Теорема 9. Невозможен алгоритм, распознающий по произ- произвольной грамматике типа 1, порождает ли она пустое множество, порождает ли она конечное множество или бесконечное множество ¦ цепочек [58]. По этой же самой причине невозможен алгоритм, определяю- определяющий, появляется ли данная цепочка как собственная часть строки -(#5#)-вывода в G. Далее, поскольку грамматика не дает никаких законченных (#5#)-выводов тогда, когда она эквивалентна грам- грамматике Gini,i с единственным правилом S-»-lSl x), то по теореме 9 невозможно определить, эквивалентна ли грамматика G грамма- грамматике GmiU, а значит, и в общем случае. Теорема 10. Невозможен алгоритм, определяющий эквива- эквивалентны ли заданнь1е две грамматики типа 1 158]. Впрочем, для любой алгоритмически неразрешимой проблемы машины Тьюринга можно найти аналогичную неразрешимую проб- проблему, касающуюся грамматик типа 1. Другими словами, мало что можно узнать о свойствах языка, порождаемого грамматикой ти- типа 1 (кроме того, что этот язык непременно рекурсивен), путем сис- систематического исследования правил этой грамматики. ') Достаточно было бы S—*-Sl. — Прим. перге. Формальные свойства грамматик 1SS Условие 1 недостаточно сильно, чтобы позволить установить единообразный метод приписывания С-маркеров порождаемым пред- предложениям, как это было бы желательно. Чтобы обеспечить эту возможность, мы, как было замечено в разд. 4 предыдущей главы, должны потребовать, чтобы на каждом шаге заменялся только один символ (вместе с некоторыми другими ограничениями, которые, как отмечено, ие влияют на порождающую способность). Эти сооб- соображения приводят нас к рассмотрению более строго ограничиваю- ограничивающего условия. Условие 2. Если <р-+'|> есть правило, то существуют це- цепочки Xi> Ха> Л, га (где А — отдельный символ и ш непуста), такие, что <p = XiAx« « Ф=Х1тХ«- В грамматике типа 2 каждое правило ср—»-ф (т.е. хИХа"*" "*Xi mZs) может рассматриваться как утверждающее, что А мо- может быть заменен на ш в контексте Xi—Хг. где, разумеется, Xi или Хз могут быть пусты. Мы будем говорить о грамматиках, удов- удовлетворяющих этому условию, как о контекстных грамматиках. Правила этого вида весьма обычны в существующих грамматиче- грамматических описаниях. Они могут использоваться для указания контек- контекстуальных ограничений на выбор определенных элементов или ка- категорий, как об этом говорилось в предыдущей главе. Для кон- контекстной грамматики можно определить класс Vа нетерминальных символов как содержащий все (и только) такие элементы А, для ко- которых G содержит правило Xi^Z2"*Xi(BZs- В дальнейшем бу- будем предполагать, что это условие всегда выполняется. Из определения ясно, что каждая грамматика типа 2 является грамматикой типа 1, но не наоборот. Тем ие менее условие 2 не ог- ограничивает порождающую способность грамматики. Теорема 11. Если G есть грамматика типа 1, то сущест- существует грамматика G' типа 2, слабо эквивалентная G. Прямое доказательство этого факта см. в работе [8]. Поскольку соответствие, указанное в теореме 11, эффективно, то сразу видно, что неразрешимые проблемы, касающиеся грамма- грамматик типа 1, остаются неразрешимыми, если ограничиться контекст- контекстными грамматиками. Теорема 12. Не существует алгоритма, определяющего по двум заданным контекстным грамматикам, являются ли эти грамматики эквивалентными, порождает ли какая-либо из них пустое, конечное или бесконечное множество цепочек, появля- появляется ли некоторая произвольно выбранная цепочка как часть строки (]iS^r)-ebteoda в какой-либо грамматике или как часть предложе- предложения порождаемого ею языка.
166 Н. Хомский Здесь, как и прежде, мы находим, что мало что можно узнать путем систематического изучения правил подобных систем. Теорема 12 имеет важные последствия для теории грамматик непосредственных составляющих. Любая теория грамматик долж- должна давать общий метод приписывания предложениям их структур- структурных описаний заданной грамматикой, а в случае грамматик непо- непосредственных составляющих это может быть сделано естественным образом лишь в том случае, если каждая грамматика удовлетворяет условию С, гласящему, что не существует символов А, В к цепоч- цепочки ш, таких, что <рЛВф и Т^шВф являются последовательными строчками вывода терминальной цепочки (ср. сноску 3 к разд. 4 предыдущей главы). Поэтому разумно было бы потребовать от пра- правильно построенной грамматики непосредственных составляющих в дополнение к уже наложенным ограничениям, чтобы она удовлет- удовлетворяла условию С. Тогда из теоремы 12 непосредственно следует, что правильная построенность является неразрешимым свойством грамматик непосредственных составляющих. Этого уже достаточно, чтобы отвергнуть теорию грамматик непосредственных составляю- составляющих в ее настоящем виде как возможную теорию грамматик. Ясно, что общая теория грамматик должна давать рекурсивный класс правильно построенных грамматик как возможных кандидатов иа роль грамматик каких-либо естественных языков; другими слова- словами, обязательно должен существовать алгоритм, определяющий, составляет ли данное множество правил правильно построенную грамматику в соответствии с этой теорией. Теория контекстных грамматик в ее современной форме ие удовлетворяет этому требо- требованию (хотя она может быть модифицирована так, чтобы ему удов- удовлетворять, см. вышеуказанную сноску). Заметим, что теория транс- трансформационных грамматик не вызывает этого затруднения, если, как предполагается в разд. 5 предыдущей главы, ее НС-компоиент порождает лишь конечное множество цепочек (аналогично, если ои порождает бесконечное множество достаточно ограниченного вида; это ограничение может оказаться достаточным, если механизм трансформаций будет в достаточной мере усиливать эту порождаю- порождающую способность). В разд. 3 предыдущей главы мы использовали для примеров три искусственных языка Llt La и L3, все со словарем [а,Ь], и до- доказали, что ?>! и L2 обладают грамматиками, которые сейчас мы на- называем контекстными. (В действительности оии обладают грам- грамматиками,, удовлетворяющими условию 2 с пустыми Xi и Ха-) Однако для L3 была построена простая грамматика, которая вооб- вообще ие является (общей) системой подстановок. Мы зиаем, конечно, что грамматика типа общей системы подстановок должна сущест- существовать для языка Ц, поскольку он, очевидно, представляет собой рекурсивно-перечислимое и даже рекурсивное множество. Инте- Формальные свойства грамматик 163 ресно увидеть, однако, что L3, в самом деле, порождается контекст- контекстной грамматикой, хотя и гораздо более сложной, чем требуется для Lj илн Lt. Это следует из одного общего свойства контекстных грамматик, к рассмотрению которого мы сейчас обратимся. Рассмотрим следую- следующее множество правил (общей системы подстановок): Rl: R2: R3: R4: R5: R6: CDA CEA Ea% ?a# aO A - -* CEAA; *-*7ГС?; — $Ea, -~Da#, — Da, - A: S — CDS C?B^ В -» СЕВВ, ВСЕ, A3) В этих правилах переменные о и р принимают значения из {A,B,F}, Так.например, правило R5 в действительности должно рас- рассматриваться как множество из трех правил: AD-+DA: BD^-DB; FD-*DF. К заданной цепочке CDfF#, где ф — любая цепочка из Л и В, правила A3) будут применимы в однозначно определенном порядке (за исключением лишь некоторой свободы в применении правил R6) и в конечном счете дадут цепочку <pCDF<p#, A4) к которой уже ни одно из этих правил не применимо. Короче гово- говоря, правила A3) описывают копирующее устройство. Имея такое копирующее устройство, уже нетрудно использовать его как осно- основу для построения грамматики, порождающей L3. Больше того, поскольку все эти правила удовлетворяют усло- условию 1, это будет грамматика типа 1. Из теоремы 11, следовательно, вытекает следующая теорема. Теорема 13. Существует контекстная грамматика, порож- порождающая 13 [81. Эта грамматика будет значительно более сложной, чем грам- грамматика A2), предложенная в разд. 3 предыдущей главы, в частности потому, что она должна включать множество правил, действующих как копирующее устройство правил A3). Грамматика A2) из разд. 3 предыдущей главы легко может быть переформулирована как тран- трансформационная грамматика. Таким образом, мы имеем здесь про- простой искусственный пример того, какие упрощения часто могут быть получены расширением области грамматической теории на транс- трансформационные грамматики, описанные в разд. 5 предыдущей главы.
168 Н. Хомский Важно отметить, что способность контекстной грамматики по- порождать язык L3 представляет скорее ее недостаток, чем достоинст- достоинство. Для объяснения этого факта рассмотрим реальное функциони- функционирование контекстного копирующего устройства. Его характерное свойство заключается в том, что оно позволяет получить переста- перестановку типа АВ-+ВА в условиях контекстной грамматики; но если при помощи последовательного применения контекстных правил мы осуществим замену АВ на В А, то оказывается, что соответствую- соответствующий С-маркер символа В в цепочке ВА получил тип А (т.е. просле- прослеживается вверх до Л в соответствующем дереве вывода), а символ А в цепочке В А получил тип В. Например, если бы мы захотели ис- использовать подобные правила для преобразования цепочки John will arrive (Джон придет) в цепочку will John arrive (придет ли Джон), мы были бы вынуждены поставить в соответствие цепочке will John arrive С-маркер, содержащий структурную информацию о том, что will в этом предложении является группой существитель- существительного (поскольку оно прослеживается вверх к символу NP, домини- доминирующему слово John), a John является вспомогательным глаголом, что никак не соответствует нашим намерениям. Если бы мы пыта- пытались строить контекстную грамматику для английского языка, то никаким простым и естественным способом нам не удалось бы из- избежать этих совершенно неприемлемых последствий. (Заметим, что если will John arrive выводится из John will arrive при помощи грамматической трансформации вида, описанного в разд. 5 преды- предыдущей главы, то это положение, противоречащее нашим интуитив- интуитивным представлениям, не возникает.) Это замечание предполагает, что было бы важно выдвинуть дальнейшие ограничения для кон- контекстных грамматик, которые исключили бы перестановки и в то же время позволили бы использовать правила, ограничивающие замену некоторых символов наличием определенного контекста. Весьма естественное ограничение, дающее этот эффект, предложил Парих [491. Условие 3. G есть грамматика типа 2, не содержащая правил вида хИХа-^Х^Хг- г^е ш есть отдельный нетерминаль- нетерминальный символ {т.е. u>?Vw). В грамматике типа 3 никакой символ не может быть заменен отдельным нетерминальным символом ни в каком контексте. При этом ограничении невозможно построить последовательность пра- правил, имеющих результатом простую перестановку АВ-+ВА. Следо- Следовательно, копирующее устройство, описанное правилами A3), не может быть построено, и нежелательные последствия не возникнут. Предположительно, L3 не может порождаться грамматикой типа 3. Несомненно, он не может ею порождаться тем способом, который описан выше. Формальные свойства грамматик 169 Условие 3, как оно сформулировано, слишком строго, чтобы выполняться для реальных грамматик естественных языков, но оно может быть слегка изменено так, что, не уменьшая порождающей способности, оно, возможно, окажется небесполезным при постро- построении грамматик для систем, подобных языку. Предположим, что грамматика О содержит правила вида хИХг-^ХЛ'Сг только тогда, когда либо а — терминальный символ (как в условии 3), либо <х доминирует лишь над конечным числом цепочек во всем множестве выводов (и, значит, С-маркеров), возможных в G. В ос- основном это сводится к требованию, чтобы если категория разделя- разделяется на подкатегории, то эти подкатегории являлись бы не типами синтагм [phrase types], а словами или классами морфем. Если счи- считать, что системы обсуждаемого здесь вида вообще сколько-нибудь полезны для грамматических описаний, то, по-видимому, именно класс, удовлетворяющий этому ограничению, будет действительно подходящим. Известно лишь одно нетривиальное свойство грамматик типа 3, именно то, которое устанавливается в теореме 14. Тем не менее этот класс грамматик заслуживает более пристального изучения. Похо- Похоже на то, что условие 3 дает адекватную в разумных пределах фор- формализацию для набора лингвистических понятий, содержащегося в наиболее развитых вариантах метода непосредственных состав- составляющих. 4. Бесконтекстные грамматики Рассмотрим теперь класс грамматик, удовлетворяющих следую- следующему условию. Условие 4. Если о-з-ф есть правило грамматики, то ср есть отдельная (нетерминальная) буква, а '!/ непуста. Таким образом, каждое правило грамматики утверждает, что определенный нетерминальный символ может быть заменен цепоч- цепочкой символов независимо от контекста, в котором он встречается. Назовем грамматику, удовлетворяющую условию 4, бесконтекстной грамматикой. Язык, порождаемый бесконтекстной грамматикой, назовем бесконтекстным языком. Отметим, что, хотя правила бес- бесконтекстной грамматики применяются безотносительно к контексту, между элементами терминальной цепочки могут быть — и обычно бывают — довольно строгие ограничения совместной встречаемо- встречаемости. О бесконтекстных грамматиках уже известно довольно много. Мы даем здесь краткий набросок основных результатов, отсылая читателя при случае к более подробным исследованиям, описанным в других работах, за доказательствами и дальнейшим обсуждением. Непосредственно очевидно, что если в условии 4 отбросить тре- требование, чтобы у была непуста, то порождающая способность бес- 13 Заказ № 563
по Н. Хомский контекстных грамматик останется неизменной (за исключением того, что будет порождаться «пустой» язык {е}). Доказательство см. в работе [4]. Мы можем также, не уменьшая порождающей спо- способности, потребовать, чтобы грамматика не содержала правила вида А-*-В 18], так что бесконтекстные грамматики также удовле- удовлетворяют условию 3. Хотя все бесконтекстные языки (языки типа 4) являются языка- языками типа 3, обратное неверно. Теорема 14. Язык. #аспГ*1" dnb # есть язык типа 3, не порождаемый бесконтекстной грамматикой. Доказательство принадлежит Париху [49]. Гораздо легче най- найти примеры языков типа 2 (языков, порождаемых классом общих контекстных грамматик), которые не могут порождаться бескон- бесконтекстной грамматикой. В частности, среди языков Llt L2 и Z-3, рас- рассмотренных в предыдущем разделе, хотя Lx и Z-2 являются бескон- бесконтекстными языками, 13, конечно, таковым не является (ср. разд. 3 предыдущей главы). Теорема 15. Язык L3 и язык {anbnan} являются языками ти- типа 2, для которых не существует порождающей их бесконтекстной грамматики [8, 59, 4]. Можно получить С-маркер (ср. с разд. 3 предыдущей главы) для цепочки, порождаемой бесконтекстной грамматикой G, непо- непосредственно путем построения новой бесконтекстной грамматики G' со словарем, состоящим из словаря грамматики G и дополнитель- дополнительных терминальных символов: ] и U для любого нетерминального А грамматики G. Если G имела правило A-^-f, то G' будет иметь правило /4-»-U<p]. Грамматика G' порождает цепочку х, содержа- содержащую скобки, задающие структуру составляющих соответствующей цепочки у, порождаемой грамматикой G, причем у может быть по- получена из х опусканием скобок. При некоторых специфических условиях скобка ] может быть опущена без появления неоднознач- неоднозначности, давая своего рода бесскобочную систему записи. Разумеет- Разумеется, система скобок, налагаемая грамматикой G' на терминальную цепочку G, в точности соответствует системе, определяемой нз де- деревьев, введенных в предыдущей главе. Итак, мы можем рассма- рассматривать структурное описание цепочки х как цепочку <р в словаре V*, содержащем Vt н новые символы ] и [а для каждого А ? Vn- Тем же самым методом можно получить С-маркер в контекстной грамматике, если она удовлетворяет условию С, стр. 166. Если кон- контекстная грамматика удовлетворяет условию С, мы говорим, что она правильно построена. Таким образом, контекстная грамматика G правильно построена тогда и только тогда, когда она обладает Формальные свойства грамматик 171 следующим свойством: если <р, ф суть две последовательные строки законченного (#S#)-вывода в О, то существуют единственные це- цепочки а ? Vn и xi, X* ">. такие, что <f'^XiaXi и <|» = Xim3Ca- Расши- Расширив словарь V так, чтобы он содержал скобки, как это было сдела- сделано выше, определим d(<p) (читай: «<р без скобок» или «дебракетизация 9») для любой цепочки <р в этом расширенном словаре, как цепочку, полученную опусканием всех вхождений скобок (вместе с их по- пометками) в цепочке <р- Теперь можно определить сильный у-вывод ф как последовательность <pi>...,?„, в которой 9i—?. <Pn='t и Для каждо- каждого ?>д существуют цепочки ">ъи>г,«'а,ач,">й и символ и, такие, что Vi==wi<W4;?/+1="W«(U5KUL; d(<%)=™6 и d(<»ja<»s)->d (w2 ш5ш3)— правило грамматики G. Если D—сильный AtS4t)-Bbmofl ф в G, а ^(ф) есть цепочка в Vt , то d('l?) есть терминальная цепочка, порождаемая грамматикой G, и ф может считаться С-маркером, единственным образом сопоставленным этой цепочке при помощи вывода D', каждая строка которого есть дебракетизация соответ- соответствующей строки вывода D. Далее, для каждого (#5#)-вывода D цепочки х в G существует соответствующий сильный (#S#)-вывод, оканчивающийся цепочкой, которую можно принять за С-маркер, единственным образом сопоставленный выводом D цепочке х. Таким образом, для правильно построенных контекстных грамматик мы имеем точное определение порождения сильных С-маркеров. Как было замечено выше, правильная построенность, определен- определенная выше, не является разрешимым свойством для контекстных грамматик. Мы можем определить разрешимое свойство правиль- правильной построенности для этих грамматик следующим образом: грам- грамматика G правильно построена, если она не имеет правила вида <рЛВф-*-<рЛо)Вф. В этом случае сильный вывод не обязательно од- однозначно определяется слабым выводом (как эю будет в случае выполненного прежнего определения правильной построенности); но по-прежнему будет однозначно определяться слабым выводом в совокупности с последовательностью правил, использовавшихся при этом выводе (причем в общем случае нельзя обойтись ни без то- того, ни без другого). В действительности, как мы отметили в разд. 4 предыдущей главы, нетрудно выдвинуть эффективные ограниче- ограничения, которые исключат подобную неопределенность, не влияя при этом на слабую порождающую способность (и влияя на силь- сильную порождающую способность только введением некоторой до- добавочной и нигде более не употребляемой категоризации). Однако эти последние условия недостаточно обоснованы. 4.1. Специальные классы бесконтекстных грамматик В этом разделе будут рассмотрены различные подклассы бес- бесконтекстных грамматик, заданные дополнительными условиями на 13*
m Н. Хамский множество правил. Напоминаем, что каждое правило имеет вид Л-> ф, где А— отдельный нетерминальный символ, а ф— не пу- пустая цепочка. Мы продолжаем следовать принятому ранее со- соглашению об обозначениях разд. 4 предыдущей главы. Напомним также, что <p-»i|) тогда и только тогда, когда существует ф-вы- вод i|). Кроме того, нетерминальный словарь Vn состоит в точ- точности из тех символов А, которые появляются в левой части пра- правила грамматики А -*¦<?. Правило называется линейным, если оно имеет вид А->-хВу. Оно npaao-линейное, если имеет вид A-+xB, лево-линейное, если имеет вид А -±Вх. Заключительным правилом называется прави- правило вида А -*-х. В терминах этих понятий мы сейчас определим некоторые виды грамматик. Определение 6. Грамматика G является а) линейной, если каждое ее незаключительное правило ли- линейно; в частности, если оно лево-линейно или право-линейно, б) односторонней линейной, если каждое ее 'не- заключительное правило право-линейно или каждое ее незаключи- незаключительное правило лево-линейно; в) м е т а-л и н е й но й, если все ее незаключительные правила либо линейны, либо имеютвид S->-<p, и если, кроме того, в ней нет правила вида A-*ySty ни для каких А, ер, ty; г) нормальной, если все ее незаключительные правила име- имеют вид A-i-BC, а все заключительные правила — вид А-^-а; д) последовательной, если ее нетерминальный сло- словарь может быть упорядочен как А1,...,Ап таким образом, что для всех 1, / из Af-*-<fA/!f следует, что \~^\. В случае линейной грамматики, если ер есть строка некоторого (#5#)-вывода, то ер содержит не более одного нетерминального сим- символа. Другими словами, имеется лишь одна точка, в которой вывод может ветвиться на каждом шаге. При первом же применении за- заключительного правила вывод заканчивается терминальной цепоч- цепочкой. В мета-линейной грамматике имеется ограниченное число (не более п) точек, в которых вывод может разветвляться. Верхняя гра- граница определяется самым длинным правилом, в котором появляется S, т.е. максимальным числом появляющихся нетерминальных симво- символов. Если применены п заключительных правил, вывод заканчива- заканчивается терминальной цепочкой. Односторонняя линейная грамматика представляет собой просто конечный автомат в смысле разд. 1.2 (см. работу [7]). Это совершен- совершенно ясно в случае односторонней линейной грамматики, все правила которой право-линейиые (либо заключительные). Без потери общ- общности можно предположить, что каждое линейное правило G имеет вид А-^-аВ, где В —неначальный символ 0, и что каждое за- заключительное правило G имеет вид A-hi. Пусть Ах,...,Ап— нетер- Формальные свойства грамматик 173 минальные символы G, причем Аг— начальный символ. Мы можем поставить в соответствие грамматике G конечный автомат F с тем же нетерминальным словарем, что и G, и с состояниями ~А1 А~п, где Ai—начальное состояние. Правила F образуются следующим путем. Если Af+aAj — правило G, то тройка (a,At, Aj ) есть пра- правило F (понимаемое как команда F перейти из состояния Л?в состоя- состояние Aj, когда он считывает с ленты символ а). Если Ai~*-a есть правило G, то тройка (a, At,A^) есть правило F. Тогда G и F кончают работу, породив одну и ту же терминальную цепочку. Точно так же и обратно, правила конечного автомата не- непосредственно задают грамматику с только право-линейными или заключительными правилами. Поскольку, если L — регулярный язык, то L*, состоящий из зеркально отраженных цепочек языка L (т.е. содержащий цепочку а„...а!для каждой al...an?L), также является регулярным языком, очевидно, что каждая односторонняя линейная грамматика пред- представляет конечный автомат и что каждый конечный автомат может быть представлен как односторонняя линейная грамматика. Нормальная грамматика — это грамматика, обычно имеющая- имеющаяся в виду при обсуждении метода анализа по непосредственным со- составляющим, принятого в лингвистике. Заключительные правила А~>-а, составляющие лексикон языка, резко отделены от множества грамматических правил А-+ВС, каждое из которых задает разло- разложение на две составляющие. Введение понятия последовательной грамматики мотивировано той легкостью, с которой порождение в этой грамматике может быть осуществлено при помощи технического устройства. После того как правила разложения некоторого нетерминального символа А были применены и таким образом уничтожены все вхождения А в последнюю строку строящегося вывода, можно быть уверенным, что А не встретится ни в какой дальнейшей строке вывода. Ограни- Ограничения этого рода (хотя для более общего случая, включающего тран- трансформационные правила) были предложены и изучены в приложе- приложении к лингвистическому материалу в работе [40]. Определение 7. Введем обозначения: (L L д )—(L I L порождается линейной грамматикой), L порождается односторонней линейной р р L порождается мета-линейной грамматикой], L д ) грамматикой], ] р р L порождается нормальной грамматикой), L порождается последовательной грамматикой], = [L L порождается бесконтекстной грамматикой). Таким образом, >.,, например, является множеством регулярных языков, как мы только что видели. С точки зрения порождающей
174 Н. Хомский способности эти системы соотносятся друг с другом следующим об- образом1) . Теорема 16. а) XlC= ХоХ т<=.-\ [7, 69]; б) v = T[8]; в) h<=-" = t 120]. Языки Lt и L2 порождаются линейными грамматиками, но, как мы уже видели в разд. 1.1, не порождаются конечными авто- автоматами (односторонними линейными грамматиками). Произведение языков Lt и L2 из X принадлежит Хт , но в общем случае не принад- принадлежит X. Множество правильно построенных формул исчисления высказываний в бесскобочной записи является примером языка, который не имеет мета-линейной грамматики, но порождается бес- бесконтекстной грамматикой S-+CSS, S^NS, S-+V, V-+V, V -«¦ р, A5) где р, р', р",...— пропозициональные переменные, С — знак им- импликации, N — знак отрицания. Языки Ll(=[anbn\) и L2(—\xx*\x есть цепочка в алфавите {а, Ь) и х*— зеркальное отражение х\) принадлежат о, но не при- принадлежат Xj. Примером языка из j, не принадлежащего о, является язык со словарем [а, Ь, с, d\, содержащий предложение *-1 d... da d.. A6) (симметричное относительно с) для каждой последовательности (k, пи...,пк^ целых положительных чисел. Этот язык порождает- порождается грамматикой с правилами S -> adAda, S ->¦ aSa, S ¦ ¦ аса, А -+ ЬАЬ, А -> bdSdb A7) (которые, впрочем, линейны), но не порождается последовательной грамматикой. Так как нормальные грамматики могут порождать любой бес- бесконтекстный язык, общее условие, сводящее грамматику к разло- разложению на бинарныесоставляющие и, отдельно, к лексикону, не ог- ограничивает порождающей способности более, чем ее ограничивает общий класс бесконтекстных грамматик (хотя, конечно, это условие весьма ограничивает системы порождаемых структурных описаний, т. е. ограничивает сильную порождающую способность). ') Знак с понимается здесь как строгое включение, исключающее слу- случай равенства,— Прим. персе. Формальные свойства грамматик 175 4.2. Бесконтекстные грамматики и ограниченно-бесконечные авто- автоматы Мы видели, что бесконтекстные и контекстные грамматики раз- различного вида, рассматривавшиеся нами, по своей порождающей способности превосходят конечные автоматы, но не достигают воз- возможностей общих систем подстановок (машии Тьюринга). В част- частности, мы иашли языки, которые не регулярны, но порождаются линейными бесконтекстными грамматиками (даже с одним нетерми- нетерминальным символом). С другой стороны, мы заметили, что даже кон- контекстные грамматики могут порождать лишь рекурсивные множест- множества и то не все. Грамматики того вида, который мы сейчас рассмат- рассматриваем, принадлежат к категории ограниченно-бесконечных авто- автоматов (разд. 1.3 — 1.7). В случае бесконтекстных языков мы ви- видим, что каждый из них допускается линейно-ограниченным авто- автоматом специального вида, использующим магазинную память (PDS) (ср. с разд. 1.4—1.6), и что такими устройствами могут до- допускаться только бесконтекстные языки. Чтобы показать это, ограничимся рассмотрением нормальных грамматик, это не приведет к потере общности [ср. теорема 16 (б)). Можно также без потери общности допустить, что если А->-ВС есть правило грамматики, то ВфС. Если задана такая нормальная грам- грамматика G, мы можем построить автомат PDS M, который будет до- допускать язык ДО), следующим образом. Для каждого нетерминаль- нетерминального символа А из G блок управления М будет иметь два состояния Аг и Аг. Для каждого правила А->-а из 0 автомат М будет иметь команду (а, А„ е) - (Лг, е). A8) Для каждого правила А -»¦ ВС из G автомат М будет иметь команды: (е, А,, е) -> (В„ А), (е, Вп е) -> (СA е), A9) (в, С,, А)-> (А„ а), где е — единичный элемент. Следовательно, в общем случае М будет недетерминированным автоматом PDS. Его начальное сос- состояние мы обозначим символом ?, i.e встречающимся в G. Уст- Устройство имеет команды (е, Е, о) -»¦ (S,, е) и (е, Sr, о) > (?, о), где S — начальный символ G, позволяющие ему переходить из S в Sj и из Sr в Е, стирая о и закашивая работу. Автомат М допускает цепочку х, порождаемую грамматикой G, систематически обходя кругом дерево, представляющее диаг-
П6 И. Хомский рамму вывода х в G, сверху вниз и слева направо. Для ил- иллюстрации рассмотрим грамматику G с правилами S-+CB, C-+AS, В->¦ b, S-+C, порождающую язык ancbn B0) B1) при помощи таких примерно выводов, как тот, который пока- показан на рис. 9 для цепочки aacbb. Соответствующее устройство PDS М будет иметь команды B2), соответствующие виду A8), и команды B3), соответствующие виду A9): (а, Аь ё) -* (Ап е), (Ь, В„ е) -+ (В,, е), B2) (с, S,, е) -> (Sn e), (е, S,, е) -> (С„ S), (е, С„ е) -> (В„ е), (е, В„ S)-+ (S,, о), ;23) (е, С„ е) -> (Л„ С), (е, Лг, е) -* (S,, е), (е, S,. С)-* (Сг. а). Рис. 9. Типичный вывод предложения в языке B1). При допущении цепочки aacbb с выводом, показанным на рис. 9, М будет последовательно совершать следующие ша- шаги, где первая колонка представляет входную ленту с рассматри- рассматриваемым символом, выделенным жирным шрифтом, вторая ука- указывает состояние блока управления, а третья представляет со- содержимое ленты памяти. Вход Блок управления Память (PDS) 1. aacbb ? о 2. aacbb S, i Формальные свойства грамматик 177 3. aacbb 4. aacbb 5. aacbb 6. aacbb 7. aacbb 8. aacbb 9. aacbb 10. aacbb 11. aacbb 12. aacbb 13. aacbb 14. aacbb 15. aacbb 16. aacbb 17. aacbb 18. aac66# 19. aac66# c, Л Л со" с, ¦ А, . Л S, Sr Сг в, Вг Sr Сг Bt Вг Sr aS aSC aSC aSC aSCS aSCSC eSCSC aSCSC aSCSC B1 aSCS aSCS aSCS cSC aS aS aS a 20. aacbb# E e Очевидно, что устройство допускает все (и только) цепочки, по- порождаемые 0, используя свою ленту памяти для запоминания той части вывода порождаемой цепочки х, которая понадобится на сле- следующем шаге работы, в то время как оно последовательно воспри- воспринимает цепочку х на свози входной ленте. Кроме того, ясно, что эта конструкция является совершенно общей и может быть использо- использована для любой нормальной грамматики. Отметим также, что авто- автомат PDS, определяемый этой конструкцией в терминах разд. 1.4, является устройством PDS с ограниченным контролем. Отсюда мы заключаем следующее. Теорема 17. Для любого заданного бесконтекстного языка L можно построить автомат PDS с ограниченным контролем, допус- допускающий L. Как показал Мэтьюз [41,42], этот результат частично распро- распространяется на контекстные грамматики. Если задана контекстная 12 Заказ № 563
178 Н. Хомский грамматика G, мы определяем прямой вывод (a left-to-right derivation) [соответственно обратный вывод (a right-to-left derivation)]как вывод, удовлетворяющий следующему условию: если (?,ф)—последователь- (?,ф)—последовательные строки этого вывода, то <?=хАи> и ^—х-/у> (соответственно <р=юДя и ty—u>ix). Таким образом, заменяется всегда самый левый (соответственно самый правый) нетерминальный символ. Мэтьюз по- показывает, что можно построить автомат PDS Ml-r, который будет допускать цепочку х тогда и только тогда, когда в G существует прямой вывод цепочки *, и автомат PDS Мц-l, который будет допу- допускать цепочку х тогда и только тогда, когда в G существует обратный вывод цепочки х. По теореме 6 разд. 1.6 отсюда следует, что языки, до- допускаемые устройствами M^-rk Mr-l, являются бесконтекстными. Следовательно, будет бесконтекстным и их объединение (теорема 20, разд. 4.3). Таким образом, если в контекстной грамматике G име- имеются только прямые и обратные выводы, эта грамматика будет по- порождать бесконтекстный язык1). Мы говорим, что контекстная грам- грамматика строго контекстна, если порождаемый ею язык не явля- является бесконтекстным. Тогда мы видим, что необходимое условие того, чтобы грамматика была строго контекстной, состоит в том, что некоторые терминальные цепочки этой грамматики не имеют ни прямых, ни обратных выводов. Нетрудно показать, что эти соображения останутся в силе, если определить прямой вывод (обратный вывод), как такой, в котором заменяемый символ в каждой строке находится не далее чем на оп- определенном фиксированном расстоянии от самого левого (соответ- (соответственно самого правого) нетерминального символа этой строки (см. Мэтьюз, в печати). Таким образом, грамматика будет строго кон- контекстной лишь в том случае, когда некоторые из ее терминальных цепочек имеют только такие выводы, которые ие являются ни пря- прямыми, ни обратными в этом расширенном смысле. Мы говорим, что D есть п-вставленный вывод, если п есть наи- наибольшее число, такое, что D содержит две последовательные строч- строчки хА<?В$Су и xAyw^By, где из цепочек tp.-Ji более короткая имеет длину п. Таким образом, в п-вставленном выводе имеется строка, в которой заменяемый символ стоит на расстоянии я символов либо от самого левого, либо от самого правого нетерминального символа этой строки. Отсюда можно заключить, что для того, чтобы грам- грамматика была строго контекстной, необходимо, чтобы для любого п она могла бы порождать некоторое предложение только при помощи m-вставленных выводов, где т>л. Заметим, в частности, что в вы- ') Предложенное Мэтьюзом [41 ] построение эквивалентного автомата PDS не приводит к цели; однако утверждение, сформулированное в этом пред- предложении, верно, как показал А. В. Гладкий (см. его реферат иа эту работу в РЖ Математика, 1965, 4В427),— Прим. перев. Формальные свойства грамматик 179 водах, производимых «копирующим устройством», описанным в примере A3), имеются строки, в которых заменяемый символ от- отстоит сколь угодно далеко и от самого правого, и от самого левого нетерминального символа. При рассмотрении этих вопросов важно не терять из виду того, что вопрос, является ли данная контекстная грамматика строго контекстной, является неразрешимым, как указал Шамир [71). В разд. 1.6 мы показали, что для каждого автомата PDS M су- существует преобразователь Т, обладающий следующим свойством: Т преобразует вход х в цепочку у, которая сводится к е тогда и только тогда, когда М допускает х. Теперь мы видим, что, следо- следовательно, для любой бесконтекстной грамматики G существует преобразователь Т, который преобразует х в цепочку у, сводящую- сводящуюся к е тогда и только тогда, когда G порождает х. Однако можно по- получить несколько более сильный результат, проведя построение Т непосредственно из G. Определим модифицированную нормальную грамматику как нор- нормальную грамматику, в которой нет пары правил вида А->-ВС, D->-CE ни для каких нетерминальных А, В, C,D, E; т.е. в моди- модифицированной нормальной грамматике для каждого нетерминаль- нетерминального символа можно однозначно определить, появляется ли он в левой нли в правой ветви вывода (никакой нетерминальный символ не появляется и в левой, и в правой ветви). Очевидно, существует модифицированная нормальная грамматика, эквивалентная любой нормальной грамматике, а значит, и любой бесконтекстной грам- грамматике. Допустим, что мы теперь хотим применить конструкцию, анало- аналогичную построению команд A8) и A9), к модифицированной нор- нормальной грамматике G и получить преобразователь Т. Для каждо- каждого нетерминального символа А из G преобразователь Т будет иметь два состояния Л, и Аг. Кроме них, Т имеет начальное состояние Е и команды (e,E)-*-(S,, е) и (е, S,)-*(E,a'), где S — начальный сим- символ G. Входным алфавитом Т является терминальный словарь VV грамматики G. Его выходной алфавит содержит, кроме того, символ а' для каждого a?Vr, пару символов А, А' для каждого нетерми- нетерминального А из Q и пару о,а'. Если Л-»а (a?VV) естьправило G, то Т будет иметь команду (а, А,) -> (А„ Ааа'А'), B5) если Л-5-ВС есть правило G, то Г будет иметь команды (е, А,) -> (В„ А), (е, Вг) - (С„ с), (е. С,) -> (А„ АХ B6)
ISO H. Хомский ¦¦ Так построенный преобразователь Т будет обладать всеми ос- основными свойствами преобразователя, сопоставленного устройству PDS прн помощи построения, приведенного в разд. 1.6, а именно О порождает х тогда и только тогда, когда Т преобразует х в цепоч- цепочку у, сводящуюся к е последовательным выбрасыванием пар а а'. Например, если G такова, как в примере B0), и Т имеет на входе цепочку #aacbb# (с выводом как на рис. 9), Т будет работать в основном так же, как М из B4), и закончит работу цепочкой aSCAaa' A' SCAaa' A' Sec'S' С ВЬЬ' В' S'С ВЬЬ' В' S' а', B7) сводящейся к е, на ленте памяти. Расширим теперь понятие «сводимости» и определим К как класс цепочек в выходном алфавите Ао > которые сводятся к е по- последовательным сокращением пар аа'или а'л(х, а'? Ао). То есть мы теперь рассматриваем от' просто как обратные элементы в сво- свободной группе 0 с образующими а ? Ао . Поскольку грамматика G, исходя из которой был построен Г, была модифицированной нор- нормальной грамматикой, выходная цепочка Т в действительности никогда не будет содержать подцепочек вида а'хх, где* сводится к е. Поэтому это расширение понятия «сводимости» не приведет ни к каким осложнениям, и при этом преобразователь Т сохраняет то свойство, что G тогда и только тогда порождает х, когда Т преобра- преобразует х в цепочку у, сводящуюся к е. 1 При этом изложении мы все время предполагали, как это и есте- естественно (ср. с разд. 4 предыдущей главы), что словарь V, в кото- котором строятся все бесконтекстные грамматики, есть фиксированное конечное множество символов, так что К представляет собой неко- некоторый фиксированный язык в словаре V", состоящем из всех сим- символов V, пары а, а' и символа а' для каждого а ? V. Пусть 9 — гомо- гомоморфизм (т.е. преобразование, осуществляемое с одним состоянием), такой, что <f.(a)->-a для всех а? VV и '$(х)=е Для "(Vr ¦ Пусть U — множество всех цепочек в V. Заметим теперь, что если G и Т тако- таковы, как было описано выше, а L@) — язык, порождаемый G, мы имеем, в частности, что L(G)=? [KTl T(U) ]. Это непосредственно приводит к построению автомата PDS, до- допускающего К; следовательно, по теореме 6 разд. 1.6 К есть бес- бесконтекстный язык. Как было отмечено в разд. 1.6, 1A1) есть регу- регулярный язык. Ниже будет явно показано, что пересечение бескон- бесконтекстного языка с регулярным языком является бесконтекстным языком и что преобразование переводит бесконтекстный язык в бесконтекстный (разд. 4.6). Если К и у таковы, как в предыдущем абзаце, определим <ji(L) для любого языка L как <{i(L) = cc(Kfl L). Подведя итог всему сказанному, мы имеем следующий результат. Формальные свойства грамматик 181 Т е о р е м а 18. Для каждого регулярного языка R гомоморфизм ty(R) deem бесконтекстный язык; для каждого бесконтекстного языка L существует такой регулярный язык R, что L='b(R). Таким образом, бесконтекстный язык однозначно определяется выбором некоторого регулярного языка (т.е. конечного автомата), и каждый такой выбор дает нам некоторый бесконтекстный язык при фиксированных К, <р- Это позволяет определить простые алгеб- алгебраические характеристики бесконтекстных языков. Из теоремы 18 немедленно следует тот результат, что каждый бесконтекстный язык L является гомоморфным образом пересече- пересечения К с некоторым 1-ограниченным языком D. (Напомним, что, как было.показано в разд. 1.2, каждый регулярный язык есть го- гомоморфный образ некоторого 1-ограниченного языка.) Далее, раз- различные категории бесконтекстных языков, которые были опреде- определены выше, легко определяются простыми условиями, налагаемыми на D (подробнее см. в работе [69 1). Из разд. 1.2 известно, что ре- регулярные языки состоят из цепочек в основном с периодической структурой. Из той роли, которую играет К в описании бесконтекстных язы- языков, мы видим, что в некотором смысле структурная симметрия со- составляет фундаментальное формальное свойство цепочек бескон- бесконтекстного языка (и подцепочек, из которых они составлены). Мож- Можно сказать, правда, довольно расплывчато, что в той мере, в какой характер некоторого аспекта упорядоченного поведения определя- определяется условиями, налагаемыми на соседние части (например, ассо- ассоциативные связи), естественно рассматривать организм, имеющий это поведение, в основных чертах как ограниченный автомат; в той -мере, в какой это поведение обладает периодической и ритмической структурой (как в случае примеров, приводимых Лэшли [39] в связи с его критикой теории «ассоциативных цепей»), организм ведет себя подобно строго конечному автомату; в той мере, в какой это поведение проявляет иерархическую организацию и симметрию, организм ведет себя подобно устройству, внутренние свойства ко- которого выражаются бесконтекстной грамматикой. Естественно, эта слишком краткая (и неточная) классификация не исчерпывает всех возможностей для комплексных, упорядочен- упорядоченных или сгруппированных актов поведения, и можно только на- надеяться, что по мере того, как будет развиваться теория более бо- богатых порождающих систем (в частности, для языка, теория транс- трансформационных грамматик), будут обнаруживаться и объясняться все более глубокие и далеко идущие формальные свойства такого поведения. Отметим, что цепочка B7) представляет собой структурное опи- описание входной цепочки waaebbw в соответствии с выводом на рис.9.
№ Н, Хамский Точнее говоря, цепочка B7) превращается в структурное описание вида, описанного иа стр. 170, следующим гомоморфным преобразо- преобразованием: для а ? VT , /(а) =а и /(а') =<?; для а ? VN, /(а)=[, Hf(z')=]. Это сводится к замене Г с командами B5) н B6) преобразователем Т', отличающимся от Г лишь тем, что он не печатает а' для а ? Vr и печатает ] вместо а' для каждого а ? Vn. Как непосредственное след- следствие теоремы 17, имеем теорему. Теорема 19. Если задан бесконтекстный язык L, то можно построить модифицированную нормальную грамматику 0, порож- порождающую L, и преобразователь Т, обладающие следующим свойством; если G порождает х со структурным описанием <р, то Т преобра- преобразует хек; если Т преобразует х в ср и у сводится к е последова- последовательными сокращениями подцепочек вида L а], где a.?VT , то 0 по- порождает х со структурным описанием ср. Преобразователь Г, о котором говорит теорема 19, представ- представляет собой, таким образом, «алгоритм распознавания» (т.е. модель восприятия), который приписывает любому предложению его струк- структурное описание относительно G. Однако это не есть строго конеч- конечный метод распознавания в силу условия, что выходная цепочка должна сводиться к е. Мы еще вернемся (разд. 4.6) к проблеме по- построения оптимальной строго конечной процедуры распознавания для бесконтекстных грамматик. В силу результатов, установленных в этом разделе, существует технический прием построения алго- алгоритма распознавания с помощью автомата PDS для каждой нормаль- нормальной бесконтекстной грамматики, а следовательно, для каждого бес- бесконтекстного языка по крайней мере в одном из его грамматических представлений (а также, как можно предполагать, и во всех). Итак, мы имеем следующие результаты. Существует фиксиро- фиксированный гомоморфизм /, такой, что для любого регулярного языка R можно найти такой 1-ограниченный язык L, что R=f(L). Существу- Существуют фиксированные гомоморфизмы gt, g2, такие, что для каждой дан- данной бесконтекстной грамматики 0', порождающей язык L(G'), существует модифицированная нормальная грамматика G, порож- порождающая язык L(G)=L(G') н порождающая множество структурных описаний E(G), и существует 1-ограниченный язык L, такой, что L{G)-^gi{KnL) и E(G)=&(/(n?), гДе К — фиксированный бес- бесконтекстный язык, определенный выше. Таким образом, слабая порождающая способность любой бесконтекстной грамматики и сильная порождающая способность любой модифицированной нор- нормальной грамматики однозначно определяются этим способом пу- путем выбора определенного 1-ограниченного языка. Мы уже знакомы с различными свойствами трех искусственных языков, введенных в разд. 3 предыдущей главы. Все три языка Формальные свойства грамматик 183 находятся за пределами возможностей конечных автоматов. L3 может порождаться контекстной грамматикой, но не может по- порождаться бесконтекстной. L2 может порождаться бесконтекстной и даже линейной грамматикой, но не может порождаться никакой системой счетчиков (ср. с разд. 1.4). Lx может порождаться системой счетчиков. Кроме того, язык порождается некоторой бесконтекст- бесконтекстной грамматикой тогда и только тогда, когда он допускается неко- некоторым автоматом PDS. Как мы видели в разд. 3 предыдущей главы, основное свойство Li (а именно, что он содержит вложенные зависимости) присуще и естественным языкам. Не мешает отметить, что множество зави- зависимостей такого рода, как в L3, также появляется в естествен- естественных языках. Постал 151] нашел развитую систему это- этого рода в языке могаук (Mohawk), в котором нз последователь- последовательности существительных произвольной длины может быть образован глагол, причем порядок элементов этой последовательности соот- соответствует порядку последовательности существительных вне глагола. Язык, обладающий таким множеством зависимостей, выходит за пределы возможностей бесконтекстной грамматики или устройства PDS безотносительно к любым условиям, налагаемым на структурные описания (ср. разд. 5.1 предыдущей главы) и силь- сильную порождающую способность. Такие подсистемы есть и в англий- английском языке, хотя там они играют менее существенную роль. Так, Соломонов A959, личное сообщение), а также Бар-Хиллел и Ша- мир [5] указывают, что слово respectively (соответственно) дает воз- возможность получить множества зависимостей типа L3 (например, John and Магу 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, т.е. если он будет содержать бесконечное множество частей предложения (синтагм) хи х,г,... и все предложения вида 'jxfiXji, в которых i отлично от / (в то время как язык типа L3 со- содержит все предложения, в которых i совпадает с /, как в упомяну- упомянутом примере языка могаук). Но такого рода ограничения весьма распространены (см., например, работу [27 1 разд. 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 pain- painter than Bill is as a SCULPTOR (Джон больше преуспел как худож- художник, чем Билл как скульптор), но не: *John is more successful as a painter than Bill is as a PAINTER (Джон больше преуспел как ху- художник, чем Билл как художник), которое при помощи обязатель- обязательной трансформации выбрасывания сворачивается в предложение: John is more successful as a painter than Bill is (Джон больше пре- преуспел как художник, чем Билл). Как н в случае наличия подсис- подсистем типа Ls, эти конструкции показывают, что естественные языки превышают возможности бесконечных автоматов или устройств PDS безотносительно к любым замечаниям, касающимся сильной порождающей способности. Как показывают рассмотрения этого рода, для того чтобы обога- обогатить лингвистическую теорию н преодолеть слабые места граммати- грамматики непосредственных составляющих (ср. с разд. 5 предыдущей главы; впрочем, отмеченные там недостатки касаются только силь- сильной порождающей способности), необходимо развивать теорию сис- систем, пригодных для изучения бесконечных множеств цепочек, ие входящих в область действия слабой порождающей способности тео- теории бесконтекстных грамматик. В этих примерах, как и в приме- примерах предыдущей главы, было бы легко установить требуемые пра- правила в форме грамматических трансформаций и таким образом охва- охватить лингвистические явления, выходящие за пределы теории грам- грамматик непосредственных составляющих. Мы уже почти полностью закончили доказательство теоремы 6 из разд. 1.6, которая утверждает, что с точки зрения слабой порож- порождающей способности бесконтекстные грамматики точно соответству- соответствуют недетерминированным автоматам PDS. В разд. 2 мы указали, что общие системы подстановок точно соответствуют машинам Тьюринга, а в разд. 4.1, что односторонние линейные грамматики имеют точно такую же слабую порождающую способность, что и ко- конечный автомат. Как для конечных автоматов, так и для машин Тьюринга недетерминированиость не увеличивает (слабой) порож- порождающей способности. Недавно было показано, что любой язык, допускаемый детерминированным линейно-ограниченным автома- автоматом, является контекстным языком [36]. Курода отметил, что это доказательство распространяется и на недетерминированные ли- Формальные свойства грамматик 185 нейио-ограничеиные автоматы, и, кроме того, доказал, что каждый контекстный язык допускается некоторым недетерминированным лииейно-ограииченным автоматом. Было также указано в работе [4], что двуленточные автоматы, введенные Рабином и Скоттом [53], соответствуют линейным грамматикам в следующем смысле. Пусть у*— отражение у, а а — заданный символ словаря VT. Тогда если Т — двуленточный автомат, допускающий множество пар \{Xj, у:)\ (где л;,, yt — цепочки в словаре Vr—(«)), то сущест- существует линейная грамматика G, порождающая язык {xtay*\\ и об- обратно, если G есть линейная грамматика, порождающая язык \х,ау*\ (xt, у, — цепочки в W—(а)), то существует двулеиточный автомат, который допускает в точности множество пар ((л:,, у*)}. Подводя итог всему сказанному, мы видим, что с точки зрения слабой порождающей способности имеется довольно близкое соответствие между иерархией различных видов грамматик непо- непосредственных составляющих и некоторой иерархией автоматов, а именно общие.системы подстановок соответствуют машинам Тью- Тьюринга, контекстные грамматики — недетерминированным линейно- ограниченным автоматам, бесконтекстные грамматики — недетер- недетерминированным автоматам PDS, линейные грамматики — двулен- точным автоматам и односторонние линейные грамматики — ко- конечным автоматам. Курода также показал, что дополнение (по отношению к фикси- фиксированному словарю) языка, допускаемого детерминированным ли- линейно-ограниченным автоматом, есть контекстный язык н что каж- каждый бесконтекстный язык допускается некоторым детерминирован- детерминированным линейно-ограничениым автоматом. Отсюда следует, что допол- дополнение бесконтекстного языка есть контекстный язык. Мы увидим ниже (разд. 4.3), что дополнение к бесконтекстному языку не обяза- обязательно является бесконтекстным языком и (разд. 4.4) что не су- существует алгоритма, определяющего, является ли оно бесконтекст- бесконтекстным языком или нет. 4.3. Свойства замкнутости относительно операций Регулярные языки замкнуты относительно булевых операций (т.е. объединения, пересечения н дополнения по отношению к фик- фиксированному алфавиту), а также относительно отражения (т.е. пре- преобразования каждой цепочки av..an в цепочку а,,...а^, произве- произведения (т.е. образования языка L1-Li=\x\x=yz,y(^L-l, г ?Lt) и бес- бесконечного замыкания (т. е. образования языка и „L", где L"= — LL- ... -L, п раз). (См. разд. 1.2.) Однако это наблюдение лишь частично оправдывается в случае бесконтекстных языков. Теорема 20. Множество бесконтекстных языков замкнуто относительно операции отражения, произведения, бесконечного замы- замыкания и теоретико-множественного объединения [4 ].
186 Н. Хамский Но пересечение двух бесконтекстных языков уже не обязательно является бесконтекстным языком, а следовательно, и дополнение бесконтекстного языка относительно множества цепочек в фикси- фиксированном алфавите не обязательно будет бесконтекстным языком. Теорема 21. Множество бесконтекстных языков не замкнуто относительно операций теоретико-множественного пересечения и дополнения (относительно фиксированного словаря. V) 159,,4? ¦' Шейнберг_159 ] приводит в качестве хонтрлримфа 'Языки Гх= =(а"а71) и Li={ambna''\, каждый нз которых есть бесконтекст- бесконтекстный язык, но пересечение которых есть множество ценочек (o"a'Ij, не являющееся бесконтекстным языком (пример, приведенный у Бар-Хиллела, Перлса н Шамира [41! в основных чертах совпадает с этим). Пересечение двух множеств может, конечно, быть представ- представлено в терминах объединения и дополнения. Поэтому отсюда следу- следует, что дополнение бесконтекстного языка ие обязательно будет бес- бесконтекстным языком, поскольку объединение бесконтекстных язы- языков бесконтекстно. Отметим, что языки Lx н L2, определенные в предыдущем абзаце, являются мета-линейными и последовательными языками. Объеди- Объединение мета-линейпых языков мета-линейир; объединение последо- последовательных языков есть последовательный язык. Следовательно, этот пример в действительности показывает, что множества Хш и з из определения 7 не замкнуты относительно операций пересечения и дополнения, точно так же как и все множество f, н, кроме того, пересечение двух языков из Хт или двух языков из о не обязательно принадлежит j. Шюценберже установил (личное сообщение), что этот результат может быть усилен до линейных грамматик (грамматик класса X по определению 7). Рассмотрим грамматику Gt с правилами S -> аа Sc, ¦ bSc, и грамматику G2 с правилами S ->- aScc, S -> aSb, ¦be S^ab. B8) B9) Пересечение языков, порождаемых грамматиками Gt и G2, есть множество цепочек [агпЬпа2п), которое не является бесконтекстным языком; но грамматики Gt и G3 линейны. Более того, это грамма- грамматики простейшего типа выше уровня конечных автоматов, а именно линейные с единственным нетерминальным символом. Теперь мы Видим, что даже в этом простейшем случае пересечение порождае- порождаемых языков может не быть бесконтекстным, а класс X также не зам- Формалыше свойства грамматик 187 кнут относительно пересечения или дополнения (он замкнут отно- относительно объединения). Свойства дополнения, вытекающие из предыдущих рассуждений о пересечении, не переносятся непосредственно иа подтипы множе- множества т бесконтекстных языков; хотя из сказанного выше следует, что дополнение языка из X (или Хя, или о) не обязательно принадле- принадлежит X (соответственно 1п или о), но нз этого не следует, что оно не принадлежит f. Однако вполне резонно предположить, что установ- установленный результат распространяется и на эти подсемейства. Очевид- Очевидно, вопрос о том, является ли дополнение линейного языка с един- единственным нетерминальным символом (и с единственным заключи- заключительным правилом S-+C, где с ие появляется нигде в остальных правилах) бесконтекстным языком — это очень важный вопрос остающийся пока открытым. Как мы знаем, класс Хх регулярных языков замкнут относитель- относительно пересечения и дополнения (теорема 1, Г.азд- 1-2). Итак, в итоге мы имеем следующее: все типы бесконтекстных языков, установлен- установленные в определении 7 разд. 4.1, замкнуты относительно операции объединения, но только Xt замкнут относительно пересечения и дополнения. Далее, пересечение языков типов X, Х,„и а не обяза- обязательно вообще будет бесконтекстным (т.е. вообще будет в j). Интересно отметить, что эти свойства не переносятся на кон- контекстные языки. В частности, пересечение двух контекстных язы- языков является контекстным языком [36]. Но вопрос о дополнении контекстного языка остается открытым. 4.4. Неразрешимые свойства бесконтекстных грамматик В разд. 3 мы показали, что многие проблемы, связанные с кон- контекстными грамматиками, оказываются алгоритмически неразре- неразрешимыми. Некоторые, но не все, из этих проблем являются нераз- неразрешимыми также и в случае бесконтекстных грамматик — в дейст- действительности даже простейшего вида, выходящего за пределы конеч- конечных автоматов. Прежде всего приведем теорему. Теорема 22. Если задана бесконтекстная грамматика G, то существует алгоритм, определяющий, является ли язык, порож- порождаемый грамматикой G, пустым, конечным или бесконечным [41. Отсюда следует, что систематическое изучение правил дает боль- больше сведений о свойствах бесконтекстной грамматики, нежели кон- контекстной грамматики. Однако во многих других отношениях мы сталкиваемся с сильными ограничениями, наложенными на то, что может быть определено этим способом. В обзоре, касающемся нераз- неразрешимости, мы будем в основном следовать Бар-Хиллелу, Перлсу и Шамиру [41.
188 Н. Хомский . Известные неразрешимые свойства бесконтекстных грамматик следуют из сведения к проблеме «алгоритмическая неразрешимость которой была доказана Постом [50]), называемой проблемой соот- соответствия. Это может быть сформулировано следующим образом. Предположим, что нам задано множество Е из п пар цепочек в алфавите из по меньшей мере двух букв. Тогда ? = ((•*!. Ух) (*„. Уп)\- Последовательность целых чисел мы назовем последовательностью индексов для Е. Мы говорим, что последовательность индексов / удовлетворяет Е только в том слу- случае, если *|,-.-*«я = й.--.*1я- C0) Проблема соответствия состоит в том, что если задано множест- множество Е, то требуется определить, существует ли последовательность индексов /, удовлетворяющая множеству Е. Пост показал, что эта проблема алгоритмически неразрешима, т. е. не существует алго- алгоритма, определяющего по заданной последовательности Е пар це- цепочек, существует ли последовательность индексов, удовлетворяю- удовлетворяющая Е. Заметим, что если / удовлетворяет Е, то II = (i1,...,im,i1,... ..., tm) также удовлетворяет Е. Следовательно, либо не существует последовательности индексов, удовлетворяющей Е, либо существу- существует бесконечно много последовательностей индексов, удовлетворяю- удовлетворяющих Е, и в силу этого вопрос,» существует ли бесконечное множест- множество удовлетворяющих последовательностей, также алгоритмически неразрешим. Этот факт играет важную роль в последующих рас- рассуждениях. Ограничимся на некоторое время рассмотрением языков в ал- алфавите [а, Ь,с\. Обозначим через L(G) язык, порождаемый грам- грамматикой G; через L — дополнение к языку L (относительно алфа- алфавита >а, Ь, с}; через I^pL,— пересечение Lt и L2; через Z-!U i3— объединение Lx и La и через х*— отражение цепочки х. Допустим, что нам задано произвольное множество Е, У Л C1) где для каждого i xt и у[ представляют собой цепочки в алфавите [а, Ь\. Пусть G(E) — множество правил подстановки S -*¦ xtSy'i C2) Формальные свойства грамматик 189 порождающих язык L[G(E)]. Тогда G(E) есть лииейиая бескон- бесконтекстная грамматика с единственным нетерминальным элементом. Рассмотрим теперь вопрос, порождает ли G(E) цепочку гсг*. Ясно, что это верно лишь в том случае, когда существует последователь- последовательность индексов (iu...,im) для множества Е, такая, что у-У^т- С33) Таким образом, проблема определения, порождает ли произволь- произвольная линейная грамматика G (с одним нетерминальным символом) цепочку вида гсг* для некоторого г, есть в точности проблема соот- соответствия Поста (см. работу [63]). Следовательно, не существует об- общего метода определения, порождает ли заданная бесконтекстная грамматика G (которая может быть даже линейной с одним нетер- нетерминальным символом) некоторую цепочку гсг*, а следовательно, и бесконечное множество таких цепочек (как это было выше замече- замечено), или же она не порождает ни одной такой цепочки. Но пусть теперь Gm есть грамматика S-mSa, C4) порождающая «зеркальный» язык L(Gm) = (zcz*]. Пусть G(E) задано равенством C2). Рассмотрим вопрос: какова мощность множества L@m) [\L [G (E)]? C5) Но это есть в точности вопрос: сколько цепочек вида гсг* порожда- порождает грамматика G(E)? Мы знаем, что ответ на этот вопрос таков: либо ни одной, либо бесконечное множество, и мы только что обна- обнаружили, что не существует алгоритма, определяющего, который из двух случаев имеет место. Следовательно, не существует алго- алгоритма, определяющего для заданного множества Е, является ли L(Gm)n^[G(E)J Пустым илн бесконечным. Отметим далее, что никакое бесконечное подмножество языка L(Gm) не является регулярным языком. Поэтому пересечение L(Gm)ftL[G(I,)] регулярно только в том случае, если оно конеч- конечно, т. е. пусто. Так как не существует алгоритма, обнаруживающе- обнаруживающего этот факт, то не существует алгоритма, определяющего для произвольного Е, является ли L(GJp.L[G(i:)] регулярным языком. Т е о р е м а 23. Не существует алгоритма, определяющего для заданных бесконтекстных грамматик Gt и G2, является ли язык HGj) П ЦО2) пустым, бесконечным или регулярным [4]. В действительности, это верно даже в том случае, когда Gt фик- фиксирована и задана соотношением C4), a G2— линейна с единствен-
190 Н. Хамский ньШ нетерминальным символом (так же, как и Gj). Линейные грам- грамматики с одним нетерминальным символом представляют собой в рамках наших исследований простейшие системы выше уровня ко- конечных автоматов; а хорошо известно, что существует алгоритм, определяющий, является ли пересечение двух регулярных языков пустым или бесконечным (оно всегда регулярно). Мы описали грамматику От в соотношении C4) как грамматику, порождающую «зеркальный» язык с заданной средней точкой. Пусть птг— грамматика, состоящая из правил C4) и правила -ScS. C6) Пусть S±— начальный символ в Gm2. Тогда L(Gm*) состоит из всех цепочек вида хсх*сусу*, где* и у— цепочки в алфавите {а, Ь). Пусть опять ? задано соотношением C1); определим Gm(?) как грамматику, содержащую правила C2) грамматики G(?) и, кроме того, правила St-±a Sl -*. cSc, C7) где Sj— начальный символ. Грамматика Gm(E) вкладывает язык L[G(L)], заданный правилами C2), в «зеркальный» язык. Это зна- значит, что L[Gm(L) ] состоит в точности из тех цепочек вида xcyczcx*, в которых усг порождается грамматикой G(E); 0m (?) является своего рода «слиянием» грамматик Gm и G(E). Рассмотрим теперь пересечение языков, порождаемых грамма- грамматиками О„г и Ота(?) {так же как раньше мы рассматривали пересе- пересечение L(Gm) и L[G(E)]]. Это есть множество L(Gms)nI. [Gm(?) ], состоящее в точности из тех цепочек х, которые удовлетворяют сле- следующим условиям: (i) х = (х; — цепочка в алфавите (а, 61), (ii) xt = х и хл — jci* (так как x?L{G2m)) (in) *1= x\ и x2cx:,?L[G(Z)\ (так как *?/.[0и(Е)]). C8) Тогда, в частности, xL—x3, лг=л4 и хг—хя' . Следовательно, ЦО„г) n L[Gm(Z) ] пусто, лишь когда не существует последователь- последовательности индексов, удовлетворяющей ?, и бесконечно в противном случае, в точности так же, как и раньше (потому что, как мы уже заметили, вопрос о том, существует ли цепочка *jM,?L[G(E)], где хг—х3* , есть в точности проблема соответствия для ?). Следо- Следовательно, не может существовать алгоритм, определяющий, явля- является лн L(Gm2) f) L[Gm(?) ] пустым или бесконечным (имеются только эти две возможности). Формальные свойства грамматик 191 Каждая цепочка в L(Gm2)(\ L[Gm(?) ] имеет вид хсх* схсх*, и легко показать, что никакое бесконечное множество таких цепочек не образует бесконтекстного языка. Следовательно, множество L(Gl)[\L[GmCZ)] представляет собой бесконтекстную грамматику лишь в случае, когда Оно конечно, т. е. пусто, и так как вопрос о непустоте, как было отмечено, неразрешим, то и вопрос, является ли бесконтекстным языком, также неразрешим. Теорема 24. Не существует алгоритма, определяющего по заданным бесконтекстным грамматикам Gl и G2, является ли L(G^j П i(Gj) бесконтекстным языком [4 ]. В действительности, это верно даже в том случае, когда Gj фиксирована в виде Gm2 и G2— мета-линейна (заметим, что Gm2 также мета-линейна). Теорема 23, впрочем, следует из рассуждений, доказывающих теорему 24. Мы рассмотрели языки в алфавите {а, Ь, с], но при соответст- соответствующем кодировании мы легко можем распространить эти резуль- результаты о неразрешимости на языки в алфавитах из двух или более символов (см. работу [4]). В работе [4] доказательство теорем 23 и 24 состоит в основном в следующем. Рассмотрим множество Е, заданное соотношением C1). Пусть Li — язык, состоящий из всех цепочек abk . . .ab cxtl. . . xt cyt[... yucbl a ...b 'a, C9) где (ii,...,ik) и (/i>¦••>//) — последовательности индексов для Е- Легко показать, 4toLs является бесконтекстным языком, порождае- порождаемым грамматикой Gs . Так определенная грамматика Gi будет иг- играть ту роль, которую играла грамматика О„(Е) в кратко описан- описанном выше доказательстве. Рассмотрим теперь язык Lm, состоящий из цепочек Xjcx^xlcx], D0) где хг и хг— цепочки в алфавите {а, Ь\. Язык LM также представ- представляет собой бесконтекстный язык, порождаемый грамматикой GM\ эта грамматика будет играть роль грамматики Gm2 в доказательст- доказательстве, приведенном выше. Заметим теперь, что LM ("| Ls является множеством всех цепочек ablk...abhcxit ¦¦¦\су]к ...y'^cba'1 ...Ь1*а, D1) где X/, ...xt =ус ...г/;', т.е. где il,...,ik есть последовательность индексов, удовлетворяющая множеству Е. Следовательно, в силу
192 Н. Хомский рассуждений, приведенных выше, если существует последователь- последовательность индексов, удовлетворяющая Е, то LM(\LS бесконечно и не является ни регулярным языком, ни бесконтекстным языком; если не существует последовательности индексов, удовлетворяющей Е, то L^fi^-a пусто (и, следовательно, тривиально, является регу- регулярным языком и бесконтекстным языком). Отсюда следует, что не- неразрешимость проблемы соответствия Поста влечет неразрешимость проблемы определения, является ли Z-м П Lz для произвольного множества S пустым, конечным, регулярным языком или же бес- бесконтекстным языком (теоремы 23 и 24). С помощью конструкции, слишком сложной, чтобы приводить ее здесь, в работе [4 ] показано, что для каждого Е дополнение L Е языка La представляет собой бесконтекстный язык. Легко пока- показать, что дополнение LM языка LM есть бесконтекстный язык. Объ- Объединение двух бесконтекстных языков есть бесконтекстный язык. Следовательно, для каждого множества Е язык LM[ M[) MM(\S представляет собой бесконтекстный язык. Дополнение этого языка равно Lm П i-Е, а мы уже отметили, что не существует алгоритма, определяющего, является ли это множество пустым, конечным, ре- регулярным или бесконтекстным. Каждый шаг конструктивен. Сле- Следовательно, мы имеем результат в форме теоремы. Теорема 25. Не существует алгоритма, определяющего по заданной бесконтекстной грамматике G, является ли язык L(G) (дополнение языка, порождаемого грамматикой G, относительно ал- алфавита {а, Ь, с\) пустым, конечным, регулярным или бесконтекст- бесконтекстным [4]. В частности, не существует алгоритма, определяющего, порож- порождает ли произвольная бесконтекстная грамматика все цепочки в своем терминальном словаре, т. е. является ли она универсальной, и не существует алгоритма, определяющего, порождает ли произ- произвольная бесконтекстная грамматика регулярный язык (так как это верно лишь в том случае, когда дополнение языка, порождае- порождаемого этой грамматикой, является регулярным языком). В конце разд. 4.3 мы заметили, что неизвестно, является ли до- дополнение языка, порождаемого линейной грамматикой с одним не- нетерминальным элементом (простейший тип нерегулярного языка), бесконтекстным языком. Если ответ на этот вопрос положителен, то дополнение языка L[G(E)], порожденного грамматикой G(E), заданной соотношением C2), является бесконтекстным язы- языком. Легко показать, что дополнение языка L{Gn), поро- порождаемого Gn из C4), есть бесконтекстный язык. Сле- Следовательно, приведенным рассуждением мы можем показать, что ие существует алгоритма, определяющего, является ли дополнение Формальные свойства грамматик 19S бесконтекстного языка (именно объединение дополнений этих ли- линейных языков) пустым, конечным или регулярным. Более того, дополнение языка Ь[вшг] (см. правило 36) есть бесконтекстный язык и дополнение языка L[Gm(E)] есть бесконтекстный язык, если дополнение языка L[G(?)] есть бесконтекстный язык. Отсюда следует, что мы могли бы полностью доказать теорему 25, не принимая во внимание язык Z.? , заданный соотношением C9), а также конструкцию, которая дает его дополнение, при условии, что дополнение языка, порождаемого линейной грамматикой с од- одним нетерминальным элементом, есть бесконтекстный язык. Одна- Однако этот вопрос, очевидно, не прост. Построение дополнения языка Z.E, данное Бар-Хиллелом, Перл- сом и Шамиром, приводит к доказательству факта, что для опреде- определенного типа линейных грамматик с одним нетерминальным эле- элементом дополнение является линейным. В работе 169] доказано, что для более общего класса линейных грамматик с определенными центральными символами и одним нетерминальным (нменно тем, для которого цепочка, расположенная вправо от центрального символа в порождаемой грамматике, однозначно определяется по цепочке, стоящей слева) дополнение является линейным. Но общий вопрос остается открытым даже для линейных грамматик с единственным нетерминальным символом и указанным центральным символом. Из теоремы 25 немедленно следует теорема. Теорема 26. Не существует алгоритма, определяющего по заданным бесконтекстным грамматикам G± и G2, имеет ли место равенство L{G1)=L(G1) 14]. Если бы такой алгоритм существовал, то можно было бы в об- общем случае определить, является ли /.(GJ универсальным языком в противоречие с теоремой 25. Немедленно также следует, что проб- проблема определения, имеет ли место включение L(G^)<zL(G^), алго- алгоритмически неразрешима (это, впрочем, следует также из теоремы 23, так как L(Gm) есть бесконтекстный язык и LIG(?)] включается в него лишь в том случае, когда его пересечение с L(Gm) пусто|. Заслуживает упоминания еще одно непосредственное следствие этих результатов о неразрешимости. Мы уже заметили (последний абзац разд. 1.5), что язык L регулярен тогда и только тогда, когда существует преобразователь Т, такой, что T(U) — L, где U есть мно- множество всех цепочек в VT ¦ Как мы видели, из теоремы 25 следует, что не существует алгоритма, определяющего, является ли произ- произвольный бесконтекстный язык регулярным,т.е. существует ли пре- преобразователь Т, такой, что T{U) = L. Так как U есть бесконтекстный (даже регулярный) язык, то мы имеем следующую теорему. Теорема 27. Не существует алгоритма, определяющего по> заданным бесконтекстным языкам L1 и L2, существует ли конеч-
194 Н. Хомский ный преобразователь Т, такой, что T(L1)=Li (С. Гинзбург, личное -сообщение). 4.5. Структурная неоднозначность Мы говорим, что бесконтекстная грамматика G неоднозначна, если она порождает цепочку х двумя существенно различными спо- способами, т. е. если она ставит в соответствие цепочке х два различ- различных структурных описания (см. стр. 170). Вопрос оструктурной не- неоднозначности важен с многих точек зрения, и хотя он до сих пор очень мало исследован, все же имеются некоторые результаты в этом отношении. Рассмотрим сначала такой вопрос. Существует ли алгоритм, ¦определяющий неоднозначность бесконтекстной грамматики? Отри- Отрицательный ответ прямо следует из неразрешимости проблемы соот- соответствия. Действительно, предположим, что X, = [xi,yl\ 1<О'<л), где х-, и у, — цепочки в некотором алфавите, скажем, в алфавите {а, Ь). Выберем п новых символов d-,...,dn и построим две грамма- грамматики G, и Gv следующим образом: Gy:Sv->-c, ^ n), <n). D2) Ясно, что Gx и Gy однозначны, no заметим, что последовательность индексов (i\,...,im), такая, что хи ¦ ¦¦Xim—yH •¦¦yim, существует тог- тогда и только тогда, когда Gx и Gy обе порождают цепочку 2, где z = dh . . , dimcx,m ...*;, = d(l... dlmcy'm D3) Таким образом, проблема соответствия для ? имеет положитель- положительное решение тогда и только тогда, когда существует цепочка 2, ко- которую порождают одновременно обе грамматики Gx и Gy, т. е. если неоднозначна грамматика Gxy, которая содержит правила грам- грамматики Gx, правила грамматики Gy и, кроме того, правила S-*SV, S-^S^,, где S является начальным символом грамматики G . Следовательно, не существует алгоритма, определяющего по произ- произвольному множеству ?, будет лн грамматика Gry, построенная указанным способом, неоднозначной. Т е о р е м а 28. Не существует алгоритма, определяющего, яв- является ли бесконтекстная грамматика неоднозначной (Шюценбер- же, личное сообщение). Заметим, что грамматика Gv), принадлежит классу грамматик G, удовлетворяющих следующему условию: Формальные свойства грамматик 195 G — линейная грамматика, обладающая по крайней мере тремя нетерминальными символами, все заключительные правила D4) которой имеют внд а-*с, где с — символ, не встречающийся ни в одном нетерминальном правиле G. Таким образом, мы видим, что проблема неоднозначности не- неразрешима уже для грамматик, удовлетворяющих этому условию. Недавно было показано посредством обобщения проблемы соот- соответствия, что условие D4) может быть ослаблено для случая одного нетерминального символа, и при этом неразрешимость проблемы неоднозначности остается в силе. Действительно, это обобщение позволяет отождествить S, Sx и Sy в грамматике Gxy [23 ]. Таким образом, теорема 28 имеет место для класса минимальных линей- линейных грамматик G, удовлетворяющих условию: G — лннейиая грамматика с единствен- единственным нетерминальным символом S и единст- единственным терминальным правилом S->c, где с D5) не встречается ни в одном из нетерминаль- нетерминальных правил G. Предположим, что G — минимальная линейная грамматика с нетерминальным правилом S-±x,Sy,*, 1<;<". связанным с мно- множеством пар G неоднозначна тогда и только тогда, когда существуют две пос- последовательности индексов I и J /-(.„...,1,), 1-4=J, I - (А, ...,/,), D6) такие, что х„...х,рсу*...у,* =хи...х]1)су*...у,*. Это в свою очередь верно тогда и только тогда, когда 0) хн ¦ ¦ ¦ \ == xh ¦ ¦ ¦ XU • Но рассмотрим вопрос: Если задано множество Е, то существу ки- кили последовательности индексов / и J, задан- заданные соотношениями D6), которые удовлетво- ряют условию D7)? D7) D8)
196 И. Хомский Из теоремы 28, распространенной на минимальные линейные грамматики, следует, что этот вопрос, касающийся однозначной дешифровки, неразрешим. В разд. 1.2 мы отметили, что для каждого конечного автомата мы можем построить эквивалентный ему детерминированный ко- конечный автомат (и, конечно, вопрос об эквивалентности двух конеч- конечных автоматов разрешим). Другими словами, если задана односто- односторонняя линейная грамматика G, то мы можем найти эквивалент- эквивалентную однозначную одностороннюю линейную грамматику. Очевид- Очевидный вопрос состоит в том, верно ли это также для бесконтекстных грамматик в целом. Парих [49] показал, что это неверно. Теорема 29. Существуют бесконтекстные языки, которые не порождаются никакой однозначной бесконтекстной грамматикой. Парих показал, что язык L = [х | х = a" bman'bm или х = а" Ьта"Ьт', п, я', т, т' > 1), D9) не может порождаться никакой однозначной бесконтекстной грам- грамматикой, хотя он порождается множеством правил S-+AB, S-*-DC, А ->¦ аАа, А -» аВа, С -* ЬСЬ, С -* bDb, E0) В-»6, В-^ЬВ, D^a, D ч^аО. В действительности существует линейная грамматика, эквивалент- эквивалентная грамматике E0). Степень неоднозначности, которой обладают цепочки в этой грамматике, равна 2. Другим примером такого язы- языка является множество \апЬтар\п—т или п—р]. Интересная проб- проблема, остающаяся пока открытой, состоит в том, чтобы найти языки более высокой (быть может, неограниченной) степени неустрани- неустранимой неоднозначности. Много важных н нерешенных вопросов мож- можно сразу поставить в связи с вопросом о неустранимой неоднознач- неоднозначности, например ее масштаб, ее соотношения с разрешимостью про- проблемы неоднозначности, насколько богаты те грамматики, где оиа возникает (например, существуют ли минимальные линейные язы- языки, которые неустранимо неоднозначны или существует ли неуст- неустранимая неоднозначность на уровне контекстных грамматик?) И т. Д. Из теоремы 29 возникают некоторые предположения. Очень ин- интересен вопрос, почему естественные языки обладают именно такой Формальные свойства грамматик 197 структурной неоднозначностью, а не другой. Мы можем надеяться получить ответ на этот eongoc в следующем виде. 1. Грамматики естественных языков принадлежат некоторому классу Г порождающих процессов. 2. Язык L обладает достаточно богатыми выразительными сред- средствами, чтобы содержать множество грамматических аппаратов Д, но не Д' (например, класс предложений Е, но не Е'). 3. Грамматика Gf Г, которая выражает Д, но не Д' (которая порождает Е, но не ? ), должна быть неоднозначной, т. е. язык, ко- который она порождает, неустранимо неоднозначен относительно Г. Если бы удалось получить некоторое рассуждение такого ро- рода, то оно было бы важным не только как «оправдание» сущест- существования структурной неоднозначности в L, но также и как пора- поразительное свидетельство независимого (и потому особенно инте- интересного) характера в пользу той общей лингвистической теории, которая претендует на выполнение условия A). Вряд ли нужно подчеркивать, что мы далеки от возможности привести подобное рассуждение для естественного языка, но теорема 29 может представлять собой первый шаг в этом направлении. 4. 6. Бесконтекстные грамматики и конечные автоматы Мы видели, что конечный автомат может быть представлен как односторонняя линейная грамматика и что у такого устройства го- гораздо более ограниченная порождающая способность, чем это мо- может быть у бесконтекстной или даже у линейной грамматики. Мы видели также, что такие элементарные формальные свойства естест- естественных языков, как рекурсивное вложение зависимостей, делают невозможным порождение их конечным автоматом, хотя эти свойст- свойства не исключают их из класса бесконтекстных (даже линейных) языков. Из этих замечаний мы должны заключить, что способно- способности носителя языка не могут быть охарактеризованы конечным ав- автоматом. Грамматика, хранимая в мозгу, не может быть одно- односторонней линейной грамматикой, что вовсе не удивительно; одна- однако поведение говорящего или слушающего должно быть представи- мо конечным автоматом некоторого вида. Говорящий-слушающий имеет лишь конечную память, часть которой он использует для хра- хранения правил имеющейся у него грамматики (множество правил для устройства с неограниченной памятью), а часть—использует для вычисления, фактически производя предложение или «восприни- «воспринимая» его структуру и понимая его. Приведенных соображений достаточно, чтобы показать, как важ- важно достигнуть более полного понимания источника и объема избы- избыточной порождающей способности бесконтекстных грамматик по сравнению с конечными автоматами (хотя бесконтекстные грамма- грамматики, как может быть доказано, не полностью адекватны граммати-
198 И. Хомский ческому описанию естественных языков). Обратимся теперь к ис- исследованию этой проблемы. Посмотрим сначала, какие вопросы касаются связи бесконтекст- бесконтекстных грамматик и ограниченно-бесконечных и конечных автоматов. В разд. 1.6 и 4.2 мы получили некоторые результаты (основан- (основанные частично на результатах, которые еще будут доказаны в дан- данном разделе), относящиеся к этим вопросам. В частности, мы пока- показали, что бесконтекстные языки представляют собой множества, которые допускаются классом ограниченно-бесконечных автоматов, названных нами автоматами PDS. Как было нами показано, из. этого факта следует, что существует чрезвычайно тесная связь между регулярными (односторонними линейными) языками и бес- бесконтекстными языками. Именно расширим словарь V, из которого» построены все бесконтекстные языки, до словаря V", содержащего- V и а' для каждого а? V. Определим К как множество всех цепо- цепочек над V", которые сводятся к е последовательным сокращением ая' и я'а (т. е. обращаясь с а и а' как с взаимно обратными эле- элементами). Положим ср(я)=а для а ? VT , <f (а)=е для o.?VT. Для любого языка L определим ty(L)~if(K(\L). Тогда для каждого ре- регулярного языка L i)(L) является бесконтекстным языком, и каж- каждый бесконтекстный язык определяется как фA.) при некотором! выборе регулярного языка L. Следовательно, семейство Хх регу- регулярных языков прообразуется в семейство i бесконтекстных языков- преобразованием -фТ ^~—-^__ Продолжал исследование соотношений между бесконтекстны- бесконтекстными и регулярными языками, заметим сначала, что существуют бес- бесконтекстные языки, которыв-*-н*котвром смысле гораздо-«больше»,>- чем любой регулярный язык. Теорема 30. Существует бесконтекстная грамматика G, порождающая L(G) и обладающая следующим свойством: если задан конечный автомат Аъ порождающий L(A^)cL(G), то мы можем построить конечный автомат At, порождающий ЦА^), такой, что: a) L(A1)cL(A^)cL(G) и б) ЦАг) содержит бесконечно много- цепочек, не принадлежащих ЦАг) [491. Парих показывает, что этот результат имеет место для бескон- бесконтекстной грамматики, которая дает соотношения (т, п, E1) [В действительности, это также верно для более простой грамма- грамматики G, порождающей только L{G)=[anbman\ m, п>1) (С. Гинз- Гинзбург, личное сообщение). ] Из теоремы 30 мы видим, что в общем случае мы не можем получить бесконтекстный язык L в качестве Формальные свойства грамматик 199- предела возрастающей последовательности регулярных языков, каждый из которых содержит бесконечное число предложений, не входящих в предыдущий член последовательности, и которые все содержатся в L. Предположим теперь, что мы имеем бесконтекстную грамматику G, порождавшую L(G), и конечный преобразователь Т с начальным состоянием So. Мы построим новую бесконтекстную грамматику G', которая порождает T[L(G) ]. Предположим сначала, что Т ограни- ограничен. Тогда мы можем допустить, что он не содержит правил вида Будем строить новую бесконтекстную грамматику G с выход- выходным словарем преобразователя Т в качестве ее терминального сло- словаря и с нетерминальными символами, представленными тройками (Sf, я, Sj), где Sf, Sj— состояния Т н а ? V1). Начальным символом в G' является 6". Правила в G' определя- определяются по следующему принципу: а) S' -* (S0,S,St) есть правило в G' для всех t; б) если А -*¦ (Xj. . . a,k есть правило в G, то / Pp G' для всех I, /, жит правило k р ft_] грамматика G' содер- содер) (Sh A2,Sr,,). . . (\_x . (Sf,x) есть правило в Т, (S S) х в) если (uti) (f) р то G' содержит правило (Sit a, Sj) -»¦ х. E2) ~"Чтоб^г-сохранить условие, что нетерминальные символы суть те и только те, котор"ыё~й5я"бл~яются в левой части правила а-»-<р, мы можем потребовать также, чтобы G' содержала правило (Sf, a, S,)-+(S,, a, Sj)a E3) для всех a, i, j, не включенных в пункт в). Терминальные правила в О' представляют собой правила, заданные в пункте в) конструкции E2). Продолжая вывод из G' до тех пор, пока мы можем обойтись без применения любого терминального правила, мы получим в качестве последней строчки цепочку ') Нижеследующее построение принадлежит Бар-Хиллелу, Перлсу и Шамиру [41, которые использовали его только для доказательства факта, который здесь мы приводим в качестве теоремы 32. Наша теорема 31 доказы- доказывается по существу тем же способом у Гинзбурга и Роуза [21 ]. Это построе- построение тесно связано с представлением преобразователей посредством матриц у Шюценберже [61].
200 Н. Хомскип , • 4' su ) а, E4) где io=O, <x;g W для всех / и G порождает a,...aft. Кроме того, ес- если G порождает (^...^(ixyg Vt), to для всех it,...,ik цепочка E4) пред- предоставляет собой строчку вывода в G'. Но выводы с цепочкой E4) в качестве последней строчки будут оканчиваться терминальной це- цепочкой 2 тогда и только тогда, когда существуют цепочки хъ...,хк, такие, что х1...хк—г и для всех /(ay, S, ^)->-(Sl,,Xj) есть предписа- предписание в Т, т. е. тогда и только тогда, когда Т преобразует входную цепочку a,...as в г, проходя в процессе этого преобразования че- через состояния So, S;,,..., Sik. Таким образом, G порождает язык P[L(G)]. Заметим, что G' может иметь правила вида а-»-е(гдел:=е в лункте б) конструкции E2)). Однако, как мы видели в разд. 4,правила такого рода не допускают порождения языков, не являющихся бес- бесконтекстными (кроме языка (е)). Следовательно, мы имеем следую- .щий результат, где Т — ограниченный преобразователь. Теорема 31. Если L — бесконтекстная грамматика и Т— •(ограниченный) преобразователь, то T(L) — бесконтекстный язык Предположим, что R — регулярный язык, допускаемый автома- автоматом F с начальным состоянием So. Строим преобразователь Т, име- тощий команду (ai,Sj)-J>-(Sk, а;) всякий раз, как F имеет предписа- предписание (i, /, k), т. е. всякий раз, когда F переходит из состояния Sj в состояние Sk, прочитав вход а;. Мы можем предположить, не ог- ограничивая общности, что F является детерминированным (см. тео- теорему 1) и что Т ограничен. Пусть G — бесконтекстная грамматика, порождающая L(G). Построим G' при помощи вышеописанной кон- конструкции, но вместо пункта а) в E2) мы имеем единственное правило S'-t-fio^.S,)). Теперь легко показать, используя теорему 31, что G' порождает пересечение R с L(G). Т е о р е м а 32. Если R — регулярный язык, a L — бесконтекст- бесконтекстный язык, то пересечение LflR есть бесконтекстный язык. Чтобы избавиться от требования ограниченности преобразовате- .ля Т в теореме 31, приведем следующую конструкцию. Если задана бесконтекстная грамматика G, порождающая L(G), заменим снача- сначала каждое правило Л-хх,...^ правилом A->qi1qa2q..,qak q, где q—некоторый новый символ. Теперь применим конструкции E2) и E3), как прежде, чтобы получить G'. Определим теперь язык Qij следующим образом: ¦QtJ = B | для ьекоторого i0 im, xv . . . , xm, г — xx. . . xm и для всех k, 1 <! k <; m, T имеет правило {e, St ) -»¦ (S,4 , xk),jne i0 = i и im = /). E5) Формальные свойства грамматик 201 (St, q, Sy)-*e и (S,, q, Sj)^ Очевидно, что Qtj рггулярен. Следовательно, мы можем к G' до- добавить правила, которые дают соотношения E6) для всех ?, у и всех х ? Q,j. Расширенная таким образом грамматика G' порождает язык TlL(G)]. Следовательно, теорема 31 верна без ограничения, наложенного на Т. Другие результаты, касающиеся эффекта применения различ- различных операций к бесконтекстным языкам и относящимся к ним сис- системам, см. в работах [21, 69]. Будем теперь рассматривать правила только следующих видов: а) А- б) А в) А г) А ВС, ¦ аВ (право-линейное), Ва (лево-линейное). E7) Напомним, что нормальная грамматика содержит только прави- правила типа а) и г); линейная грамматика без ограничения общности мо- может быть описана как грамматика, содержащая только правила вида б), в) и г); конечный автомат содержит только правила вида б), г) или только правила вида в) и г). Напомним также, что нормальная грамматика может порождать любой бесконтекстный язык и что линейная грамматика, хотя и с более ограниченной порождающей способностью, может порождать языки, лежащие за пределами воз- возможностей конечных автоматов (теорема 16). Таким образом, мы получаем порождающую способность, большую, чем у конечных автоматов, разрешая лево- и право-линейные правила, и еще боль- большую, разрешая появление нелинейных правил в грамматике. Конеч- Конечно, некоторые линейные грамматики могут порождать только ре- регулярные языки, хотя ни в том, ни в другом случае не существует алгоритма, определяющего, когда это верно (теорема 25). Остает- Остается решить вопрос, при каких условиях нормальная или линейная грамматика богаче, чем любой конечный автомат, в отношении по- порождающей способности. Чтобы изучить этот вопрос, полезно снова рассмотреть класси- классификацию рекурсивных элементов, данную в разд. 3 предыдущей главы. Конечный автомат содержит либо все право-рекурсивные, либо все лево-рекурсивные элементы. Линейная грамматика мо- может содержать одновременно лево-рекурсивные и право-рекурсив- право-рекурсивные элементы. Кроме того, и линейные, и нормальные грамматики могут содержать самовставляемые элементы. Оказывается, что по- последнее свойство влияет на увеличение порождающей способности по сравнению с конечными автоматами. 15 Заказ № 563
¦202 Н. Хомский E8) Определение 8. Грамматика называется грамма- грамматикой с самовставлением, если она содержит нетер- нетерминальный символ А, такой, что для некоторых непустых цепочек Другими словами, грамматика с самовставлением содержит са- самовставляемые элементы. Теперь можно показать, что: Если G — бесконтекстная грамматика без самовставления, порождающая L(G), то су- существует конечный автомат, который порож- порождает L(G). Отсюда мы немедленно получаем следующий результат. Теорема 33. Язык L не шляется регулярным тогда и только тогда, когда все его бесконтекстные грамматики являются грамма- грамматиками с самовставлением [4, 8, 9]. Таким образом, L является регулярным языком только в том слу- случае, если он обладает грамматикой без самовставления. Ясно, что существует алгоритм, определяющий, содержит ли бесконтекстная грамматика самовставляемые элементы (аналогич- (аналогично содержит ли она право-рекурсивные и лево-рекурсивные элемен- элементы). Если мы испытаем грамматику G и обнаружим, что она не име- имеет самовставляемых символов, то мы можем заключить, что G име- имеет «мощность» конечного автомата (хотя она может содержать и ле- лево-рекурсивные, н право-рекурсивные символы). Если, с другой стороны, мы обнаружим, что G имеет самовстав- самовставляемые символы, мы не будем знать, обладает ли она мощностью конечного автомата. Это зависит от ответа на вопрос, существует ли грамматика G', которая порождает тот же язык, что н G, но не имеет самовставляемых символов. Как мы видели, не существует механической процедуры, с по- помощью которой это может быть установлено для произвольной грам- грамматики G. Таким образом, хотя теорема 33 дает эффективное дос- достаточное условие эквивалентности бесконтекстной грамматики ко- конечному автомату в отношении порождающей способности (и более того, условие, которому удовлетворяет некоторая грамматика каж- каждого регулярного языка), мы знаем, что оно не может быть усилено до эффективного критерия, т. е. эффективного необходимого и до- достаточного условия. Утверждение E8) непосредственно следует из элементарных свойств конечного автомата. Предположим, что G является грам- грамматикой без самовставления, порождающей L(G), а нетерминальные элементы G суть Аъ...,Ап. Назовем G сильно связной, если для каж- каждых I, j существуют цепочки <р и Ф, такие, что Л(-*?Л/|). Предполо- Формальные свойства грамматик 203 жнм, что G ¦— сильно связная грамматика. Если существуют (", /, k, I, такие, что Л,-»?И/ра и Л^фИ,^, где ?1=?е=?ф21 тогда немедленно получаем вопреки предположению, что G обладает свой- свойством самовставления. Следовательно, таких i, /, k, I не существу- существует, и, таким образом, либо каждое нетерминальное правило в G право-линейио, либо каждое правило лево-линейно. В любом слу- случае G порождает регулярный язык. Предположим теперь, что л=1. Тогда либо L(G) конечен (и регулярен), либо G сильно связна и порождает регулярный язык, как только что было показано. Допустим, что утверждение E8) верно для всех грамматик, со- содержащих менее чем п нетерминальных символов. Предположим, что Аг есть начальный символ в G, которая имеет нетерминальные символы А1,...,Аа. Мы можем допустить, что G не содержит лишних символов и не является сильно связной. Таким образом, для неко- некоторого / не существует <р, ф, таких, что Aj-t-rfA^. Предположим, что j=l=\. Образуем G' вычеркиванием из G каждого правила Aj-*4? и заменой Л;- во всех правилах на новый символ а. По индуктивно- индуктивному предположению язык V, порождаемый грамматикой G', явля- является регулярным, так же как и множество К— [х\Л/-» х\. Очевидно, что если Lt и Ьг регулярны и L3 состоит из всех цепочек, образованных из x?Lj заменой каждого символа а (если он встречается) в х некоторой цепочкой из L2, тогда La— регуляр- регулярный язык. L(G) построен таким способом из L' и К и в силу этого регулярен. Предположим, что /=1. Пусть <fi,..., <fr — такие цепочки, что A-^t?,. Пусть К-, —[x\(f!-*x} для каждого i. Предположим, что 9i=ai ••¦ am- По индуктивному предположению множество L;-=(x|a,-#x) регулярно. Из теоремы 2 следует, что К-,, а следова- следовательно и L, также регулярно. Этим доказано утверждение E8). Кроме того, утверждение непосредственно следует из более сильного результата, который будет получен ниже. Мы исследовали так подробно только вопрос слабой эквивалент- эквивалентности грамматик, т. е. вопрос о том, порождают лн они один и тот же язык. Мы определили также понятие сильной эквивалентности двух грамматик, которые не только порождают один и тот же язык, но также одно и то же множество структурных описаний (см. разд. 5.1 предыдущей главы). О сильной эквивалентности известно мало, однако важно отметить, что мы можем расширить утверждение E8) таким образом, что если задана грамматика без самовставления G, то мы можем построить конечный преобразователь Т, такой, что он, в том смысле как это будет уточнено, сильно эквивалентен G. Мы можем также усилить этот результат до любой конечной степени самовставляемости. К отдельным следствиям из этих положений мы вернемся в следующей главе (см. также работу [10]). 15*
204 Н, Хамский Для уточнения сказанного рассмотрим более подробно класс конечных преобразователей. Мы можем предположить, что вход- входной алфавит каждого преобразователя Т есть подмножество Vt (фиксированного и универсального множества терминальных сим- символов для всех бесконтекстных грамматик). Мы предполагаем, что выходной алфавит каждого преобразователя есть подмножество некоторого фиксированного множества А(у Если задан Т, мы гово- говорим, что Т допускает х и ставит ему в соотве пствие структурное описание у [или коротко: Т порождает (х, у) ] только в том случае, когда Т начинает работу в состоянии So с пустой лентой памяти, считывая самый левый символ цепочки х# на входной ленте, и заканчивает работу при первом возвращении в So, считывая # на входной ленте, имея у в качестве содержимого ленты памяти1). Та- Таким образом, если Т порождает (х, у), то он допускает х как конеч- конечный автомат, не имеющий выхода (см. разд. 1.2), и преобразует его в у как преобразователь. Чтобы сравнить порождающую способность преобразователей, понимаемых таким образом, с порождающей способностью бескон- бесконтекстных грамматик, допустим, что нам задано эффективное взаим- взаимно однозначног соответствие Ф, отображающее множество струк- структурных описаний, порождаемых бесконтекстными грамматиками (задаваемых, скажем, цепочками с системами отмеченных скобок, см. стр. 170) в множество цепочек в Ао - Мы можем теперь опреде- определить строгую эквивалентность как отношение между бесконтекст- бесконтекстными грамматиками и конечными преобразователями. - Определение 9. Если задана бесконтекстная грамматика G и конечный преобразователь Т, mo G и Т сильно эквива- эквивалентны тогда и только тогда, когда выполнено следующее усло- условие: Т порождает (х,Ф{у)) в том и только в том случае, когда G порождает х со структурным описанием у. Таким образом, если Т строго эквивалентно G, то Т допускает только цепочки, порождаемые G, и преобразует каждую такую це- цепочку в каждое структурное описание, сопоставленное ей грамма- грамматикой G, и ни во что другое. Мы можем теперь дать точную формулировку обобщения утвер- утверждения E8). Теорема 34. Существует эффективная процедура V, такая, что если задана нормальная бесконтекстная грамматика без само- самовставления G, то W(G) есть конечный преобразователь, сильно эк- эквивалентный G 18]. ') Более точно, в соответствии с описанием преобразователей, данным в разд. 1.5, мы будем говорить, что Г начинает работу, наблюдая а на (в ос- остальном) пустой лейте памяти, и заканчивает работу с чу в качестве содер- содержимого ленты памяти. Формальные свойства грамматик 205 Как было ранее отмечено, эта процедура легко может быть обоб- обобщена на случай любой конечной степени самовставляемости спосо- способом, который мы опишем более тщательно. Очевидно, что утвержде- утверждение E8) и теорема 33 следуют из теоремы 34. Теорема 34 фактически доказана только для нормальных грам- грамматик, удовлетворяющих дополнительному условию, что если Л-*- -+ВС есть правило, то В=?=С, и если A-^yBty и А-^-хВ® суть пра- правила, то x=t? и 11=а). , Нетрудно показать, что этн дополнительные условия не влияют на порождающую способность. Кроме того, только от деталей дока- доказательства зависит вопрос об отбрасывании этих ограничений (и даже многих, если не всех ограничений, которые обусловливают нормальность). Доказательство теоремы 34 слишком сложно, чтобы излагать его здесь, но мы опишем процедуру ЧГ и проиллюстрируем ее на при- примере. Посмотрим сначала, чем теорема 34 отличается от теоремы 19 в разд. 4.2, которая утверждает, что если задана модифициро- модифицированная нормальная грамматика G, то существует конечный пре- преобразователь Т, обладающий следующим свойством: Т преобразу- преобразует jc в цепочку z, которая сводится к е тогда и только тогда, когда г есть структурное описание, поставленное в соответствие цепочке х грамматикой G. В этом случае Ф есть тождественное преобразова- преобразование, т. е. выход преобразователя Т имеет в точности вид струк- структурного описания, определяемого грамматикой G. Кроме того, здесь мы не ограничены только грамматиками без самовставления. Однако преобразователь, существование которого гарантиру- гарантируется теоремой 19, не является сильно эквивалентным G в смысле определения 9. Таким образом, Т, имея на входе х, может возвра- возвращаться в So и закончить работу с цепочкой у на ленте памяти, ко- которая не сводится к е (и не является структурным описанием, по- поставленным в соответствие х грамматикой G). В действительности, причина, по которой преобразователь Т, сопоставленный с бесконтекстной грамматикой в теореме 19, пред- представляется на первый взгляд более мощным, чем преобразователь 7", сопоставленный с бесконтекстной грамматикой в теореме 33, состоит в том, что Т, но не 7" эффективно использует потенциально бесконечную память прн решении вопроса о допущении цепочки с заданным структурным описанием, так как это решение требует ана- анализа сводимости к е (неограниченной) цепочки на ленте памяти. Из теоремы 33 мы знаем, что теорема 34 является самым сильным воз- возможным результатом, касающимся сильной эквивалентности бес- бесконтекстных грамматик и устройств со строго ограниченной па- памятью. Чтобы проиллюстрировать теорему 34, предположим, что G — нормальная грамматика без самевставлеиия, удовлетворяющая
206 Н. Хомский дополнительному условию, приведенному сразу после теоремы 34. Пусть К — множество последовательностей {(Аи ... ,Ат)\, удовле- удовлетворяющих следующему условию: для каждой пары I, j, такой, что 1 <i'</<m, имеет место Л,-*<рЛ,+1ф и А1ф Aj. Теперь мы можем построить грамматику С* с нетерминальными симво- символами, представленными в виде [Bl...Bn]l (i=l,2), где В.- — нетерминальные символы G, следующим образом '). Пусть (В, Ва)?К. 1) Если В„ -* а, то [В,... В,]^ а[Вг... В„]2. 2) Если Bn-+CD, где СфВьфО (?<л). то а) [В1...В„]1-ЧВ1...В„С]1, б) [В,... ВпСJ -». [В,. . . BnD]t, в) [B1...BD]t-blBl...Bn]t. 3) Если Bn-+CD, где В, == ?) для некоторого (</г, то E9) а) [В1...В11]1-ИВ1...В„С]„ б) [В,. ..В„С]а-*[В1...В,]1. 4) Если В„ -S- CD, где Bt = С для некоторого ? <; гг, то а) [Bj. . . Вг]2 ->. [Вх. . . BnD)}, б) [В1...В„О]2-*[В1...В„]2. Теперь мы можем доказать, что в G существует S-вывод це- почкн г тогда и только тогда, когда' в G* существует [Slj-вывод цепочки zlSlz (теорема 10 в работе 18]), гдеS—начальный символ в G. Правила в G все имеют вид А-^-аВ, где а—е, если онн не явля- являются правилами, полученными по пункту 1) конструкции E9). Сле- Следовательно, мы можем рассматривать G* как конечный автомат. Предположим теперь, что мы снабдили автомат новым состоянием So н дополнительными правилами Sf Ql г С l Q /сл\ О ~* l^Jl» 1^21 ~* '-V (ЬО) Если So считать начальным состоянием, то устройство становится ') Мы можем использовать символ -•- одинаково для грамматики Саб*, так как вид их нетерминальных символов различен. Формальные свойства грамматик 207 слабо эквивалентным G. Чтобы превратить это устройство в преоб- преобразователь, мы должны снабднть его правилами выдачи выходного символа при переходе из состояния Qt в состояние Qj и считывании символа ак. Мы считаем, что выходной алфавит состоит из множе- множества нетерминальных символов G* (т. е. множества символов вида [В,...В„]г, которые теперь означают состояния автомата). Мы бу- будем говорить, что когда устройство переходит в состояние Q, оно печатает выходной символ Q. Этим завершается конструкция W, требуемая теоремой 34, которая связывает конечный преобразова- преобразователь Т с грамматикой без самовставления G. Если G порождает х, то Т преобразует входную цепочку х в выходную'цепочку о, где о есть запись последовательных состояний, через которые Т прохо- проходит, допуская (порождая) х. Эта последовательность о в действительности содержит полную информацию о структурном описании, сопоставленном х граммати- грамматикой G, и обратно, для каждого структурного описания, сопостав- сопоставленного цепочке х грамматикой G, существует последовательность состояний о, в которую Т преобразует х и которая точно представ- представляет строение этого структурного описания. Дело в том, что назва- названия состояний в действительности содержат информацию о некотором поддереве размеченного дерева, сопоставленного цепоч- цепочке х грамматикой G; из данной последовательности состояний это размеченное дерево может быть полностью восстановлено. Мож- Можно построить процедуру Ф такого типа, как это описано в опреде- определении 9, которая будет превращать выход Т в структурное описа- описание (скажем в структуру помеченных скобок) его входа и обратно. Такое построение подробно описано у Лангендоена [3711). Следо- Следовательно, преобразователь Т, построенный при помощи процедуры W из конструкций E9) и F0), сильно эквивалентен G. Свойства конструкции W можно объяснить на примере. Рассмот- Рассмотрим грамматику F1), которая удовлетворяет условиям конструк- конструкции ЧГ н теоремы 34: S-+ АВ, А -* SC, В -> DB, А-+а, В^Ь, С-у с, D->-d. F1) Эта грамматика порождает язык, состоящий из всех цепочек a(dlbc)> d"b, и ставит им в соответствие структурное описание та- такого вида, как показано на рис. 10 (для случая {=/-=!, k—2). Заме- •) Лаигендоеи, в действительности, строит процедуру Ф, которая рабо- работает в реальном масштабе времени; т. е. скобочная структура цепочки х, порождаемой грамматикой G, выводится процедурой Ф из выхода преобра- преобразователя Г, сопоставленного с G, во время работы Т иад х.
1 208 Н. Хамский А В i I /V В I -7V тим, что G содержит как лево- леворекурсивные, так и право-реку- право-рекурсивные элементы, хотя она не содержит самовставляемых эле- элементов, и что в данном случае лево-рекурсивный элемент А до- доминирует над прзво-рекуреив- иыи элементом Л.:.Этот пример иллюстрирует положение {часто опускаемое, или недопонимае- недопонимаемое), что, хотя конечный преоб- преобразователь Т, который интер- интерпретирует предложения так же, как грамматика G, конечно, чи- читает эти предложения слева на- направо при одном прохождении, отсюда не следует, что должна быть какая-либо лево-правая асимметрия в структурном опи- описании этих предложений. Класс К последовательностей, построенных из грамматики G F1), содержит последовательности (S), (S, A), (S,B), (S,A,C) н (S,B,D). Конструкция W производит следующие правила: (шагом 2 конструкции E9)) В Рис. 10. Структурное описание предложения, порождаемого грамма- грамматикой F1). [SA]1 -*• a [SA]2 (шагом 1 конструкции E9)) (шагом 4 конструкции E9)) F2) -6 [SB]2 (шагом 1 конструкции E9)) -* [SBD], [SBD], -+ [SB], >¦ с (шагом 3 конструкции E9)) (шагом 1 конструкции E9)) Эти- правила образуют грамматику G*, определяемую при по- помощи W. В соответствии с рис. 10 имеем вывод Формальные [S]i \SA\i a[SA\, a[SB]i ad [SBDh ad [SB]! adb[SB]2, adb [Sb adb [SAC^ adbc [SAC]2 свойства грамматик 20i adbc [SA]2 adbc [SB]! adbclSBDh adbcd [SBD]t adbcd[SB]t adbcdlSBD)! ' F3 adbcdd [SBD]t adbcdd [SB]t adbcddb [SB]2 adbcddb [S]2 Ясно, что последовательность нетерминальных символов, по- полученных в этом выводе, позволяет нам однозначно восстано- восстановить структурное описание, показанное на рис. 10. Действитель- Действительно, автомат с правилами из примера F2) порождает предложение adbcddb, систематически обходя размеченное дерево рис. 10. Этот пример типичен; он показывает, каким образом устройство с конечной памятью может сопоставлять с каждой цепочкой х, порождаемой нормальной грамматикой без самовставления G, структурное описание, которое грамматика G ставит в соответ- соответствие х, причем это структурное описание может иметь произ- произвольную сложность. Предположим теперь, что нам нужно применить эту конструк- конструкцию к нормальной грамматике G с самовставлением. Будем гово- говорить, что преобразователь Т порождает (х, у) подобно грамматике G, если Т порождает (я, у) в том смысле, как это было определено выше (т.е. преобразует х в у, допуская х как конечный автомат), причем Ф~1(у) есть структурное описание, которое грамматика G ставит в соответствие х. Тогда преобразователь ^@), построенный, согласно конструкциям E9) и F0), будет, действительно, порождать (х, у) подобно грамматике G для каждой пары (х, у), такой, что у есть структурное описание, которое грамматика G ставит в соот- соответствие х, и такой, что у не включает никакого самовставления. Кроме того, увеличивая память преобразователя Т (по-видимому, самый простой способ здесь состоит в присоединении ограничен- 14 Заказ Mi 563
210 Н. Хомский цого устройства PDS), мы позволим ему переименовать самовстав- самовставляемые символы вплоть до получения любой ограниченной степени самовставляемости и далее работать, как прежде. В этом случае Т может порождать (х, у) подобно G для всех таких пар (х, у), что у есть структурное описание, которое грамматика G ставит в соответ- соответствие х и которое может содержать только ограниченные степени самовставлеиия. Как мы знаем из теоремы 33, это самое большее, чего мы можем достичь при помощи конечного устройства. Из ре- результатов разд. 1.6 и 4.2 следует, что если мы разрешим преобразо- преобразователю использовать неограниченную память PDS, то он может быть сделан строго эквивалентным любой нормальной грамматике G; заметим, в частности, что конструкции A8) и A9) из разд. 4.2 на самом деле являются лишь' тривиальными частными случаями кон- конструкции E9), содержащими только разделы A) и B). Приведенные рассмотрения четко ограничивают объем, в ко- котором предложения, порождаемые бесконтекстной грамматикой, могут обрабатываться (т.е. допускаться или интерпретироваться) устройством с конечной памятью или человеком, не имеющим (или имеющим весьма ограниченные) вспомогательных средств для ра- работы. Мы снова вернемся к этим вопросам в следующей главе. 4.7. Определимость языков системами уравнений Пусть G — бесконтекстная грамматика; ее нетерминальные сим- символы обозначим по порядку Аг А„, где Л,— выделенный на- начальный символ. Каждому At соответствует множество Е, терми- терминальных цепочек, доминируемых символом Аг; т. е. Т1~{х\А1^х\ в наших обычных обозначениях. Сопоставим грамматике G после- последовательность множеств (?ь...,?„), состоящих из терминальных цепочек, где Et— терминальный язык, порождаемый граммати- грамматикой G. Мы скажем, что данная последовательность множеств удов- удовлетворяет грамматике G при данном порядке нетерминальных символов. Очевидно, каждый член удовлетворяющей последователь- последовательности будет терминальным языком, порождаемым некоторой бес- бесконтекстной грамматикой, а именно грамматикой, отличающейся от G только выбором начального символа. Предположим теперь, что мы рассматриваем нетерминальные символы G как переменные, значениями которых являются мно- множества цепочек в терминальном словаре. Мы определяем полиноми- полиномиальное выражение над переменными А1,...,Ап как выражение вида 9i + • • • + 9*. F4) где каждая <р, есть цепочка в V, а единственные нетерминальные символы, встречающиеся в выражении F4), суть А1....,Ап. С по- помощью такого полиномиального выражения, как выражение F4), можно задать функцию /, отображающую последовательность мно- Формальные свойства грамматик 211 жеств цепочек в Vr на множество цепочек в Vt следующим образом. Если дана последовательность (?,,...,?„), где Е, есть множество цепочек в Vt-, то пусть /(Е, Еп) будет множеством'цепочек, ко- которое получится, если в выражении F4) заменить каждое вхожде- вхождение Л, знаком Е,, обозначающим множество Е,, н затем интерпре- интерпретировать знак + как теоретико-множественное объединение, а сое- соединение (конкатенацию) — как теоретико-множественное (прямое) произведение (т.е. если А и В — Два множества, то АВ = \yz\y ? Л, z?B\; хА = {ху\у?А}; Ах=\ух\у ? А}). Например, функция/(Л, В), заданная полиномиальным выражением а+Аа + ВаА, F5) отображает пару множеств \х,у), (г, w) на множество [а, ха, уа, zax, гау, wax, may]. Если дана бесконтекстная грамматика G с нетерминальными Л j,...,Л„, сопоставим каждому Л, полиномиальное выражение <р!+ —^- —|-tpft, где Л(—*-<pi,...,A,-*-ipft суть все правила G, в которых Л; встречается в левой части. Рассмотрим теперь систему уравнений А = h (Л, А„), F6) где /,— функция, заданная полиномиальным выражением, сопос- сопоставленным символу Л,. Известно, что такая система уравнений имеет единственное минимальное решение; иначе говоря, существу- существует единственная последовательность множеств ?!,...,?„, удовлет- удовлетворяющая этой системе уравнений (в качестве значений для Ли... ..., Л „соответственно), и такая, что если Е'ъ...,?'„ есть другое ре- решение этой системы, то Е;сЕ', для каждого i. Далее, ясно, что по- последовательность множеств, являющаяся минимальным решением для уравнений F6) (в дальнейшем мы будем называть ее просто решением [the solution]), есть та самая последовательнссть мно- множеств, которая удовлетворяет грамматике G в смысле первого абза- абзаца этого раздела, а Е^ есть терминальный язык, порождаемый грам- грамматикой G. Несколько иначе сформулировав это замечание, мы можем рас- рассматривать уравнения F6) как задающие функцию /, такую, что f (Д ,..., Ап) = [МА ...., Л„) U (А,...., Л„)]. F7) Неподвижной точкой функции / называется такая последователь- последовательность (?!....,?„), что /(?!,...,?„)=(?!,...,?„). Тогда у функции / существует единственная минимальная неподвижная точка, совпа- 14*
212 Н. Хомский дающая с решением уравнений F6); т.е. это последовательность множеств, удовлетворяющая грамматике О. Для нахождения решения уравнений F6) можно определнть сле- следующий рекурсивный процесс. Будем строить последовательность в|), о,,..., каждый член которой представляет собой кортеж п мно- множеств, следующим способом: о0 есть кортеж @,...,0), где 0 есть пустое множество. Для каждого ?>•() положим а1+1 =/(о,). Если теперь о,—(в1!,...,!»',,), определим о так: o=lim о(=(о"|,...,о"), о,*1). Эта последовательность о и будет решением урав- уравнений F6). Она будет также неподвижной точкой для функций / из F7) н последовательностью множеств, удовлетворяющей грамма- грамматике G, a о" будет терминальным языком, порождаемым G. Будем говорить, что каждое о" определимо из уравнений F6): определи- определимый язык есть множество, определимое подобной системой урав- уравнений. Очевидно, что определимые языки суть в точности бескон- бесконтекстные языки. Кратко обрисованная здесь схема рассмотрена подробнее Гинз- Гинзбургом и Райсом [20] и служит основой для исследований, прове- проведенных в этой работе и продолженных в статьях [21, 22]. Эта ра- работа первоначально выросла из исследований по языкам вычисли- вычислительных машин (в частности, по АЛГОЛу) н привела к некоторым интересным результатам, касающимся этих систем; к ним мы вер- иемся в разд. 4.8. Этот подход к бесконтекстным языкам был обобщен Шюценбер- же (см., в частности, работы [63, 65, 691). Пусть имеется отображе- отображение /, сопоставляющее каждой цепочке х в Vt неотрицательное це- целое число f(x). Можно представить f формальным степенным ря- рядом г: X, F8) над элементами щ ? Vt , где общий коэффициент < г, х > =/(*). Мы скажем, что формальный степенной ряд г — характеристический, если < г, х > Для каждогох равно 0 илн1, т.е. если ( г, х > представ- представляет собой характеристическую функцию. Определим основание (sup- (support) формального степенного ряда г [=sup (r) ] как множество тех цепочек, для которых < г, х > =?0. То есть основание можно полу- получить, если рассматривать знак .+ как обычное теоретико-множест- теоретико-множественное объединение, а пх, где п — коэффициент прн х, как х-\-...+х п раз (что сводится к отождествлению пх с х прн пфО). х) Под суммой здесь имеется в виду теоретико-множественное объедине- объединение.— Прим. перед. Формальные свойства грамматик 213 Заметим, что формальный степенной ряд становится обычным степенным рядом над переменными а, ? Vt ,если считать их комму- коммутативными, т.е. если отождествлять цепочки, которые могут быть получены друг из друга перестановкой элементов. Множество формальных степенных рядов замкнуто (среди про- прочих) относительно следующих операций: (а) Умножение иа целое число: коэффици- коэффициент < w, х~у прн х равен п < г,х > . (б) Сложение: коэффициент < г+г',х > при х в ряде г+г' равен < г, х ) + ( г', х ) . F9) (в) Умножение: коэффициент (гг',х} при х в ряде гг' получается разложением х во всевозможные произведения уг=х vl суммированием всех членов < г,у > <г',г), т.е. < rr',x > =J] < г,у > <г',г) по всем уг, таким, что уг=х. Отметим, что сложение аналогично теоретико-множественному объединению, а умножение — образованию прямого произведения. Таким образом, мы имеем sup (г -+¦ г') = sup (г) и sup (г'), sup (г г') = SUP (r) • sUP (О- G0) Можно также определить операцию, аналогичную пересечению множеств, как операцию ®. такую, что г®г' есть степенной ряд с коэффициентом г®'"' при*, равным < г,х > < г',х > . Так же легко определяются операции, соответствующие замыканию и —для неко- некоторых случаев — дополнению. Если дана грамматика G с нетерминальными Л, Ап, то пусть ft (х) — число структурных описаний, приписываемых цепочке х грамматикой G,, которая получится, если в G принять Ai за на- начальный символ (мы можем для определенности считать, что струк- структурные описания представляют собой системы помеченных скобок, порождаемых грамматикой так, как это описано на стр. 170; в этой случае ft(x) равно числу цепочек, порождаемых грамматикой G,-, которые при опускании скобок дают цепочку х). Пусть Г; — фор- формальный степенной ряд, который каждой цепочке х сопоставляет коэффициент < г-„х > =ft(x). Тогда [sup(r1),...,sup(rn)l есть после- последовательность множеств, которая удовлетворяет грамматике О в вышеописанном смысле; sup(r,) есть терминальный язык 1@), по- порождаемый грамматикой G; < rltx > =0 тогда и только тогда, когда xiL(G); ( rux > —п тогда и только тогда, когда G дает п неэкви- неэквивалентных выводов и, значит, п различных структурных описаний для х. Мы говорим, что последовательность (гь...,г„) удовлетворяет грамматике G. Данное выше определение удовлетворяющей после- последовательности является частным случаем этого определения, при
214 Н. Комский котором рассматриваются те формальные степенные ряды, которые получаются из определенных здесь рядов отождествлением всех неравных нулю коэффициентов. Последовательность (г1,...,г„), удовлетворяющая грамматике G, может быть получена, точно так же как и раньше, методом итера- итераций. Рассматривая G в виде системы уравнений вида F6), мы стро- строим бесконечную последовательность о,,,^,.,., где о, = (r'j,...,/•{,), a r'j есть формальный степенной ряд (в действительности имеющий лишь конечное число членов; иначе говоря, г';- будет полиномиаль- полиномиальным выражением над нетерминальными символами G). Как и преж- прежде, считаем, что уравнения F6) определяют функцию /, которая в этом случае отображает последовательность (r^...,^) на последо- последовательность 1/1(г1,...,г„,),...,/„(г1,...,гп) ]. Функция /, задана, как н прежде, полиномиальным выражением tpi+"-+<P*, гДе A-^-'fj (l^j^k) суть все правила G, имеющие А в левой части. Опера- Операции + и соединение интерпретируются теперь не как объединение н произведение, но как соответствующие им операции над степен- степенными рядами (см. определение F9)). Определим о0 как последова- последовательность1 (г0!,...,г°„), где каждый г°(есть «пустой» степенной ряд, у которого все коэффициенты равны нулю. Примем о,и=/(ог). Как и прежде, возьмем о—Нтог= (г™ ,...,г"), где г/° определен сле- дующим образом. Пусть х — цепочка длины k, a r'j, как и выше,— /-Й член последовательности ак. Тогда коэффициент при х в степенном ряде г* определяется следующим условием: = < г* G1) В самом деле, нетрудно показать, что в последовательности з0, ai,... коэффициенты при цепочках длины k не изменяются после оА. Следовательно, о действительно является пределом этой последова- последовательности; г™ есть формальный степенной ряд, порождаемый грам- грамматикой G, если /4j есть начальный символ G, а его основание. sup(r"(), есть язык, порождаемый G в ранее определенном смысле; '*",, кроме этого, ставит в соответствие каждой цепочке х, принад- лежащей sup(r™), ее коэффициент < г^ , х}, который представляет собой меру степени неоднозначности, приписываемой грамматикой G цепочке х. В дальнейшем, когда мы буд;м говорить о степенном ряде, удовлетворяющем G, будет иметься в виду ряд г™ . Пусть, например, имеется грамматика G с правилами А->-Ь\ G2) Формальные свойства грамматик 215 ей соответствует система уравнений, состоящая из одного следую- следующего уравнения: А = а + Ь+А\ G3) В этом простейшем случае имеем °j=(r'i), где ?- а + Ь Л- (г\)* ^a bf» G4> < r\ , x > =1 для каждой цепочки длины 1, 2 и 4, < г\ , х > =2 для каждой цепочки длины 3, г\ = а -+ Ь + ( АУ н т. Д. Коэффициенты при каждой цепочке длины 3 остаются равными 2 в любом r'!(i>3), при цепочках большей длины коэффициенты увели- увеличиваются. Таким образом, в этой грамматике имеется только один Л А А / \ / Ч / \ А А А Д А А II А I I /\ а Ь А А а а А А а Ъ b a д А А А ^ / \ /\ /\/\ / \ / Л Л1 Ait Л ! А 1111 Л Г 1 Л * " 1 Л ' Л а Ь а Ь А А а »ЛА Ь А А А А Ь a b Ь а а Ь Ь а Рис. И. С-маркеры, иллюстрирующие неоднозначность грамматики G2). способ порождения для каждой цепочки длины 2, ровно два способа порождения цепочки длины 3, пять способов порождения цепочки длины 4 и т.д., как можно видеть из примеров, приведенных на рис. 11. Ряд гг, являющийся пределом так определенных г\, будет
216 Н. Хомский решением уравнений G3). Его основание есть терминальный язык ЦСО), порождаемый грамматикой G. В этом случае L(G) есть множество всех цепочек в алфавите \а,Ь}> и мы знаем, что существует эквивалентная грамматика G*, имеющая в качестве решения характеристический степенной ряд (т.е. коэффициенты которого равны 0 либо 1 — в данном случае все равны 1, за исключением коэффициента прн е) с основанием L{G). Примером может служить грамматика G , заданная уравне- уравнением А = а+Ь+аА+ЬА. G5) Как было отмечено выше (разд. 1.2, теорема 1), для каждого конеч- конечного автомата существует соответствующий ему детерминирован- детерминированный автомат. Говоря в терминах этого раздела, каждый регулярный язык порождается грамматикой G, которой удовлетворяет некото- некоторый характеристический формальный степенной ряд. Язык, порож- порождаемый грамматикой из примера G2), регулярен; мы можем это ви- видеть из того факта, что он порождается односторонней линейной грамматикой G5). Однако, как утверждает теорема 29 из разд. 4.5, существуют бесконтекстные языки, которые нельзя представить та- таким способом при помощи характеристического ряда; именно теоре- теорема 29 утверждает существование языка L, являющегося основанием ряда г, который удовлетворяет бесконтекстной грамматике, но не являющегося основанием никакого характеристического ряда, удовлетворяющего бесконтекстной грамматике. В качестве еще одного примера для иллюстрации этих понятий рассмотрим следующие грамматики: S-+a+bSS, - G6) S-±a + SbS. G7) Интерпретируя Ь как знак импликации и а как переменную, мы ви- Дим, что грамматика G6) порождает множество правильно построен- построенных формул имплнкативного исчисления с одной свободной пере- переменной в бесскобочной записи Лукассвича и соответственно имеет характеристическое решение. Грамматика G7) порождает множест- множество цепочек, получающихся нз формул этого исчисления в обычной записи опусканием скобок, и ее решением является степенной ряд, в котором коэффициент прн данной цепочке равен числу различных способов расстановки скобок, превращающих эту цепочку в пра- правильно построенную формулу. Введенное Шюценберже понятие представляющих множеств, перечисляемых порождающим процессом в терминах формальных степенных рядов, обусловлено потребностями изучения языка. Как подчеркивалось не раз, мы в конечном счете заинтересованы в 217 изучении процессов, порождающих системы структурных описа- описаний, больше, чем процессов, порождающих множества цепочек, т.е. в сильной, а не в слабой порождающей способности. Кратко описанный здесь подход является первым шагом в этом направле- направлении, поскольку он учитывает число структурных описаний, припи- приписываемых цепочке (хотя и не сами этн структурные описания). Он также дает нам вполне естественный подход к изучению недетер- недетерминированных преобразователен. Напомним, что преобразователь, вообще говоря, может обла- обладать двумя различными видами недетерминированное™. Находясь в состоянии Sf н считывая символ а, он может иметь право выбрать переход в то нли иное состояние. Выбрав переход в состояние S,, он может, далее, иметь право напечатать ту или иную цепочку на выходной ленте. Мы скажем, что цепочка х=Ь1...Ьт (где bt—сим- bt—символ входного алфавита) переводит преобразователь Т из состояния Sj в состояние S, с выходом x=xv..xm, если Т имеет правила (ftt. Sik)~+(Sik+l' **) АЛЯ некоторых i1 im+1 (h = i; imtl =/) и для каждого ft-^rrc. Тогда цепочка х может переводить Т из St в S/ со многими различными выходами, и оиа может переводить Т из Sj в Sj с выходом х многими различными путями (с различным разложением х). Естественно поэтому попытаться представить результат действия одной цепочки х на преобразователь Т при переводе его из S( в S, 5] < ( i j) ) Есо поэтому попытаться представить результат действ входной цепочки х на преобразователь Т при переводе его из S( в S, полиномиального выражения п(х, ?, /) =5] < к(х, i, j), ффт ( {х i /) г ) представляет собой число прн помощи полиномиального выражения щ*, ¦., J; ^ ч ..v., ,,, z > г, где коэффициент < п{х, i, /), г ) представляет собой число различных путей, переводящих Т из St в Sj, прн которых г по- получается на выходе. Тогда можно представить преобразова- преобразователь Т, имеющий п состояний, при помощи гомоморфизма \х, отобра- отображающего Vt в кольцо квадратных матриц л-го порядка, элементы которых есть полиномиальные выражения над выходным алфа- алфавитом Т. Матрица \хх с элементами (|ix)y =к(х, i, j) представляет поведе- поведение преобразователя Т при его переходе из состояния S, в состоя- состояние S: под действием цепочки х. Многие задачи теории преобразо- преобразовании сводятся прн этом к проблемам оперирования с матрицами, что позволяет применить хорошо разработанную технику [61, 66]. Более того, при этом общем подходе возникают некоторые новые проблемы. Так, в этом изложении мы ограничились лишь положи- положительными степенными рядами, т.е. рядами с неотрицательными коэф- коэффициентами. Обобщая этот подход, можно рассматривать алгебраи- алгебраические элементы (элементы кольца степенных рядов), имеющие как положительные, так и отрицательные коэффициенты и удовлетворя- удовлетворяющие системам уравнений, которые могут иметь н отрицательные коэффициенты в полиномиальных выражениях.
218 Н. Хомский Степенной ряд г с положительными н отрицательными коэффи-- циентами можно представить в виде разности двух положительных степенных рядов г' и г''. Коэффициент прн цепочке х в ряде г будет при этом равен разности между числом способов, которыми грамма- грамматика, соответствующая ряду г', порождает цепочку х, н числом спо- способов, которыми порождает эту же цепочку грамматика, соответ- соответствующая ряду г''. Основание ряда г есть множество тех цепочек, которые порождаются этими двумя грамматиками неодинаковым числом способов. Шюценберже исследовал семейство формальных степенных ря- рядов г—г'— г", где г' и г" удовлетворяют односторонней линейной грамматике и, следовательно, основаниями их являются регуляр- регулярные языки ( эти формальные степенные ряды соответствуют рацио- рациональным функциям, если отождествить цепочки, получаемые друг из друга перестановкой нх элементов), и охарактеризовал основа- основания этих формальных рядов в терминах допустимости некоторым классом ограниченно-бесконечных автоматов [611. Он показал так- также, что подобный ряд г может иметь в качестве основания язык, не являющийся бесконтекстным, и, с другой стороны, что сущест- существуют бесконтекстные языки, не являющиеся основанием какого-ли- какого-либо подобного степенного ряда [66]. Дальнейшее обсуждение этих и связанных с этими вопросов можно найти в вышеприведенных ра- работах и в работе Шюценберже и Хомского [69]. Чтобы показать на примере использование введенных выше по- понятий, приведем следующий общий результат, относящийся к ре- регулярным языкам и связанный с вопросами неоднозначности бес- бесконтекстных языков, обсуждавшихся в разд. 4.5. Теорема 35. Пусть G — односторонняя линейная грамма- грамматика, которой удовлетворяет формальный степенной ряд г и ко- которая порождает язык L(G)=sup(r). Пусть Lk = [x\{r, x)<^k\. Тогда при каждом k Lk есть регулярный язык (Шюценберже, личное сообщение). Пусть N — множество натуральных чисел, k — фиксированное целое число, a NM— полукольцо квадратных матриц порядка М с элементами из N. Доказано [66], что если G и г удовлетворяют усло- условиям теоремы 35, a U — множество всех цепочек в Vr (т.е. сво- свободная полугруппа с образующими a?Vr), то существует такое М < да и такой гомомор- гомоморфизм p.: U в NM, что< г, х > =( Пусть и р: N->K, определенное условиями Р (я) = п для п < к; р (л) = k для п > 6. G8) G9) Формальные свойства грамматик 119 Определим сложение и умножение на множестве К, положив i(Di^Hi + i), i®i = H4")- (80) К, есть полукольцо н легко показать, что р есть гомоморфизм, отоб- отображающий N на К. Пусть Км будет множеством (даже полуколь- полукольцом) матриц порядка М с элементами из К- Тогда р естественным образом распространяется в гомоморфизм р: Nm-+Km. Определим ср(х)=р[а(х) ], где \i удовлетворяет условиям предло- предложения G8). Тогда f(x) принадлежит Км для x?U. Очевидно, что (<?хIМ= < г, х > , если < г, х} <fe, (? *)i, м = k, если < г, х > > k. Но Км есть мультипликативная полугруппа конечного порядка, и для k''<Л г, х 6Q); здесь первый знак равенства имеет место по определению, а вто- второй — в силу предложения G8); Q есть подмножество множества f(U), содержащее tp(x) в том и только в том случае, когда (?x)i,M^fe'. Хорошо известно, что если iji —• гомоморфизм, отображающий под- подмножество множества U на конечную полугруппу Я, то множество ¦b~1(H) = {x[<]f(x) ?#| является регулярным языком. Следователь- Следовательно, Lf также есть регулярный язык. Из того, что при каждом k Lk есть регулярный язык, в силу ос- основных свойств регулярных множеств, следует (см. теорему 1), что для каждого k множество цепочек х, для которых ( г,х ) =к, и множество цепочек, для которых < г, х ) 5>й, будут регулярными языками. В частности, множество тех цепочек х, для которых < г,х ) >2, также есть регулярный язык. Это—множество цепочек, неоднозначных относительно G в смысле разд. 4.5. Возьмем, в частности, два множества цепочек X— {х17...,*„) и F=jr/,,...,Уц\. Определим Lx как множество всех цепочек г=х^.-. ...хк (ks^n), т.е. всех цепочек, разлагающихся в соединение элемен- элементов множества X; в терминах разд. 1.2 множество Lx было бы обоз- обозначено (*!,...,*,,)*• Аналогично определим Ly . Назовем Lx кодом (ср. с разд. 2 предыдущей главы), если каждая цепочка Lx однознач- однозначным образом разлагается (дешифруется) на элементы нз X (ана- (аналогично для К). Рассмотрим теперь грамматику Gx с правилами S->XiS и грамматику Gy с правилами S->r/,S (и правилом S-»e). По теореме 35 множество цепочек, неоднозначных относительно G< (как н относительно Gy), регулярно, и, значит, существует алгоритм для определения того, пусто оно или нет. Следовательно, существу-
220 Н. Хомский ет алгоритм, позволяющий определить, образует лн данное мно- множество цепочек код илн нет (см. работу [56]). Однако мы не можем узнать, одинаково ли не являются кодами данные два множества (ср. с разд. 4.5). Пусть теперь G н г удовлетворяют условиям теоремы 35, а С другая односторонняя линейная грамматика, которой удовлетворя- удовлетворяет ряд г'. Из теоремы Маркова н предложения G8) следует, что не- невозможен алгоритм, определяющий для произвольного случая это- этого рода, существует лн цепочка х, для которой < г,х > = ( г', х > . Из теоремы 35 следует, что прн любом фиксированном k существу- существует алгоритм, определяющий, когда непусто пересечение Lk()L'h, где Lk = \х\ < r,x} <&|,L/=(x| < r',x) ¦<?). Отсюда видно, что не- невозможен алгоритм, определяющий, существует ли такое k, для ко- которого Lk(\Lk' непусто (Шюценберже, личное сообщение). 4.8. Языки программирования Программа цифровой вычислительной машины может рассматри- рассматриваться как цепочка символов в некотором фиксированном алфавите. Язык программирования может рассматриваться как бесконечное множество цепочек, каждая из которых есть программа. Он имеет грамматику, точно определяющую алфавит, и множество правил построения программ. Гинзбург и Райе указывают, что язык АЛГОЛ имеет бесконтекстную грамматику, хотя и не односторон- одностороннюю линейную и не последовательную. Это наблюдение показывает, что интересно попытаться интерпретировать результаты, получен- полученные в общей теории бесконтекстных языков, считая, что они состав- составляют класс потенциальных языков программирования для решения задач. Заметим, в частности, что язык программирования должен иметь однозначную грамматику в смысле, определенном выше в разд. 4.5. Если множество правил, применяющихся при построении про- программ, составляет неоднозначную грамматику, то может получиться что программист составит программу, которую машина должна интерпретировать определенным образом, а машина интерпретирует ее совершенно иначе. Мы, однако, видели, что некоторые бес- бесконтекстные языки существенно неоднозначны относительно класса бесконтекстных грамматик (разд. 4.5, теорема 29). Поэтому имеется хотя бы абстрактная возможность того, что некоторое бесконечное множество «программ» нельзя будет охарактернзовать при помощи однозначной грамматики, если ограничиться теми методами по- построения программ, которые выразимы в пределах теории бескон- бесконтекстных грамматик. Кроме того, мы видели, что невозможен ал- алгоритм, распознающий по заданной бесконтекстной грамматике, является ли она однозначной (разд. 4.5, теорема 28). Следователь- Следовательно, в отдельных случаях задача распознавания однозначности Формальные свойства грамматик 221 грамматики (т.е. удовлетворяет ли предлагаемый язык программи- программирования минимальным требованням адекватности) может оказаться весьма нелегкой. Возьмем теперь проблему перевода с одного языка программи- программирования Lx на другой L, (например, машинный код или другой язык программирования более высокого порядка). Мы можем рассматри- рассматривать ее как проблему построения конечного преобразователя («ком- («компилятора») Т, такого, что T(L^=Li. В общем случае нет причин предполагать, что такой преобразователь существует. Более того, мы знаем, что общая проблема распознавания по двум бесконтекст- бесконтекстным языкам i-i и L% существует ли такой преобразователь Т, что T(L1)=L2, алгоритмически неразрешима (разд. 4.4, теорема 27), Отсюда вытекает, что прн решении проблемы перевода произволь- произвольных систем этого рода, по-видимому, смогут возникнуть весьма сложные вопросы (Гинзбург, личное сообщение). 5. Категориальные грамматики Основное содержание традиционного грамматического анализа составляет расчленение предложения на все более и более мелкие составляющие его частн-еннтагмы вплоть до категорий отдельных слов; при этом имеется лишь конечное число типов, к которым при- принадлежат этн синтагмы (именная группа, глагольная группа, имя существительное н т.п.). За последние двадцать лет в дескриптив- дескриптивной лингвистике появились различные попытки более четко и ясно сформулировать этот традиционный1 подход. Здесь можно прежде всего назвать Харриса (работа [25], переработанная затем в гл. 16 работы [26 ]), затем Уэллса 176 ] и недавние работы Пайка и его кол- коллег по тагмемике (in Tagmemics) (см., например, работу [18]). По- Порождающие системы, рассмотренные в разд. 3 и 4, дают один воз- возможный метод точного выражения некоторых из этих идей. Но бы- были и другие, более илн менее связанные с этим подходы, которые здесь лишь бегло упомянуты. Были сделаны некоторые попытки развить систематический ме- метод, ведущий от множества цепочек к разбиению подцепочек на ти- типы составляющих (см., например, работы [6, 25, 26, 32]). Эти под- подходы, несомненно, связаны друг с другом и с рассматриваемыми здесь системами, но точная природа этой связи еще не исследована. Несколько отличный подход к систематической категоризации ти- типов составляющих можно найти у Хнза [28]. Другой подход вытекает нз теории семантических категорий Лес- невского, которая была развита для нужд изучения формализован- формализованных языков. Некоторая модификация этой теории, основанная на формулировке Айдукевнча [1 ], была предложена Бар-Хиллелом {2 ] в качестве точного аналога метода анализа по непосредственным
H. Хомский Формальные свойства грамма'гик 223 являющим разрабатываемого в современной лингвистике. Лам- 2е [43—35 ] также построил несколько систем в общем того же тн- о с некоторыми дополнительными изменениями и исследовал "опоос об их применимости к лингвистическому материалу. Схо- «неСодходы также имеются в работах [15, 16 74, 77 Здесь мы * Дуем изложению Бар-Хнллела, Гаифмана и Шамнра [3]. Система категорий может быть установлена следующим путем, пмбеоем конечное число простых категорий (напрнмер, категория .„я предложений н категория п для имен и именных групп; это ^ннственные простые категории, рассматривавшиеся в системе Айдукевнча). Простые категории суть категории. Если а и р - ка- «горнн то [о/р ] (читается: « над р») и [Др ] (читается: « под р») тякже будут категориями — назовем их производными категория- категориями Тати образом получаются категории, такие, как [я/s], Minis]] или lln\n]\ls,n}l Других категории нет. Каждому элементу терминального словаря VT присваивается одна нлн не- несколько категорий. Множество категории, сопоставленных эле- элементам Vt , вместе со списками членов этих категории составляет грамматику О. Имеется два правила сведения: а) последовательность двух символов, обозначающих категории, вида [а/р], р сво- сводится К а, б) последовательность двух символов, рии (82) б) последоват у обозначающих категории, вида а, [а\р] сво- сводится к р. д р Эти правила напоминают правила сокращения дробей в ариф- арифметике, чем и были вызваны такие обозначения. _ Если теперь дана цепочка х элементов VT , заменим каждый сим- символ из Vr в этой цепочке символом, обозначающим категорию, к которой он принадлежит, и таким образом получим последователь- последовательность символов категорий. Поскольку каждый член цепочки может принадлежать к нескольким категориям, каждой цепочке ставится в соответствие несколько последовательностей символов категории. Обозначим эти последовательности С,(х),...,С (*). Последователь- Последовательно применяя правила сведения, к некоторой С,(*), мы получим, что либо С,(х) в конце концов Сведется к s, либо она в конце концов сведется к некоторой последовательностн одного или более симво- символов, отличной от s. Если, для некоторого i С (х) сводится к s, мы говорим, что грамматика G порождает х; если такого i нет, G не порождает х. Множество цепочек, порождаемых грамматикой G, есть язык, порождаемый G. Так же как и для других ранее обсуж- обсуждавшихся порождающих грамматик, считать, что G П°Р°ЖД^Т предложения; или считать, что она получает на вход цепочки н ре- решает являются ли они предложениями (т.е. как распознающий ме- механизм),— это просто вопрос терминологии. Обычно для толы*° чТо описанных категориальных грамматик употребляется вторс>и Мз этих оборотов речи. • Функционирование такой грамматики можно пояснить на пРи- мере. Пусть наша грамматика содержит простые категории /* и s, слова John, Mary, loves, died, is, old, very (Джон, Мэри, л^Ит, умер, есть, старый, очень) н следующее распределение слов )*° Ка- Категориям: John, Mary — вп; died — в [n\s]; loves — в [/Asl/rc, old — в [nln]; very — в [nlnVlnln]; is — в [n\s]/[n!n]. 'Гаким образом, непереходный глагол (такой, как died) рассматриРаеТся как «оператор», который «превращает» нмя существительное, стОя- щее слева от него, в предложение; переходный глагол (loves') Рас- Рассматривается как оператор, превращающий имя существите^Ное, стоящее справа от него, в непереходный глагол; прилагат^ЛЬ|юе рассматривается как оператор, превращающий существите^Чое, стоящее справа от него, в существительное; наречие very рассмат- рассматривается как оператор, превращающий прилагательное, сГ0Я1Дее справа от него, в прилагательное; связка is рассматривается как оператор, превращающий прилагательное, стоящее справа of н^го, в непереходный глагол. Цепочки, показанные ниже, cвoдяfся к s следующим образом: a) John died n[n\s\ s 6) John loves Mary л, \n\s]/n, n s в) John is very old n, [n\»)/[n/n], _[n/n]/[n/nb J (83) П, [ll\s\ Грамматика описанного типа называется двунаправлен но& ка- категориальной грамматикой. Если все производные категории Грам. матики имеют вид [Др ] или все имеют вид [а/р ], эта систеУ18 Чазы- вается однонаправленной категориальной грамматикой. АйДУ^евич рассматривал только второй вид категорий, поскольку он вна- вначале занимался системами бесскобочной записи, где функторы Пред- Предшествуют аргументам. Разумеется, можно рассматривать однонаправленные f3 Двуна- Двунаправленные категориальные снстемы как порождающие г[РамМати- ки. Встает вопрос об их связях и отношениях друг с друг°М и с
324 И. Хомский выше рассмотренными системами. Бар-Хиллел, Гайфман иШамир [3] показали следующее. Теорема 36. Семейства однонаправленных категориальных грамматик, двунаправленных категориальных грамматик и бес- бесконтекстных грамматик слабо эквивалентны друг другу. Если G — двунаправленная категориальная грамматика, то существует бесконтекстная грамматика, порождающая тот же язык, что и О, и если G есть бесконтекстная грамматика, то существует однонаправленная категориальная грамматика, порождающая тот же язык, что и G. Несколько неожиданным следствием этого ре- результата является тот факт, что класс однонаправленных катего- категориальных грамматик эквивалентен по своей порождающей способ- способности полному классу двунаправленных категориальных грамматик. Шамнр указал недавно (личное сообщение), что для теоремы 36 существует доказательство, весьма похожее на доказательство эк- эквивалентности бесконтекстных грамматик н автоматов PDS. Необходимо подчеркнуть, что отношение, о котором идет речь в теореме 36,— это отношение слабой эквивалентности. Из него не •следует, что для любой заданной грамматики одного из этих видов всегда найдется грамматика другого вида, дающая распределение по категориям, сравнимое по сложности или естественности, или дающая такую же систему помеченных скобок (структуру состав- составляющих) для подцепочек. По-видимому, как раз для тех частей реальных языков, которые легко и естественно могут быть описаны при помощи бесконтекстных грамматик, соответствующее описание в терминах двунаправленной категориальной грамматики очень •быстро чересчур усложняется, а об естественном описании с по- помощью однонаправленной категориальной грамматики, конечно, ле может быть н речи. Системы, предложенные Ламбеком, в некоторых отношениях ¦отличаются от только что описанной; в частности, они позволяют большую свободу в приписывании категорий. Так, его правила све- сведения утверждают, например, что категория а. одновременно яв- является и категорией p/[a\fi], так что этим или иным путем слож- сложность и длина последовательности символов категорий, сопостав- сопоставленных цепочке, может возрастать прн применении правил приве- приведения. Поэтому непосредственно не очевидно, как это было в ранее рассмотренных системах, что порождаемый язык представляет со- собой рекурсивное множество. Однако Ламбек показал, что изучае- изучаемые им системы в действительности являются разрешимыми. Не известно, как связаны системы Ламбека с двунаправленными ка- категориальными грамматиками или с бесконтекстными граммати- грамматиками, хотя можно ожидать, что эта связь окажется довольно тес- яой, возможно даже слабой эквивалентностью. Формальные свойства грамматик 225 Привлекательность различных видов категориальных грамма- грамматик состоит в том, что онн не имеют почти никаких грамматических правил, не включенных в словарь, т.е. если грамматика G дает рас- распределение слов из конечного словаря W по конечному числу ка- категорий, простых или производных, то для каждой цепочки х в словаре Vt возможно определить, верно ли, что G порождает х, прн помощи вычислительного процесса, использующего правила приведения, которые одинаковы для всех грамматик заданного типа и поэтому не должны входить в состав грамматики G. Дейст- Действительно, существует традиционная точка зрения, которая отож- отождествляет грамматику с множеством грамматических свойств слов или морфем (ср. [57], стр. 149), и целесообразно будет подчеркнуть, что вышеописанный подход дает точное выражение этих понятий. В последнее время Мэтьюз [42 ] исследовал обобщение теории грамматик непосредственных составляющих, прн котором допус- допускаются некоторые типы прерванных составляющих. Продолжая следовать обозначениям, принятым в разд. 4 предыдущей главы, рассмотрим правила вида Л^^Ыср,,, гДе ч>0. Мы интерпрети- интерпретируем такое правило как в применении к цепочке $Аа1..,апх, дающее цепочку +9iai---an<fsX (гДе а(=?е)>и в применении к цепочке ||>Л«,... ... am(m<n), дающее цепочку tyf^... amy2. При этих условиях бесконтекстная грамматика может рассматриваться как грамматика, имеющая только правила вида Л-^ГО]?^ Мэтьюз также естест- естественным образом обобщил это понятие на случай разрывных кон- контекстных правил. Для любой грамматики определим теперь прямой вывод, явно определенный в разд. 4.2, стр. 178, и прямую разрыв- разрывную грамматику как грамматику с правилами только что описан- описанного вида (нлн более общего контекстного разрывного типа) и с ограничением на применение правил, разрешающим только пря- прямые выводы (ср. с разд. 4.2). Мэтьюз показал, что прямые разрыв- разрывные грамматики могут порождать только бесконтекстные языки, так что это обобщение не увелнчнвает порождающей способности. Очевидно, то же самое верно и для обратных разрывных грамма- грамматик, которые разрешают вывод так, как это описано на стр. 178 (на каждом шаге заменяется самый правый нетерминальный сим- символ), н в которых правило вида Л-^Ысра понимается так, что нужно поставить ср! на п символов влево (или на левый конец) при замене символа Л, вместо того чтобы ставить ее на п символов впра- вправо (или на правый конец), как в случае прямой разрывной грамма- грамматики (аналогично для контекстных разрывных правил). Мэтьюз распространил этот результат на правила со многими разрывами и указал, что даже допущение двусторонних ранрывных правил не увеличивает порождающей способности контекстных грамматик. Были предложены н различные другие модели лингвистической структуры, но постольку, поскольку они могут быть интерпретп-
Н. Хомский рованы как специальный внд порождающих грамматик (т.е. по- поскольку онн определяют грамматики, в явном виде выдающие ин- информацию о структуре предложения), они, по-видимому, большей частью попадают в область теории грамматик непосредственных составляющих и даже почти всегда в область теории бескон- бесконтекстных грамматик. Обсуждение этих вопросов см. в работах [24,52]. Этим заканчивается наш обзор, посвященный формальным свой- свойствам грамматик. Вряд лн нужно специально отмечать предвари- предварительный характер большей части наших рассмотрений. Как явст- явствует из приложенного списка литературы, исследование этих воп- вопросов началось, собственно говоря, всего пять нли шесть лет назад, и многие нз упомянутых здесь работ еще продолжаются. Важно снова подчеркнуть, что рассмотренные системы, которые так хорошо доказали свою пригодность для абстрактно-математиче- абстрактно-математических исследований, несомненно, недостаточны, чтобы представить ис- исчерпывающим образом всю сложность н богатство синтаксических механизмов, используемых в естественных языках, в особенности из-за того, что, ограничившись системами подстановок, мы не включили в рассмотрение грамматических трансформаций, подоб- подобных обсуждавшимся в разд. 5 предыдущей главы. В то же время этн системы, по-видимому, достаточно широки, чтобы охватить тео- теории грамматической структуры, предложенные в традиционной н современной лингвистике, равно как н в недавних новых работах по автоматическому синтаксическому анализу, так же как и неявно содержащиеся в традиционных или современных описательных ра- работах, за исключением рассмотрения трансформаций. Некоторые характерные черты естественных языков (например, расстановка скобок в запутанных фразах, категоризация лексических типов и типов составляющих, вставленные друг в друга зависимости) по- появляются в системах рассмотренного вида. Поэтому изучение та- таких систем непосредственно связано с изучением природы естест- естественного языка. Далее, очевидно, что плодотворное изучение абстрактных свойств столь богатых и сложных систем, как естественные языки, или организмов, достаточно мощных, чтобы овладевать и пользоваться такими системами, потребует более разнообразных средств н более глубокого проникновения в сущность формальных систем, чем то, которым мы располагаем в настоящее время, а это может быть дос- достигнуто только путем изучения систем, подобных языку, но более простых, чем имеющиеся естественные языки. Но будут ли эти более мощные системы служить объектом для серьезных формальных исследований — это, конечно, вопрос, над разрешением которого мы в настоящее время можем только гадать. Формальные свойства грамматик 227 ЛИТЕРАТУРА Ajdukiewicz К., Die syntaktische Konnexitat, Studia Phitoso- phica, I A935), 1—27. В a r-H i 1 1 e 1 Y., A quasi-arithmetical notation for syntactic descropti- on, Language, 29 A953), 47—58. В a r-H i 1 1 e 1 Y., G a I [ m a n C, Shamir E., On categorial and phrase structure grammars, Bull. Res. Council of Israel, 9F A960), 1 — 16. В a r-H i 1 1 e 1 Y., P e r 1 e s M., Shamir E., On formal properties of simple phrase structure grammars, Tech. Rept. № 4, Office of Naval Research, Information Systems Branch, 1960; Zeitschrijt fur Phonetik, Spruchwissenschaft und Kommunikationsforschung, 14 A961), 143—172. В a r-H 1 1 1 e 1 Y., S h a m i r E., Finite state languages: formal repre- representation and adequacy problems, Bull. Res. Council of Israel, 8F A960), 155—166. Chomsky N., Systems of syntactic analysis, 3. Symbolic Logic, 18 A953), 242—256. Chomsky N.. Three models for the desctiption of language, IRE Trans. on Inform. Theory, 1T-2 A956), 113—124. (Русский перевод: Хомс- Хомский H., Три модели для описания языка, Кибернетический сборник, вып. 2, ИЛ, 1961, 237—266.) Chomsky N., On certain formal properties of grammars, Information and Control, 2 A959), 137—167. (Русский перевод: X омский Н., О некоторых формальных свойствах грамматик, Кибернетический сбор- сборник, вып. 5, ИЛ, 1962, 279—312.) С h о m s k у N.. A note on phrase structure grammars, Information and Control, 2 A959), 393—395. (Русский перевод: X о м с к н й Н., Замет- Заметка о грамматиках непосредственных составляющих, Кибернетический сборник, вып. 5, ИЛ, 1962, 312—315.) Chomsky N.,On the notion«Rule of grammar», в сб. J a k о b s о п R. (Ed.), Structure od language and its mathematical aspects, Proc. 12tli Sympos. in Appl. Math. Providence, American Mathematical Society, 1961; см. также К a t z J., F о d q r J. (Eds.), Readings in the Philoso- Philosophy of Language, New York, Prentice-Hall, 1963. (Русский перевод: Х о ы- с к и й Н., О понятии «правило грамматики», в сб. «Новое в лингвисти- лингвистике», вып. 4, изд-во «Прогресс», 1965, 34—65). Chomsky N.. Context-free grammars and pushodown storage RLE, Quart. Prog. Rept. № 65, Cambridge, Mass., M. I. T., March, 1962. С h о m s k у N., The logical basis for linguistic theory, Proc. IXth Int. Cong, of Linguists, 1962; см. также К a t z J., F о d о r J. (Eds.), Readings in the Philosophy of Language, New York, Prentice-Hall, 1963. (Русский перевод: Хомскнй Н., Логические основы лингвистической теории, в сб. «Новое в лингвистике», вып. 4, нзд-во «Прогресс», 1965, 465—575.) Chomsky N., Miller G. A., Finite state languages, Information and Control, 1 A958), 91 — 112. (Русский перевод: X о м с к и й Н., М и л- л е р Д., Языки с конечным числом состояний, Кибернетический сбор- сборник, вып. 4, ИЛ, 1962, 231—255.) Culik К-, Some notes on finite state languages and events represented by finite automata using labelled graphs, Casopis pro pestovdni matematiky (Prague), 86 A961), 43—55. Curry H., Some logical aspects of grammatical structure, n сб. Jakob- son R. (Ed.), Structure of language and its mathematical aspects, Proc. 12th Sympos. in Appl. Math., Providence, American Mathematical So- Society, 1961. (Русский перевод: К а р р и Г., Некоторые логические аспек- аспекты грамматической структуры, в сб. «Новое в лингвистике», вып. 4, изд-во «Прогресс», 1965, 97—116.) 10. 12. 13. 14. 15.