Обычный язык - Regular language
В теоретическом информатики и теории формальных языков , регулярный язык (также называется рациональным языком ) является формальным языком , который может быть определен с помощью регулярного выражения , в строгом смысле , в теоретической информатике (в отличии от многих современных регулярных выражений двигателей, которые дополнены функциями , позволяющими распознавать нерегулярные языки).
В качестве альтернативы, обычный язык можно определить как язык, распознаваемый конечным автоматом . Эквивалентность регулярных выражений и конечных автоматов известна как теорема Клини (в честь американского математика Стивена Коула Клини ). В иерархии Хомского регулярные языки - это языки, генерируемые грамматиками типа 3 .
Формальное определение
Набор регулярных языков над алфавитом Σ определяется рекурсивно следующим образом:
- Пустой язык Ø - это обычный язык.
- Для каждого a ∈ Σ ( a принадлежит Σ) одноэлементный язык { a } является регулярным языком.
- Если A - регулярный язык, A * ( звезда Клини ) - регулярный язык. Благодаря этому язык пустых строк {ε} также является регулярным.
- Если A и B - регулярные языки, то A ∪ B (объединение) и A • B (конкатенация) - регулярные языки.
- Никакие другие языки над Σ не являются регулярными.
См. В разделе регулярное выражение синтаксис и семантику регулярных выражений.
Примеры
Все конечные языки регулярны; в частности, язык пустых строк {ε} = Ø * является регулярным. Другие типичные примеры включают язык, состоящий из всех строк в алфавите { a , b }, которые содержат четное число a s, или язык, состоящий из всех строк формы: несколько a s, за которыми следуют несколько b s.
Простым примером языка, который не является регулярным, является набор строк { a n b n | n ≥ 0}. Интуитивно это невозможно распознать с помощью конечного автомата, поскольку конечный автомат имеет конечную память и не может запомнить точное количество а. Методы строгого доказательства этого факта приведены ниже .
Эквивалентные формализмы
Регулярный язык удовлетворяет следующим эквивалентным свойствам:
- это язык регулярного выражения (согласно приведенному выше определению)
- это язык, принятый недетерминированным конечным автоматом (NFA)
- это язык, принятый детерминированным конечным автоматом (DFA)
- его можно сгенерировать с помощью обычной грамматики
- это язык, принятый переменным конечным автоматом
- это язык, принятый двусторонним конечным автоматом
- он может быть сгенерирован префиксной грамматикой
- он может быть принят машиной Тьюринга, доступной только для чтения
- его можно определить в монадической логике второго порядка ( теорема Бюхи – Элгот – Трахтенброта )
- он распознается некоторым конечным синтаксическим моноидом M , т. е. является прообразом { w ∈ Σ * | f ( w ) ∈ S } подмножества S конечного моноида M при гомоморфизме моноида f : Σ * → M из свободного моноида на его алфавите
- число классов эквивалентности его синтаксической конгруэнтности конечно. (Это число равно количеству состояний минимального детерминированного конечного автомата, принимающего L. )
Свойства 10. и 11. представляют собой чисто алгебраические подходы к определению регулярных языков; аналогичный набор утверждений можно сформулировать для моноида M ⊆ Σ * . В этом случае эквивалентность над M приводит к понятию узнаваемого языка.
Некоторые авторы используют одно из вышеперечисленных свойств, отличное от «1». как альтернативное определение обычных языков.
Некоторые из приведенных выше эквивалентностей, особенно те, что относятся к первым четырем формализмам, в учебниках называют теоремой Клини . Какой именно из них (или какое подмножество) называть таковыми, зависит от авторов. Один учебник называет эквивалентность регулярных выражений и NFA («1» и «2» выше) «теоремой Клини». Другой учебник называет эквивалентность регулярных выражений и DFA («1» и «3» выше) «теоремой Клини». Два других учебника сначала доказывают выразительную эквивалентность NFA и DFA («2» и «3»), а затем заявляют «теорему Клини» как эквивалентность между регулярными выражениями и конечными автоматами (последний, как говорят, описывает «узнаваемые языки») . Лингвистически ориентированный текст сначала приравнивает обычные грамматики («4.» выше) к DFA и NFA, называет языки, созданные (любым из) этими «регулярными», после чего вводит регулярные выражения, которые он называет «рациональными языками», и, наконец, утверждает «теорему Клини» как совпадение регулярных и рациональных языков. Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками».
Очевидно, термин «регулярный» происходит из технического отчета 1951 года, в котором Клини ввел «регулярные мероприятия» и явно приветствовал «любые предложения относительно более описательного термина» . Ноам Хомский в своей основополагающей статье 1959 года сначала использовал термин «регулярный» в другом значении (имея в виду то, что сегодня называется « нормальной формой Хомского » ), но заметил, что его «языки с конечным числом состояний» эквивалентны «регулярным языкам» Клини. события » .
Свойства закрытия
Регулярные языки закрыты относительно различных операций, то есть, если языки K и L регулярны, то это является результатом следующих операций:
- в теоретико-множественные булевы операции : объединение K ∪ L , пересечение K ∩ L , и дополнение L , а значит , и относительное дополнение К - л .
- регулярные операции: K ∪ L , конкатенация и звезда Клини L * .
- в трио операции: строка гомоморфизм , обратная струна гомоморфизм, и пересечения с регулярными языками. Как следствие, они замкнуты относительно произвольных преобразований с конечным числом состояний , как фактор K / L с регулярным языком. Более того , регулярные языки замкнуты относительно дробей с произвольными языками: Если L является регулярным , то L / K является регулярным для любого K .
- обратная (или зеркальное изображение) L R . Если задан недетерминированный конечный автомат для распознавания L , автомат для L R может быть получен путем обращения всех переходов и смены начального и конечного состояний. Это может привести к нескольким стартовым состояниям; Для их соединения можно использовать ε-переходы.
Свойства разрешимости
Для двух детерминированных конечных автоматов A и B разрешимо, принимают ли они один и тот же язык. Как следствие, используя указанные выше свойства замыкания, следующие проблемы также разрешимы для произвольно заданных детерминированных конечных автоматов A и B с принятыми языками L A и L B соответственно:
- Сдерживание: L A ⊆ L B ?
- Дизъюнктность: является ли L A ∩ L B = {}?
- Пустота: L A = {}?
- Универсальность: является ли L A = Σ * ?
- Принадлежность: для данного a ∈ Σ * является ли a ∈ L 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 является
Дзета-функция регулярного языка в общем случае не рациональна, в отличие от произвольного циклического языка .
Обобщения
Понятие регулярного языка было обобщено на бесконечные слова (см. Ω-автоматы ) и деревья (см. Древовидный автомат ).
Рациональный набор обобщает понятие (регулярного / рационального языка) на моноиды, которые не обязательно свободны . Точно так же понятие распознаваемого языка (с помощью конечного автомата) имеет тезку как узнаваемое множество над моноидом, который не обязательно является свободным. Говард Штраубинг отмечает в связи с этими фактами: «Термин« обычный язык »несколько неудачен. В статьях, на которые повлияла монография Эйленберга , часто используется термин «узнаваемый язык», который относится к поведению автоматов, или «рациональный язык», который относится к важным аналогиям между регулярными выражениями и рациональными степенными рядами. (Фактически, Эйленберг определяет рациональные и узнаваемые подмножества произвольных моноидов; эти два понятия, в общем, не совпадают.) Эта терминология, хотя и лучше мотивированная, никогда не прижилась, а «регулярный язык» используется почти повсеместно ».
Рациональный ряд - еще одно обобщение, на этот раз в контексте формального степенного ряда над полукольцом . Этот подход порождает взвешенные рациональные выражения и взвешенные автоматы . В этом алгебраическом контексте регулярные языки (соответствующие логическим взвешенным рациональным выражениям) обычно называются рациональными языками . Также в этом контексте теорема Клини находит обобщение, называемое теоремой Клини-Шютценбергера .
Учимся на примерах
Примечания
использованная литература
- Берстель, Жан ; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. 137 . Кембридж: Издательство Кембриджского университета . ISBN 978-0-521-19022-0. Zbl 1250,68007 .
- Эйленберг, Самуэль (1974). Автоматы, языки и машины. Том A . Чистая и прикладная математика. 58 . Нью-Йорк: Academic Press. Zbl 0317.94045 .
- Саломаа, Арто (1981). Драгоценности теории формального языка . Pitman Publishing. ISBN 0-273-08522-0. Zbl 0487.68064 .
- Сипсер, Майкл (1997). Введение в теорию вычислений . PWS Publishing. ISBN 0-534-94728-X. Zbl 1169.68300 .Глава 1: Обычные языки, стр. 31–90. Подраздел «Разрешаемые проблемы, касающиеся регулярных языков» раздела 4.1: Разрешаемые языки, стр. 152–155.
- Филипп Флажоле и Роберт Седжвик, Аналитическая комбинаторика : символическая комбинаторика. Электронная книга, 2002.
- Джон Э. Хопкрофт; Джеффри Д. Ульман (1979). Введение в теорию автоматов, языки и вычисления . Эддисон-Уэсли. ISBN 0-201-02988-X.
- Альфред В. Ахо, Джон Э. Хопкрофт и Джеффри Д. Уллман (1974). Дизайн и анализ компьютерных алгоритмов . Эддисон-Уэсли.
дальнейшее чтение
- Клини, 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.
внешние ссылки
- СМИ, связанные с обычным языком на Викискладе?
- Зоопарк сложности : Класс REG