Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
«Среди таких публикаций», «автор склонен считать», «далее в наиболее доступной форме описаны», «согласно Колмогорову» и куча других сухих оборотов, характерных для формальных бумаг вроде научных статей, дипломных работ, справок из ГАИ, отчетов на госпредпиятиях и так далее.
Как-то не вяжется с задумкой о том, что формат поста будет популярным. ;-)
Как-то не вяжется с задумкой о том, что формат поста будет популярным. ;-)
Я надеюсь это только первая часть?
Отлично написано! Спасибо, разжевали то, что не понял в универе. Жду продолжения!
Огромное спасибо за статью!
Очень надеюсь, что в возможных следующих публикациях будут рассмотрены прикладные аспекты теории формальных языков. Кстати говоря, работ в области символической динамики, идейно близкой к формальным языкам, в последнее время все больше и больше.
Очень надеюсь, что в возможных следующих публикациях будут рассмотрены прикладные аспекты теории формальных языков. Кстати говоря, работ в области символической динамики, идейно близкой к формальным языкам, в последнее время все больше и больше.
А продолжение будет? Контекстно-независимые грамматики, LL/LR разбор и т.п.? :)
Спасибо за статью, продолжайте, тема интересная!
Спасибо за статью, все понятно и доступно!
Один вопрос по следующей цитате:
Нет ли здесь опечатки? Мне показалось, что мощность распознающих грамматик должна быть больше мощности порождающих и перечисляющих, потому что, имея распознающую грамматику, можно получить порождающую или перечисляющую, но не наоборот. Возможный алгоритм — перебирать все цепочки символов в алфавитном порядке и выводить те из них, которые проверены распознающей грамматикой на принадлежность языку.
Один вопрос по следующей цитате:
В этом смысле мощность распознающих грамматик меньше мощности порождающих и перечисляющих
Нет ли здесь опечатки? Мне показалось, что мощность распознающих грамматик должна быть больше мощности порождающих и перечисляющих, потому что, имея распознающую грамматику, можно получить порождающую или перечисляющую, но не наоборот. Возможный алгоритм — перебирать все цепочки символов в алфавитном порядке и выводить те из них, которые проверены распознающей грамматикой на принадлежность языку.
Под мощностью класса грамматики здесь подразумевается возможность задавать некоторый класс языков. Некоторые языки, которые могут быть заданы перечисляющей грамматикой, не могут быть заданы распознающей грамматикой, хотя обратное утверждение, как Вы верно заметили, всегда выполняется. Т.е. имеется вложение класса распознаваемых языков в класс перечислимых. В теории алгоритмов используются термины рекурсивное и рекурсивно-перечислимое множество. Там утверждение о неэквивалентности этих классов множеств (языков) — одна из основных теорем.
ЕМНИП, рекурсивные множества отличаются от рекурсивно-перечислимых ровно тем, что для первых существуют распознающие алгоритмы, которые останавливаются на всех возможных входах (т.е., входящих в множество и не входящих), тогда как для вторых — только частичные алгоритмы, т.е. такие, которые заведомо останавливаются на элементах множества, но могут зацикливаться на других входах.
По-моему, все эти основы детально и доступно разбираются в первых главах классической книги А.Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции, т.1.
По-моему, все эти основы детально и доступно разбираются в первых главах классической книги А.Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции, т.1.
Спасибо, понятно, хотя я поначалу запутался.
Спасибо за статью.
Впервые вижу, чтобы автоматы называли грамматикам — зачем путаете добрых людей? :)
ЕМНИП, по Хопкрофту и Ульману, более правильно называть способы задания языков «формализмами», тогда грамматики — порождающие формализмы (можно получить какую-то, не очень заранее известно какую, цепочку последовательным раскрытием правил), а автоматы — распознающие формализмы (можно алгоритмически ответить на вопрос, принадлежит ли данная цепочка в алфавите V языку или нет).
Перечисляющая же «грамматика» — это попросту говоря «список всех цепочек языка», который в случае бесконечного языка попросту не является конечным объектом (как, скажем, и гипотетическая запись числа Пи без ограничения числа значащих цифр).
Впервые вижу, чтобы автоматы называли грамматикам — зачем путаете добрых людей? :)
ЕМНИП, по Хопкрофту и Ульману, более правильно называть способы задания языков «формализмами», тогда грамматики — порождающие формализмы (можно получить какую-то, не очень заранее известно какую, цепочку последовательным раскрытием правил), а автоматы — распознающие формализмы (можно алгоритмически ответить на вопрос, принадлежит ли данная цепочка в алфавите V языку или нет).
Перечисляющая же «грамматика» — это попросту говоря «список всех цепочек языка», который в случае бесконечного языка попросту не является конечным объектом (как, скажем, и гипотетическая запись числа Пи без ограничения числа значащих цифр).
Грамматика — это необязательно автомат. Можно задать грамматику языка, которая не будет алгоритмом, т.е. не предназначена для задания языка. Например, окрестностная грамматика в этом тексте просто описывает синтаксические свойства языка, хотя может быть использована для задания распознающей грамматики очевидным образом. Такой вид грамматик, которые описывают язык, но не определяют алгоритм его задания, я называю описательными грамматиками. Другой вид описательной грамматики — категориальная грамматика Ламбека. Эта грамматика, конечно, превращается в алгоритм распознавания цепочек, т.е. в исчисление, которое применяется к цепочке на основе правил редукции, но важна и сама по себе, как описание синтаксических закономерностей языка.
Грамматики могут быть не только порождающие, как Вы написали выше, но и другого типа (распознающие, перечисляющие). Например, машину Тьюринга можно считать распознающей грамматикой, если использовать первую с вполне определенными довольно узкими целями: для распознавания множества цепочек. В этом смысле, определение грамматики уже определения алгоритма. Интересный вид перечисляющей грамматики — формальные степенные ряды над контекстно-свободными языками. Формализм, на мой взгляд, явно недооцененный.
Резюмируя, грамматика — это не только алгоритм задания языка, но и описание синтаксических закономерностей. В лингвистике, например, принимается во внимание исключительно второй аспект определения, на первый не особо обращают внимание. Конечно, с математической точки зрения важно понимать, как конкретный формализм задает язык, но это не обязательно самое главное в изучении синтаксических свойств языка. Теория алгоритмов изучает закономерности процессов вычислений и, ясно, что любое задание языка протекает во времени и, следовательно, является процессом. Отсюда можно сделать вывод, что любая грамматика, если ее применять как процесс задания языка, неизбежно превращается в один из возможных типов алгоритмов задания множества цепочек. Но грамматика — не алгоритм, но нечто большее. Поэтому я предпочитаю использовать термин «грамматика» вместо термина «автомат».
Грамматики могут быть не только порождающие, как Вы написали выше, но и другого типа (распознающие, перечисляющие). Например, машину Тьюринга можно считать распознающей грамматикой, если использовать первую с вполне определенными довольно узкими целями: для распознавания множества цепочек. В этом смысле, определение грамматики уже определения алгоритма. Интересный вид перечисляющей грамматики — формальные степенные ряды над контекстно-свободными языками. Формализм, на мой взгляд, явно недооцененный.
Резюмируя, грамматика — это не только алгоритм задания языка, но и описание синтаксических закономерностей. В лингвистике, например, принимается во внимание исключительно второй аспект определения, на первый не особо обращают внимание. Конечно, с математической точки зрения важно понимать, как конкретный формализм задает язык, но это не обязательно самое главное в изучении синтаксических свойств языка. Теория алгоритмов изучает закономерности процессов вычислений и, ясно, что любое задание языка протекает во времени и, следовательно, является процессом. Отсюда можно сделать вывод, что любая грамматика, если ее применять как процесс задания языка, неизбежно превращается в один из возможных типов алгоритмов задания множества цепочек. Но грамматика — не алгоритм, но нечто большее. Поэтому я предпочитаю использовать термин «грамматика» вместо термина «автомат».
Спасибо огромное за пост! Буду ждать продолжения. По поводу изложения материала. Я уже немного (скажу сразу достаточно поверхностно) погружался в эту тему. Литература есть, книжки есть, но всё-таки тема в целом непроста для восприятия. В некоторых книгах, методичках авторы сразу предоставляют кучу всяких формул, вводях кучу всяких терминов — многих это отталкивает, запутывает. Дак вот к чему я это. В Вашей статье я увидел как раз всё-таки больше объяснения, появления, разъяснения различных аспектов — считаю что так и надо делать. Чтобы больше людей разобралось в этой теме как раз нужно больше статей, где материал достаточно плавно и равномерно разъясняется, очень аккуратно и аргментированно вводятся формулы и делается так, чтобы читатель понял формулу и она не пугала его. Вот такие мысли и идеи, извиняюсь если немного бредовые :)
Обычно для выделения центра окрестности этот символ в цепочке подчеркивается, здесь этого делать не будем за неимением простой технической возможности.
Подчеркивание — это просто.
Я попытался расширить понятие окрестностной грамматики, надо которым работали Борщев и Хомяков в 70-х годах. Владимир Борисович, кстати, делал доклад по этой работе на Диалоге . Идея та же, что и со шрейдеровскими окрестностными грамматиками. Только они задавали грамматики деревьев вывода контекстно-свободных грамматик. Т.е. они расширили понятие о языке. Язык — это не множество цепочек, но множество синтаксических структур, для КС-грамматик это деревья вывода. Для каждого символа можно задать множество его окрестностей, которые будут уже не цепочки, но «кусты» в дереве. Тогда дерево принадлежит языку в том и только в том случае, если каждая его вершина входит в это дерево вместе с некоторой своей окрестностью (кустом).
Идея здесь на самом деле топологическая. Окрестность — это аналог окрестности точки в топологии, т.е. открытого множества, содержащегося в топологии. Топология и есть ведь набор открытых множеств, заданных для каждой точки пространства. Множество в топологии считается открытым, если каждая точка входит в него вместе с какой-то своей окрестностью. Все это очень похоже на то, что имеется в грамматике. Я понял, что на самом деле в деревьях вывода визуализируется отношение иерархии («быть частью»), которое является основным в КС-грамматике. В цепочках языка имеется отношение непосредственного следования, т.е. «быть рядом». Такие отношения можно рисовать в виде графов, для них я даже придумал специальный термин — синтаграмма. Граф синтаксических отношений цепочки правильный (а значит и сама цепочка принадлежит языку), если каждая вершина этого графа входит в него вместе с некоторой своей окрестностью. Т.е. здесь полный аналог топологии и открытых множеств.
Понятие синтаграммы позволяет абстрагироваться от природы синтаксических отношений. Синтаграммы — это и деревья КС-грамматик, а также и обычные цепочки традиционного формального языка. Но графы — это не множества, поэтому понятия вложения в них другое. Два графа могут вкладываться друг в друга несколькими способами, тогда как для множеств вложение только одно. Значит, математический аппарат топологии сюда
непосредственно применить не получается. Но можно попытаться применить методы теории категорий, т.е. образовать категорию синтаграмм. В этой категории топологией будет как раз окрестностная грамматика. В теории категорий есть аналог понятия топологического пространства — это т.н. топология Гротендика. Но эта топология сама по себе только на основе категории не строится. Для нее необходимо еще одна категория, куда объекты исходной категории будут отображаться. Я понял, что для синтаксиса такая категория естественным образом появляется.
Если для каждой окрестностной синтаграммы задать множество ее смыслов, то получим функтор (отображение) из категории синтаксиса в категорию семантики этого языка. От природы смыслов мы абстрагируемся, просто считаем, что это элементы какого-то множества. С каждой базовой синтаксической конструкцией связано конечно множество смыслов. Причем наблюдается интересная закономерность. Если мы имеем какую-то синтаграмму, например, дерево вывода какого-то предложения в КС-грамматике Хомского, то она имеет покрытие окрестностными синтаграммами для каждой своей вершины. Т.е. имеется такой подъем, когда любая синтаграмма составляется из окрестностей — отображение наверх, к более сложным частям. С другой стороны, в семантике имеется спуск вниз. Если есть какой-то смысл, связанный с составной конструкцией и есть смыслы связанные с его составными частями, то с каждым смыслов в составной конструкции связаны смыслы его частей. Т.е. это отображение вниз в категории семантики.
Это именно то, что требуется для топологии Гротендика, она примерно так и описывается. Надо только, чтобы при составлении правильной конструкции каждая комбинация смыслов его частей задавала однозначно смысл этой составной конструкции. Но это как раз именно то, что в формальной семантике называют «принципов композиционности», когда семантика конструкции определятся семантикой его частей. В теории категорий в интерпретации синтаксиса, как я его описал, этот принцип связан с понятием пучка.
В общем, эти соображения я попытался формализовать и опубликовать. Работа в результате получилась пограничная, на стыке лингвистики и теории категорий. В результате, как это обычно бывает, ее мало кто понял. На самом деле, работа была бы интересной, если бы на основе этого подхода можно было решить какую-то известную лингвистическую задачу. Но я этого не сделал, работа содержала только формулировку методологии интерпретация синтаксиса в теории категорий. Поэтому работа тогда не пошла. Я разделил текст на две части, про синтаграммы и окрестностные грамматики и про топологию Гротендика в категории синтаграмм. Перевел на английский и опубликовал а сайте архива. Но работа не пошла.
Мне кажется, какие-то вещи в этом подходе интересны и сами по себе. Даже в вещах, на первый взгляд, далеких от лингвистики. Например, известную задачу о раскраске карты можно интерпретировать как задачу построения соответствующей окрестностной грамматики. Ну и интерпретация лингвистических вещей в теории категорий может дать возможность использовать интересные методы и подходы из этой области математики.
Сейчас посмотрел, к сожалению, на моем компьютере тексты статей не сохранились. При желании их можно найти, но для понимания надо освоить какие-то понятия теории категорий. Это конечно трудно.
Идея здесь на самом деле топологическая. Окрестность — это аналог окрестности точки в топологии, т.е. открытого множества, содержащегося в топологии. Топология и есть ведь набор открытых множеств, заданных для каждой точки пространства. Множество в топологии считается открытым, если каждая точка входит в него вместе с какой-то своей окрестностью. Все это очень похоже на то, что имеется в грамматике. Я понял, что на самом деле в деревьях вывода визуализируется отношение иерархии («быть частью»), которое является основным в КС-грамматике. В цепочках языка имеется отношение непосредственного следования, т.е. «быть рядом». Такие отношения можно рисовать в виде графов, для них я даже придумал специальный термин — синтаграмма. Граф синтаксических отношений цепочки правильный (а значит и сама цепочка принадлежит языку), если каждая вершина этого графа входит в него вместе с некоторой своей окрестностью. Т.е. здесь полный аналог топологии и открытых множеств.
Понятие синтаграммы позволяет абстрагироваться от природы синтаксических отношений. Синтаграммы — это и деревья КС-грамматик, а также и обычные цепочки традиционного формального языка. Но графы — это не множества, поэтому понятия вложения в них другое. Два графа могут вкладываться друг в друга несколькими способами, тогда как для множеств вложение только одно. Значит, математический аппарат топологии сюда
непосредственно применить не получается. Но можно попытаться применить методы теории категорий, т.е. образовать категорию синтаграмм. В этой категории топологией будет как раз окрестностная грамматика. В теории категорий есть аналог понятия топологического пространства — это т.н. топология Гротендика. Но эта топология сама по себе только на основе категории не строится. Для нее необходимо еще одна категория, куда объекты исходной категории будут отображаться. Я понял, что для синтаксиса такая категория естественным образом появляется.
Если для каждой окрестностной синтаграммы задать множество ее смыслов, то получим функтор (отображение) из категории синтаксиса в категорию семантики этого языка. От природы смыслов мы абстрагируемся, просто считаем, что это элементы какого-то множества. С каждой базовой синтаксической конструкцией связано конечно множество смыслов. Причем наблюдается интересная закономерность. Если мы имеем какую-то синтаграмму, например, дерево вывода какого-то предложения в КС-грамматике Хомского, то она имеет покрытие окрестностными синтаграммами для каждой своей вершины. Т.е. имеется такой подъем, когда любая синтаграмма составляется из окрестностей — отображение наверх, к более сложным частям. С другой стороны, в семантике имеется спуск вниз. Если есть какой-то смысл, связанный с составной конструкцией и есть смыслы связанные с его составными частями, то с каждым смыслов в составной конструкции связаны смыслы его частей. Т.е. это отображение вниз в категории семантики.
Это именно то, что требуется для топологии Гротендика, она примерно так и описывается. Надо только, чтобы при составлении правильной конструкции каждая комбинация смыслов его частей задавала однозначно смысл этой составной конструкции. Но это как раз именно то, что в формальной семантике называют «принципов композиционности», когда семантика конструкции определятся семантикой его частей. В теории категорий в интерпретации синтаксиса, как я его описал, этот принцип связан с понятием пучка.
В общем, эти соображения я попытался формализовать и опубликовать. Работа в результате получилась пограничная, на стыке лингвистики и теории категорий. В результате, как это обычно бывает, ее мало кто понял. На самом деле, работа была бы интересной, если бы на основе этого подхода можно было решить какую-то известную лингвистическую задачу. Но я этого не сделал, работа содержала только формулировку методологии интерпретация синтаксиса в теории категорий. Поэтому работа тогда не пошла. Я разделил текст на две части, про синтаграммы и окрестностные грамматики и про топологию Гротендика в категории синтаграмм. Перевел на английский и опубликовал а сайте архива. Но работа не пошла.
Мне кажется, какие-то вещи в этом подходе интересны и сами по себе. Даже в вещах, на первый взгляд, далеких от лингвистики. Например, известную задачу о раскраске карты можно интерпретировать как задачу построения соответствующей окрестностной грамматики. Ну и интерпретация лингвистических вещей в теории категорий может дать возможность использовать интересные методы и подходы из этой области математики.
Сейчас посмотрел, к сожалению, на моем компьютере тексты статей не сохранились. При желании их можно найти, но для понимания надо освоить какие-то понятия теории категорий. Это конечно трудно.
Нашел статьи на русском языке. Статья по синтаксическим топологиям даже перекомпилировал. Правда, не знаю, как ее здесь присоединить. Могу выслать почтой, если необходимо.
Первую статью, в которой задаются сами синтаграммы, я пока не хочу публиковать. За прошедшее время я переосмыслил кое-какие вещи, поэтому хочется заново переформулировать понятия и, заодно, понятия языка и его алфавита. Мне кажется, должно получится что-то интересное.
С работами Прозорова я не знаком. Спасибо за ссылку, почитаю и напишу свое мнение.
Первую статью, в которой задаются сами синтаграммы, я пока не хочу публиковать. За прошедшее время я переосмыслил кое-какие вещи, поэтому хочется заново переформулировать понятия и, заодно, понятия языка и его алфавита. Мне кажется, должно получится что-то интересное.
С работами Прозорова я не знаком. Спасибо за ссылку, почитаю и напишу свое мнение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Формальные языки и грамматики