Обычный язык - Regular language

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

В качестве альтернативы, обычный язык можно определить как язык, распознаваемый конечным автоматом . Эквивалентность регулярных выражений и конечных автоматов известна как теорема Клини (в честь американского математика Стивена Коула Клини ). В иерархии Хомского регулярные языки - это языки, генерируемые грамматиками типа 3 .

Формальное определение

Набор регулярных языков над алфавитом Σ определяется рекурсивно следующим образом:

  • Пустой язык Ø - это обычный язык.
  • Для каждого a ∈ Σ ( a принадлежит Σ) одноэлементный язык { a } является регулярным языком.
  • Если A - регулярный язык, A * ( звезда Клини ) - регулярный язык. Благодаря этому язык пустых строк {ε} также является регулярным.
  • Если A и B - регулярные языки, то AB (объединение) и AB (конкатенация) - регулярные языки.
  • Никакие другие языки над Σ не являются регулярными.

См. В разделе регулярное выражение синтаксис и семантику регулярных выражений.

Примеры

Все конечные языки регулярны; в частности, язык пустых строк {ε} = Ø * является регулярным. Другие типичные примеры включают язык, состоящий из всех строк в алфавите { a , b }, которые содержат четное число a s, или язык, состоящий из всех строк формы: несколько a s, за которыми следуют несколько b s.

Простым примером языка, который не является регулярным, является набор строк { a n b n | n ≥ 0}. Интуитивно это невозможно распознать с помощью конечного автомата, поскольку конечный автомат имеет конечную память и не может запомнить точное количество а. Методы строгого доказательства этого факта приведены ниже .

Эквивалентные формализмы

Регулярный язык удовлетворяет следующим эквивалентным свойствам:

  1. это язык регулярного выражения (согласно приведенному выше определению)
  2. это язык, принятый недетерминированным конечным автоматом (NFA)
  3. это язык, принятый детерминированным конечным автоматом (DFA)
  4. его можно сгенерировать с помощью обычной грамматики
  5. это язык, принятый переменным конечным автоматом
  6. это язык, принятый двусторонним конечным автоматом
  7. он может быть сгенерирован префиксной грамматикой
  8. он может быть принят машиной Тьюринга, доступной только для чтения
  9. его можно определить в монадической логике второго порядка ( теорема Бюхи – Элгот – Трахтенброта )
  10. он распознается некоторым конечным синтаксическим моноидом M , т. е. является прообразом { w ∈ Σ * | f ( w ) ∈ S } подмножества S конечного моноида M при гомоморфизме моноида f : Σ *M из свободного моноида на его алфавите
  11. число классов эквивалентности его синтаксической конгруэнтности конечно. (Это число равно количеству состояний минимального детерминированного конечного автомата, принимающего L. )

Свойства 10. и 11. представляют собой чисто алгебраические подходы к определению регулярных языков; аналогичный набор утверждений можно сформулировать для моноида M ⊆ Σ * . В этом случае эквивалентность над M приводит к понятию узнаваемого языка.

Некоторые авторы используют одно из вышеперечисленных свойств, отличное от «1». как альтернативное определение обычных языков.

Некоторые из приведенных выше эквивалентностей, особенно те, что относятся к первым четырем формализмам, в учебниках называют теоремой Клини . Какой именно из них (или какое подмножество) называть таковыми, зависит от авторов. Один учебник называет эквивалентность регулярных выражений и NFA («1» и «2» выше) «теоремой Клини». Другой учебник называет эквивалентность регулярных выражений и DFA («1» и «3» выше) «теоремой Клини». Два других учебника сначала доказывают выразительную эквивалентность NFA и DFA («2» и «3»), а затем заявляют «теорему Клини» как эквивалентность между регулярными выражениями и конечными автоматами (последний, как говорят, описывает «узнаваемые языки») . Лингвистически ориентированный текст сначала приравнивает обычные грамматики («4.» выше) к DFA и NFA, называет языки, созданные (любым из) этими «регулярными», после чего вводит регулярные выражения, которые он называет «рациональными языками», и, наконец, утверждает «теорему Клини» как совпадение регулярных и рациональных языков. Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками».

Очевидно, термин «регулярный» происходит из технического отчета 1951 года, в котором Клини ввел «регулярные мероприятия» и явно приветствовал «любые предложения относительно более описательного термина» . Ноам Хомский в своей основополагающей статье 1959 года сначала использовал термин «регулярный» в другом значении (имея в виду то, что сегодня называется « нормальной формой Хомского » ), но заметил, что его «языки с конечным числом состояний» эквивалентны «регулярным языкам» Клини. события » .

Свойства закрытия

Регулярные языки закрыты относительно различных операций, то есть, если языки K и L регулярны, то это является результатом следующих операций:

Свойства разрешимости

Для двух детерминированных конечных автоматов A и B разрешимо, принимают ли они один и тот же язык. Как следствие, используя указанные выше свойства замыкания, следующие проблемы также разрешимы для произвольно заданных детерминированных конечных автоматов A и B с принятыми языками L A и L B соответственно:

  • Сдерживание: L AL B  ?
  • Дизъюнктность: является ли L AL B = {}?
  • Пустота: L A = {}?
  • Универсальность: является ли L A = Σ *  ?
  • Принадлежность: для данного a ∈ Σ * является ли aL B  ?

Для регулярных выражений проблема универсальности NP-полная уже для одноэлементного алфавита. Для больших алфавитов эта проблема решена для PSPACE . Если регулярные выражения расширены, чтобы разрешить также оператор возведения в квадрат , где « A 2 » обозначает то же самое, что и « AA », все еще могут быть описаны только регулярные языки, но проблема универсальности имеет экспоненциальную нижнюю границу пространства и фактически является полной для экспоненциальное пространство относительно редукции за полиномиальное время.

Результаты сложности

В теории сложности вычислений , то класс сложности всех регулярных языков иногда называют REGULAR или REG и равна DSPACE (O (1)), то проблемы решения , которые могут быть решены в постоянном пространстве (пространство используется не зависит от размера входного ). ОБЫЧНЫЙAC 0 , поскольку он (тривиально) содержит проблему четности для определения того, является ли количество 1 битов на входе четным или нечетным, и эта проблема не в AC 0 . С другой стороны, REGULAR не содержит AC 0 , потому что нерегулярный язык палиндромов или нерегулярный язык могут быть распознаны в AC 0 .

Если язык не является регулярным, для его распознавания требуется машина с пространством не менее Ω (log log n ) (где n - размер ввода). Другими словами, DSPACE ( o (log log n )) соответствует классу обычных языков. На практике большинство нерегулярных задач решаются машинами, занимающими хотя бы логарифмическое пространство .

Расположение в иерархии Хомского

Регулярный язык в классах иерархии Хомского.

Чтобы найти обычные языки в иерархии Хомского , нужно заметить, что каждый регулярный язык контекстно-независим . Обратное неверно: например, язык, состоящий из всех строк, имеющих такое же количество букв a , что и b , является контекстно-независимым, но не регулярным. Чтобы доказать, что язык не является регулярным, часто используют теорему Майхилла – Нероде и лемму о накачке . Другие подходы включают использование закрывающих свойств обычных языков или количественное определение колмогоровской сложности .

Важные подклассы обычных языков включают

Количество слов в обычном языке

Пусть обозначим число слов длины в . Обыкновенная производящая функция для L представляет собой формальный степенной ряд

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

Таким образом, нерегулярность некоторых языков может быть доказана путем подсчета слов заданной длины в . Рассмотрим, например, язык Дейка строк сбалансированных круглых скобок. Количество слов длины в языке Дейка равно каталонскому числу , которое не имеет формы , что свидетельствует о нерегулярности языка Дейка. Следует проявлять осторожность, поскольку некоторые собственные значения могут иметь одинаковую величину. Например, количество слов длины в языке всех четных двоичных слов не имеет формы , а количество слов четной или нечетной длины имеет эту форму; соответствующие собственные значения равны . В общем, для каждого регулярного языка существует такая константа , что для всех количество слов длины асимптотически .

Дзета - функция языкового L является

Дзета-функция регулярного языка в общем случае не рациональна, в отличие от произвольного циклического языка .

Обобщения

Понятие регулярного языка было обобщено на бесконечные слова (см. Ω-автоматы ) и деревья (см. Древовидный автомат ).

Рациональный набор обобщает понятие (регулярного / рационального языка) на моноиды, которые не обязательно свободны . Точно так же понятие распознаваемого языка (с помощью конечного автомата) имеет тезку как узнаваемое множество над моноидом, который не обязательно является свободным. Говард Штраубинг отмечает в связи с этими фактами: «Термин« обычный язык »несколько неудачен. В статьях, на которые повлияла монография Эйленберга , часто используется термин «узнаваемый язык», который относится к поведению автоматов, или «рациональный язык», который относится к важным аналогиям между регулярными выражениями и рациональными степенными рядами. (Фактически, Эйленберг определяет рациональные и узнаваемые подмножества произвольных моноидов; эти два понятия, в общем, не совпадают.) Эта терминология, хотя и лучше мотивированная, никогда не прижилась, а «регулярный язык» используется почти повсеместно ».

Рациональный ряд - еще одно обобщение, на этот раз в контексте формального степенного ряда над полукольцом . Этот подход порождает взвешенные рациональные выражения и взвешенные автоматы . В этом алгебраическом контексте регулярные языки (соответствующие логическим взвешенным рациональным выражениям) обычно называются рациональными языками . Также в этом контексте теорема Клини находит обобщение, называемое теоремой Клини-Шютценбергера .

Учимся на примерах

Примечания

использованная литература

дальнейшее чтение

  • Клини, SC : Представление событий в нервных сетях и конечных автоматах. В: Shannon, CE, McCarthy, J. (eds.) Automata Studies, стр. 3–41. Издательство Принстонского университета, Принстон (1956); это слегка измененная версия его одноименного отчета корпорации RAND за 1951 год , RM704 .
  • Сакарович, J (1987). "Повторный визит к теореме Клини". Тенденции, методы и проблемы теоретической информатики . Конспект лекций по информатике. 1987 . С. 39–50. DOI : 10.1007 / 3540185356_29 . ISBN 978-3-540-18535-2.

внешние ссылки