Формальные языки и грамматики

  • Tutorial

Мотивация


Время от времени на Хабре публикуются посты и переводные статьи, посвященные тем или иным аспектам теории формальных языков. Среди таких публикаций (не хочется указывать конкретные работы, чтобы не обижать их авторов), особенно среди тех, которые посвящены описанию различных программных инструментов обработки языков, часто встречаются неточности и путаница. Автор склонен считать, что одной из основных причин, приведших к такому прискорбному положению вещей, является недостаточный уровень понимания идей, лежащих в основании теории формальных языков.

Этот текст задуман как популярное введение в теорию формальных языков и грамматик. Эта теория считается (и, надо сказать, справедливо) довольно сложной и запутанной. На лекциях студенты обычно скучают и экзамены тем более не вызывают энтузиазма. Поэтому и в науке не так много исследователей в этой тематике. Достаточно сказать, что за все время, с зарождения теории формальных грамматик в середине 50-х годов прошлого века и до наших дней, по этому научному направлению было выпущено всего две докторских диссертации. Одна из них была написана в конце 60-х годов Алексеем Владимировичем Гладким, вторая уже на пороге нового тысячелетия — Мати Пентусом.

Далее в наиболее доступной форме описаны два основных понятия теории формальных языков: формальный язык и формальная грамматика. Если тест будет интересен аудитории, то автор дает торжественное обещание разродиться еще парой подобных опусов.


Формальные языки


Коротко говоря, формальный язык — это математическая модель реального языка. Под реальным языком здесь понимается некий способ коммуникации (общения) субъектов друг с другом. Для общения субъекты используют конечный набор знаков (символов), которые проговариваются (выписываются) в строгом временном порядке, т.е. образуют линейные последовательности. Такие последовательности обычно называют словами или предложениями. Таким образом, здесь рассматривается только т.н. коммуникативная функция языка, которая изучается с использованием математических методов. Другие функции языка здесь не изучаются и, потому, не рассматриваются.

Чтобы лучше разобраться в том, как именно изучаются формальные языки, необходимо сначала понять, в чем заключаются особенности математических методов изучения. Согласно Колмогорову и др. (Александров А.Д., Колмогоров А.Н., Лаврентьев М.А. Математика. Ее содержание, методы и значение. Том 1. М.: Издательство Академии Наук СССР, 1956.), математический метод, к чему бы он ни применялся, всегда следует двум основным принципам:
  1. Обобщение (абстрагирование). Объекты изучения в математике — это специальные сущности, которые существуют только в математике и предназначены для изучения математиками. Математические объекты образуются путем обобщения реальных объектов. Изучая какой-нибудь объект, математик замечает только некоторые его свойства, а от остальных отвлекается. Так, абстрактный математический объект «число» может в реальности обозначать количество гусей в пруду или количество молекул в капле воды; главное, чтобы о гусях и о молекулах воды можно было
    говорить как о совокупностях. Из такой «идеализации» реальных объектов следует одно важное свойство: математика часто оперирует бесконечными совокупностями, тогда как в реальности таких совокупностей не существует.
  2. Строгость рассуждений. В науке принято для выяснения истинности того или иного рассуждения сверять их результаты с тем, что существует в действительности, т.е. проводить эксперименты. В математике этот критерий проверки рассуждения на истинность не работает. Поэтому выводы не проверяются экспериментальным путем, но принято доказывать их справедливость строгими, подчиняющимися определенным правилам, рассуждениями. Эти рассуждения называются доказательствами и доказательства служат единственным способом обоснования верности того или иного утверждения.

Таким образом, чтобы изучать языки с помощью математических методов, необходимо сначала выделить из языка его свойства, которые представляются важными для изучения, а затем эти свойства строго определить. Полученная таким образом абстракция будет называться формальным языком — математической моделью реального языка. Содержание конкретной математической модели зависит от того, какие свойства важны для изучения, т.е. что планируется в данный момент выделить и изучать.

В качестве известного примера такой математической абстракции можно привести модель, известную под неблагозвучным для русского уха названием «мешок слов». В этой модели исследуются тексты естественного языка (т.е. одного из тех языков, которые люди используют в процессе повседневного общения между собой). Основной объект модели мешка слов — это слово, снабженное единственным атрибутом, частотой встречаемости этого слова в исходном тексте. В модели не учитывается, как слова располагаются рядом друг с другом, только сколько раз каждое слово встречается в тексте. Мешок слов используется в машинном обучении на основе текстов в качестве одного из основных объектов изучения.

Но в теории формальных языков представляется важным изучить законы расположения слов рядом друг с другом, т.е. синтаксические свойства текстов. Для этого модель мешка слов выглядит бедной. Поэтому формальный язык задается как множество последовательностей, составленных из элементов конечного алфавита. Определим это более строго.

Алфавит представляет собой конечное непустое множество элементов. Эти элементы будем называть символам. Для обозначения алфавита обычно будем использовать латинское V, а для обозначения символов алфавита — начальные строчные буквы латинского алфавита. Например, выражение V = {a,b} обозначает алфавит из двух символов a и b.

Цепочка представляет собой конечную последовательность символов. Например, abc — цепочка из трех символов. Часто при обозначении цепочек в символах используют индексы. Сами цепочки обозначают строчными символами конца греческого алфавита. Например, omega = a1...an — цепочка из n символов. Цепочка может быть пустой, т.е. не содержать ни одного символа. Такие цепочки будем обозначать греческой буквой эпсилон.

Наконец, формальный язык L над алфавитом V — это произвольное множеств цепочек, составленных из символов алфавита V. Произвольность здесь означает тот факт, что язык может быть пустым, т.е. не иметь ни одной цепочки, так и бесконечным, т.е. составленным из бесконечного числа цепочек. Последний факт часто вызывает недоумение: разве имеются реальные языки, которые содержат бесконечное число цепочек? Вообще говоря, в природе все конечно. Но мы здесь используем бесконечность как возможность образования цепочек неограниченной длины. Например, язык, который состоит из возможных имен переменных языка программирования C++, является бесконечным. Ведь имена переменных в C++ не ограничены по длине, поэтому потенциально таких имен может быть бесконечно много. В реальности, конечно, длинные имена переменных не имеют для нас особого смысла т.к. к концу чтения такого имени уже забываешь его начало. Но в качестве потенциальной возможности задавать неограниченные по длине переменные, это свойство выглядит полезным.

Итак, формальные языки — это просто множества цепочек, составленных из символов некоторого конечного алфавита. Но возникает вопрос: как можно задать формальный язык? Если язык конечен, то можно просто выписать все его цепочки одну за другой (конечно, можно задуматься, имеет ли смысл выписывать цепочки языка, имеющего хотя бы десять тысяч элементов и, вообще, есть ли смысл в таком выписывании?). Что делать, если язык бесконечен, как его задавать? В этот момент на сцену выходят грамматики.

Формальные грамматики


Способ задания языка называет грамматикой этого языка. Таким образом, грамматикой мы называем любой способ задания языка. Например, грамматика L = {a^nb^n} (здесь n — натуральное число) задает язык L, состоящий из цепочек вида ab, aabb, aaabbb и т.д. Язык L представляет собой бесконечное множество цепочек, но тем не менее, его грамматика (описание) состоит всего из 10 символов, т.е. конечна.

Назначение грамматики — задание языка. Это задание обязательно должно быть конечным, иначе человек не будет в состоянии эту грамматику понять. Но каким образом, конечное задание описывает бесконечные совокупности? Это возможно только в том случае, если строение всех цепочек языка основано на единых принципов, которых конечное число. В примере выше в качестве такого принципа выступает следующий: «каждая цепочка языка начинается с символов a, за которыми идет столько же символов b». Если язык представляет собой бесконечную совокупность случайным образом набранных цепочек, строение которых не подчиняется единым принципам, то очевидно для такого языка нельзя придумать грамматику. И здесь еще вопрос, можно или нет считать такую совокупность языком. В целях математической строгости и единообразия подхода обычно такие совокупности языком считают.

Итак, грамматика языка описывает законы внутреннего строения его цепочек. Такие законы обычно называют синтаксическими закономерностями. таким образом, можно перефразировать определение грамматики, как конечного способа описания синтаксических закономерностей языка. Для практики интересны не просто грамматики, но грамматики, которые могут быть заданы в рамках единого подхода (формализма или парадигмы). Иначе говоря, на основе единого языка (метаязыка) описания грамматик всех формальных языков. Тогда можно придумать алгоритм для компьютера, который будет брать на вход описание грамматики, сделанное на этом метаязыке, и что-то делать с цепочками языка.

Такие парадигмы описания грамматик называют синтаксическими теориями. Формальная грамматика — это математическая модель грамматики, описанная в рамках какой-то синтаксической теории. Таких теорий придумано довольно много. Самый известный метаязык для задания грамматик — это, конечно, порождающие грамматики Хомского. Но имеются и другие формализмы. Один из таких них — окрестностные грамматики, будет описан чуть ниже.

С алгоритмической точки зрения грамматики можно подразделить по способу задания языка. Имеются три основных таких способа (вида грамматик):
  • Распознающие грамматики. Такие грамматики представляют собой устройства (алгоритмы), которым на вход подается цепочка языка, а на выходе устройство печатает «Да», если цепочка принадлежит языку, и «Нет» — в противном случае.
  • Порождающие грамматики. Этот вид устройств используется для порождения цепочек языков по требованию. Образно говоря, при нажатии кнопки будет сгенерирована некоторая цепочка языка.
  • Перечисляющие грамматики. Такие грамматики печатают одну за другой все цепочки языка. Очевидно, что если язык состоит из бесконечного числа цепочек, то процесс перечисления никогда не остановится. Хотя, конечно его можно остановить принудительно в нужный момент времени, например, когда будет напечатана нужная цепочка.

Интересным представляет вопрос о преобразовании видов грамматики друг в друга. Можно ли, имея порождающую грамматику, построить, скажем, перечисляющую? Ответ — да, можно. Для этого достаточно генерировать цепочки, упорядочив их, скажем по длине и порядку символов. Но превратить перечисляющую грамматику в распознающую в общем случае нельзя. Можно использовать следующий метод. Получив на вход цепочку, запустить процесс перечисления цепочек и ждать, напечатает ли перечисляющая грамматика эту цепочку или нет. Если такая цепочка напечатана, то заканчиваем процесс перечисления и печатаем «Да». Если цепочка принадлежит языку, то она обязательно будет напечатана и, таким образом, распознана. Но, если цепочка не принадлежит языку, то процесс распознавания будет продолжаться бесконечно. Программа распознающей грамматики зациклится. В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих. Это следует иметь ввиду, когда сравнивают порождающие грамматики Хомского и распознающие машины Тьюринга.

Окрестностные грамматики


В середине 60-х годов советский математик Юлий Анатольевич Шрейдер предложил простой способ описания синтаксиса языков на основе т.н. окрестностных грамматик. Для каждого символа языка задается конечное число его «окрестностей» — цепочек, содержащих данный символ (центр окрестности) где-то внутри. Набор таких окрестностей для каждого символа алфавита языка называется окрестностной грамматикой. Цепочка считается принадлежащей языку, задаваемому окрестностной грамматикой, если каждый символ этой цепочки входит в нее вместе с некоторой своей окрестностью.

В качестве примера рассмотрим язык A = {a+a, a+a+a, a+a+a+a,...}. Этот язык представляет собой простейшую модель языка арифметических выражений, где роль чисел играет символ «a», а роль операций — символ "+". Составим для этого языка окрестностную грамматику. Зададим окрестности для символа «a». Символ «a» может встречаться в цепочках языка A в трех синтаксических контекстах: вначале, между двумя символами "+" и в конце. Для обозначения начала и конца цепочки введем псевдосимвол "#". Тогда окрестности символа «a» будут следующими: #a+, +a+, +a#. Обычно для выделения центра окрестности этот символ в цепочке подчеркивается (ведь в цепочке могут быть и другие такие символы, которые не являются центром!), здесь этого делать не будем за неимением простой технической возможности. Символ "+" встречается только между двух символов «a», поэтому для него задается одна окрестность, цепочка a+a.

Рассмотрим цепочку a+a+a и проверим, принадлежит ли она языку. Первый символ «a» цепочки входит в нее вместе с окрестностью #a+. Второй символ "+" входит в цепочку вместе с окрестностью a+a. Подобное вхождение можно проверить и для остальных символов цепочки, т.е. данная цепочка принадлежит языку, как и следовало ожидать. Но, например, цепочка a+aa языку A не принадлежит, поскольку последний и предпоследний символы «a» не имеют окрестностей, с которыми они входят в эту цепочку.

Не всякий язык может быть описан окрестностной грамматикой. Рассмотрим, например, язык B, цепочки которого начинаются либо с символа «0», либо с символа «1». В последнем случае далее в цепочке могут идти символы «a» и «b». Если же цепочка начинается с нуля, то далее могут идти только символы «a». Нетрудно доказать, что для этого языка нельзя придумать никакой окрестностной грамматики. Легитимность вхождения символа «b» в цепочку обусловлена ее первым символом. Для любой окрестностной грамматики, в которой задается связь между символами «b» и «1» можно будет подобрать достаточно длинную цепочку, чтобы всякая окрестность символа «b» не доставала до начала цепочки. Тогда в начало можно будет подставить символ «0» и цепочка будет принадлежать языку A, что не отвечает нашим интуитивным представлениям о синтаксическом строении цепочек этого языка.

С другой стороны, легко можно построить конечный автомат, который распознает этот язык. Значит, класс языков, которые описываются окрестностными грамматиками, уже класса автоматных языков. Языки, задаваемые окрестностными грамматиками, будем называть шрейдеровскими. Таким образом, в иерархии языков можно выделить класс шрейдеровских языков, который является подклассом автоматных языков.

Можно сказать, что шрейдеровские языки задают одно простое синтаксическое отношение — «быть рядом» или отношение непосредственного предшествования. Отношение дальнего предшествования (которое, очевидно, присутствует в языке B) окрестностной грамматикой задано быть не может. Но, если визуализировать синтаксические отношения в цепочках языка, то для диаграмм отношений, в которые превращаются такие цепочки, можно придумать окрестностную грамматику.
Share post

Comments 23

    +11
    Вспоминаю курс проектирования трансляторов, который проходил в университете. Занимательная вещь.
    А статья как-то неожиданно закончилась, ожидал больше. Жду продолжения.
      +3
      «Среди таких публикаций», «автор склонен считать», «далее в наиболее доступной форме описаны», «согласно Колмогорову» и куча других сухих оборотов, характерных для формальных бумаг вроде научных статей, дипломных работ, справок из ГАИ, отчетов на госпредпиятиях и так далее.

      Как-то не вяжется с задумкой о том, что формат поста будет популярным. ;-)
        +7
        А по мне, так нормально написано. Научные статьи с «формальным» языком тоже разные бывают. Некоторые читаешь и засыпаешь после первого абзаца, а есть которые на одном дыхании читаются.
        Автору спасибо, прочитал на одном дыхании.
          +1
          Действительно, логично — статья о формальных языках написана «формальным» языком :-)
        +5
        Я надеюсь это только первая часть?
          +2
          Отлично написано! Спасибо, разжевали то, что не понял в универе. Жду продолжения!
            0
            Огромное спасибо за статью!
            Очень надеюсь, что в возможных следующих публикациях будут рассмотрены прикладные аспекты теории формальных языков. Кстати говоря, работ в области символической динамики, идейно близкой к формальным языкам, в последнее время все больше и больше.
              +1
              А продолжение будет? Контекстно-независимые грамматики, LL/LR разбор и т.п.? :)
                +1
                Будет, чуть попозже. Наверное, порождающие грамматики. Можно и про методы синтаксического анализа.
                +1
                Спасибо за статью, продолжайте, тема интересная!
                  +1
                  Спасибо за статью, все понятно и доступно!

                  Один вопрос по следующей цитате:
                  В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих

                  Нет ли здесь опечатки? Мне показалось, что мощность распознающих грамматик должна быть больше мощности порождающих и перечисляющих, потому что, имея распознающую грамматику, можно получить порождающую или перечисляющую, но не наоборот. Возможный алгоритм — перебирать все цепочки символов в алфавитном порядке и выводить те из них, которые проверены распознающей грамматикой на принадлежность языку.
                    0
                    Под мощностью класса грамматики здесь подразумевается возможность задавать некоторый класс языков. Некоторые языки, которые могут быть заданы перечисляющей грамматикой, не могут быть заданы распознающей грамматикой, хотя обратное утверждение, как Вы верно заметили, всегда выполняется. Т.е. имеется вложение класса распознаваемых языков в класс перечислимых. В теории алгоритмов используются термины рекурсивное и рекурсивно-перечислимое множество. Там утверждение о неэквивалентности этих классов множеств (языков) — одна из основных теорем.
                      0
                      ЕМНИП, рекурсивные множества отличаются от рекурсивно-перечислимых ровно тем, что для первых существуют распознающие алгоритмы, которые останавливаются на всех возможных входах (т.е., входящих в множество и не входящих), тогда как для вторых — только частичные алгоритмы, т.е. такие, которые заведомо останавливаются на элементах множества, но могут зацикливаться на других входах.

                      По-моему, все эти основы детально и доступно разбираются в первых главах классической книги А.Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции, т.1.
                        0
                        Спасибо, понятно, хотя я поначалу запутался.
                      +1
                      Спасибо за статью.

                      Впервые вижу, чтобы автоматы называли грамматикам — зачем путаете добрых людей? :)

                      ЕМНИП, по Хопкрофту и Ульману, более правильно называть способы задания языков «формализмами», тогда грамматики — порождающие формализмы (можно получить какую-то, не очень заранее известно какую, цепочку последовательным раскрытием правил), а автоматы — распознающие формализмы (можно алгоритмически ответить на вопрос, принадлежит ли данная цепочка в алфавите V языку или нет).

                      Перечисляющая же «грамматика» — это попросту говоря «список всех цепочек языка», который в случае бесконечного языка попросту не является конечным объектом (как, скажем, и гипотетическая запись числа Пи без ограничения числа значащих цифр).

                        +2
                        Грамматика — это необязательно автомат. Можно задать грамматику языка, которая не будет алгоритмом, т.е. не предназначена для задания языка. Например, окрестностная грамматика в этом тексте просто описывает синтаксические свойства языка, хотя может быть использована для задания распознающей грамматики очевидным образом. Такой вид грамматик, которые описывают язык, но не определяют алгоритм его задания, я называю описательными грамматиками. Другой вид описательной грамматики — категориальная грамматика Ламбека. Эта грамматика, конечно, превращается в алгоритм распознавания цепочек, т.е. в исчисление, которое применяется к цепочке на основе правил редукции, но важна и сама по себе, как описание синтаксических закономерностей языка.

                        Грамматики могут быть не только порождающие, как Вы написали выше, но и другого типа (распознающие, перечисляющие). Например, машину Тьюринга можно считать распознающей грамматикой, если использовать первую с вполне определенными довольно узкими целями: для распознавания множества цепочек. В этом смысле, определение грамматики уже определения алгоритма. Интересный вид перечисляющей грамматики — формальные степенные ряды над контекстно-свободными языками. Формализм, на мой взгляд, явно недооцененный.

                        Резюмируя, грамматика — это не только алгоритм задания языка, но и описание синтаксических закономерностей. В лингвистике, например, принимается во внимание исключительно второй аспект определения, на первый не особо обращают внимание. Конечно, с математической точки зрения важно понимать, как конкретный формализм задает язык, но это не обязательно самое главное в изучении синтаксических свойств языка. Теория алгоритмов изучает закономерности процессов вычислений и, ясно, что любое задание языка протекает во времени и, следовательно, является процессом. Отсюда можно сделать вывод, что любая грамматика, если ее применять как процесс задания языка, неизбежно превращается в один из возможных типов алгоритмов задания множества цепочек. Но грамматика — не алгоритм, но нечто большее. Поэтому я предпочитаю использовать термин «грамматика» вместо термина «автомат».
                          +1
                          Хмм… Похоже, что русскоязычный термин «формальная грамматика» (формализм) явно используется в более широком смысле, чем англоязычный «formal grammar» (набор правил вывода). Okay. :)
                        +5
                        Спасибо огромное за пост! Буду ждать продолжения. По поводу изложения материала. Я уже немного (скажу сразу достаточно поверхностно) погружался в эту тему. Литература есть, книжки есть, но всё-таки тема в целом непроста для восприятия. В некоторых книгах, методичках авторы сразу предоставляют кучу всяких формул, вводях кучу всяких терминов — многих это отталкивает, запутывает. Дак вот к чему я это. В Вашей статье я увидел как раз всё-таки больше объяснения, появления, разъяснения различных аспектов — считаю что так и надо делать. Чтобы больше людей разобралось в этой теме как раз нужно больше статей, где материал достаточно плавно и равномерно разъясняется, очень аккуратно и аргментированно вводятся формулы и делается так, чтобы читатель понял формулу и она не пугала его. Вот такие мысли и идеи, извиняюсь если немного бредовые :)
                          +1
                          Обычно для выделения центра окрестности этот символ в цепочке подчеркивается, здесь этого делать не будем за неимением простой технической возможности.


                          Подчеркивание — это просто.
                          • UFO just landed and posted this here
                              +1
                              Я попытался расширить понятие окрестностной грамматики, надо которым работали Борщев и Хомяков в 70-х годах. Владимир Борисович, кстати, делал доклад по этой работе на Диалоге . Идея та же, что и со шрейдеровскими окрестностными грамматиками. Только они задавали грамматики деревьев вывода контекстно-свободных грамматик. Т.е. они расширили понятие о языке. Язык — это не множество цепочек, но множество синтаксических структур, для КС-грамматик это деревья вывода. Для каждого символа можно задать множество его окрестностей, которые будут уже не цепочки, но «кусты» в дереве. Тогда дерево принадлежит языку в том и только в том случае, если каждая его вершина входит в это дерево вместе с некоторой своей окрестностью (кустом).

                              Идея здесь на самом деле топологическая. Окрестность — это аналог окрестности точки в топологии, т.е. открытого множества, содержащегося в топологии. Топология и есть ведь набор открытых множеств, заданных для каждой точки пространства. Множество в топологии считается открытым, если каждая точка входит в него вместе с какой-то своей окрестностью. Все это очень похоже на то, что имеется в грамматике. Я понял, что на самом деле в деревьях вывода визуализируется отношение иерархии («быть частью»), которое является основным в КС-грамматике. В цепочках языка имеется отношение непосредственного следования, т.е. «быть рядом». Такие отношения можно рисовать в виде графов, для них я даже придумал специальный термин — синтаграмма. Граф синтаксических отношений цепочки правильный (а значит и сама цепочка принадлежит языку), если каждая вершина этого графа входит в него вместе с некоторой своей окрестностью. Т.е. здесь полный аналог топологии и открытых множеств.

                              Понятие синтаграммы позволяет абстрагироваться от природы синтаксических отношений. Синтаграммы — это и деревья КС-грамматик, а также и обычные цепочки традиционного формального языка. Но графы — это не множества, поэтому понятия вложения в них другое. Два графа могут вкладываться друг в друга несколькими способами, тогда как для множеств вложение только одно. Значит, математический аппарат топологии сюда
                              непосредственно применить не получается. Но можно попытаться применить методы теории категорий, т.е. образовать категорию синтаграмм. В этой категории топологией будет как раз окрестностная грамматика. В теории категорий есть аналог понятия топологического пространства — это т.н. топология Гротендика. Но эта топология сама по себе только на основе категории не строится. Для нее необходимо еще одна категория, куда объекты исходной категории будут отображаться. Я понял, что для синтаксиса такая категория естественным образом появляется.

                              Если для каждой окрестностной синтаграммы задать множество ее смыслов, то получим функтор (отображение) из категории синтаксиса в категорию семантики этого языка. От природы смыслов мы абстрагируемся, просто считаем, что это элементы какого-то множества. С каждой базовой синтаксической конструкцией связано конечно множество смыслов. Причем наблюдается интересная закономерность. Если мы имеем какую-то синтаграмму, например, дерево вывода какого-то предложения в КС-грамматике Хомского, то она имеет покрытие окрестностными синтаграммами для каждой своей вершины. Т.е. имеется такой подъем, когда любая синтаграмма составляется из окрестностей — отображение наверх, к более сложным частям. С другой стороны, в семантике имеется спуск вниз. Если есть какой-то смысл, связанный с составной конструкцией и есть смыслы связанные с его составными частями, то с каждым смыслов в составной конструкции связаны смыслы его частей. Т.е. это отображение вниз в категории семантики.

                              Это именно то, что требуется для топологии Гротендика, она примерно так и описывается. Надо только, чтобы при составлении правильной конструкции каждая комбинация смыслов его частей задавала однозначно смысл этой составной конструкции. Но это как раз именно то, что в формальной семантике называют «принципов композиционности», когда семантика конструкции определятся семантикой его частей. В теории категорий в интерпретации синтаксиса, как я его описал, этот принцип связан с понятием пучка.

                              В общем, эти соображения я попытался формализовать и опубликовать. Работа в результате получилась пограничная, на стыке лингвистики и теории категорий. В результате, как это обычно бывает, ее мало кто понял. На самом деле, работа была бы интересной, если бы на основе этого подхода можно было решить какую-то известную лингвистическую задачу. Но я этого не сделал, работа содержала только формулировку методологии интерпретация синтаксиса в теории категорий. Поэтому работа тогда не пошла. Я разделил текст на две части, про синтаграммы и окрестностные грамматики и про топологию Гротендика в категории синтаграмм. Перевел на английский и опубликовал а сайте архива. Но работа не пошла.

                              Мне кажется, какие-то вещи в этом подходе интересны и сами по себе. Даже в вещах, на первый взгляд, далеких от лингвистики. Например, известную задачу о раскраске карты можно интерпретировать как задачу построения соответствующей окрестностной грамматики. Ну и интерпретация лингвистических вещей в теории категорий может дать возможность использовать интересные методы и подходы из этой области математики.

                              Сейчас посмотрел, к сожалению, на моем компьютере тексты статей не сохранились. При желании их можно найти, но для понимания надо освоить какие-то понятия теории категорий. Это конечно трудно.
                              • UFO just landed and posted this here
                                  0
                                  Нашел статьи на русском языке. Статья по синтаксическим топологиям даже перекомпилировал. Правда, не знаю, как ее здесь присоединить. Могу выслать почтой, если необходимо.
                                  Первую статью, в которой задаются сами синтаграммы, я пока не хочу публиковать. За прошедшее время я переосмыслил кое-какие вещи, поэтому хочется заново переформулировать понятия и, заодно, понятия языка и его алфавита. Мне кажется, должно получится что-то интересное.
                                  С работами Прозорова я не знаком. Спасибо за ссылку, почитаю и напишу свое мнение.

                            Only users with full accounts can post comments. Log in, please.