Формальные свойства грамматик - Хомский Н.
Скачать (прямая ссылка):
Возьмем, в частности, два множества цепочек X= Jx1,и Y= t/n\. Определим Lx как МНОЖеСТВО всех ЦеПОЧеК Z=Xkt...
...xkt(ks^n), т.е. всех цепочек, разлагающихся в соединение элементов множества Х\ в терминах разд. 1.2 множество Lx было бы обозначено (X1,...,Xit)*. Аналогично определим Ly . Назовем Lx кодом (ср. с разд. 2 предыдущей главы), еслн каждая цепочка Lx однозначным образом разлагается (дешифруется) на элементы нз X (аналогично для К). Рассмотрим теперь грамматику Gx с правилами S-^xiS и грамматику Gy с правилами S-^ylS (и правилом S-»e). По теореме 35 множество цепочек, неоднозначных относительно Gx (как н относительно Gy), регулярно, и, значит, существует алгоритм для определения ТОГО, пусто оно или нет. Следовательно, существу-
Н. Хомский
ет алгоритм, позволяющий определить, образует лн данное множество цепочек код илн нет (см. работу [56]). Однако мы не можем узнать, одинаково ли не являются кодами данные два множества (ср. с разд. 4.5).
Пусть теперь Ght удовлетворяют условиям теоремы 35, a Gr другая односторонняя линейная грамматика, которой удовлетворяет ряд г'. Из теоремы Маркова н предложения (78) следует, что невозможен алгоритм, определяющий для произвольного случая этого рода, существует лн цепочка х, для которой < г,х > = ( г', х > . Из теоремы 35 следует, что прн любом фиксированном k существует алгоритм, определяющий, когда непусто пересечение LkO L1k, где Lk — [х\ < г,х > Lk'=\x\ < г', х ХА|. Отсюда видно, что не-
возможен алгоритм, определяющий, существует ли такое k, для которого LitOLk' непусто (Шюценберже, личное сообщение).
4.8. Языки программирования'
Программа цифровой вычислительной машины может рассматриваться как цепочка символов в некотором фиксированном алфавите. Язык программирования может рассматриваться как бесконечное множество цепочек, каждая из которых есть программа. Он имеет грамматику, точно определяющую алфавит, и множество правил построения программ. Гинзбург н Райс указывают, что язык АЛГОЛ имеет бесконтекстную грамматику, хотя н не одностороннюю линейную и не последовательную. Это наблюдение показывает, что интересно попытаться интерпретировать результаты, полученные в общей теории бесконтекстных языков, считая, что они составляют класс потенциальных языков программирования для решения задач.
Заметим, в частности, что язык программирования должен иметь однозначную грамматику в смысле, определенном выше в разд. 4.5. Если множество правил, применяющихся при построении программ, составляет неоднозначную грамматику, то может получиться что программист составит программу, которую машина должна интерпретировать определенным образом, а машина интерпретирует ее совершенно иначе. Мы, однако, видели, что некоторые бесконтекстные языки существенно неоднозначны относительно класса бесконтекстных грамматик (разд. 4.5, теорема 29). Поэтому имеется хотя бы абстрактная возможность того, что некоторое бесконечное множество «программ» нельзя будет охарактеризовать при помощи однозначной грамматики, если ограничиться темн методами построения программ, которые выразимы в пределах теории бесконтекстных грамматик. Кроме того, мы видели, что невозможен алгоритм, распознающий по заданной бесконтекстной грамматике, является ли она однозначной (разд. 4.5, теорема 28). Следовательно, в отдельных случаях задача распознавания однозначности
Формальные свойства грамматик
221
грамматики (т.е. удовлетворяет ли предлагаемый язык программирования минимальным требованиям адекватности) может оказаться весьма нелегкой.
Возьмем теперь проблему перевода с одного языка программирования L1 на другой Lt (например, машинный код или другой язык программирования более высокого порядка). Мы можем рассматривать ее как проблему построения конечного преобразователя («компилятора») Т, такого, что T(L1)=La. В общем случае нет причин предполагать, что такой преобразователь существует. Более того, мы знаем, что общая проблема распознавания по двум бесконтекстным языкам L1 и L2 существует ли такой преобразователь Т, что T(L1)=Ls, алгоритмически неразрешима (разд. 4.4, теорема 27), Отсюда вытекает, что при решении проблемы перевода произвольных систем этого рода, по-видимому, смогут возникнуть весьма сложные вопросы (Гинзбург, личное сообщение).
5. Категориальные грамматики
Основное содержание традиционного грамматического анализа составляет расчленение предложения на все более и более мелкие составляющие его частн-сннтагмы вплоть до категорий отдельных слов; при этом имеется лишь конечное число типов, к которым принадлежат эти синтагмы (именная группа, глагольная группа, имя существительное н т.п.). За последние двадцать лет в дескриптивной лингвистике появились различные попытки более четко и ясно сформулировать этот традиционный1 подход. Здесь можно прежде всего назвать Харриса (работа [25], переработанная затем в гл. 16 работы [26 J), затем Уэллса [76 ] и недавние работы Пайка и его коллег по тагмемике (in Tagmemics) (см., например, работу [18]). Порождающие системы, рассмотренные в разд. 3 и 4, дают один возможный метод точного выражения некоторых из этих идей. Ho были и другие, более или менее связанные с этим подходы, которые лдесь лишь бегло упэмянуты.
