Обычный язык

Информацию о регулируемом естественном языке см. в разделе «Список регуляторов языка» .

«Теорема Клини» перенаправляется сюда. Для его теорем для рекурсивных функций см. теорему Клини о рекурсии .

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

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

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

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

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

См. «Регулярное выражение», чтобы узнать о синтаксисе и семантике регулярных выражений.

Примеры

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

Простым примером нерегулярного языка является набор строк { a ^н б ^н | п ≥ 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» выше) названа «теоремой Клини». Другой учебник называет эквивалентность регулярных выражений и ДКА («1» и «3» выше) «теоремой Клини». Два других учебника сначала доказывают выразительную эквивалентность NFA и DFA («2» и «3»), а затем утверждают «теорему Клини» как эквивалентность между регулярными выражениями и конечными автоматами (последние, как говорят, описывают «узнаваемые языки»). . Лингвистически ориентированный текст сначала приравнивает регулярные грамматики («4.» выше) к DFA и NFA, называет языки, порожденные (любым из) этих языков, «регулярными», после чего вводит регулярные выражения, которые он называет терминами для описания «рациональных языков». и, наконец, утверждает «теорему Клини» как совпадение регулярных и рациональных языков. Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками».

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

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

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

• теоретико -множественные булевы операции : объединение K ∪ L , пересечение K ∩ L и дополнение L , а следовательно, и относительное дополнение K − L .
• регулярные операции: K ∪ L , конкатенация $K\circ L$и звезда Клини L ^* .
• трио гомоморфизм операций: строк , обратный гомоморфизм строк и пересечение с регулярными языками. Как следствие, они замкнуты относительно произвольных преобразований с конечным состоянием , как фактор K / L с регулярным языком. Более того, регулярные языки замкнуты относительно факторов с произвольными языками: если L регулярен, то / K регулярен для любого K. L
• реверс (или зеркальное отображение) L ^Р . Учитывая недетерминированный конечный автомат для распознавания L , автомат для L ^Р можно получить, обратив все переходы и поменяв местами начальное и конечное состояния. Это может привести к появлению нескольких начальных состояний; Для их соединения можно использовать ε-переходы.

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

Учитывая два детерминированных конечных автомата 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 ² " обозначает то же самое, что и " АА ", но можно описать только обычные языки, но проблема универсальности имеет нижнюю границу экспоненциального пространства, и фактически является полным для экспоненциального пространства относительно полиномиальной редукции по времени.

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

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

В теории сложности вычислений всех класс сложности регулярных языков иногда называют REGULAR или REG и равен DSPACE (O(1)), проблемам решения , которые могут быть решены в постоянном пространстве (используемое пространство не зависит от размера входных данных). ). ОБЫЧНЫЙ ≠ переменный ток ⁰ , поскольку он (тривиально) содержит проблему четности определения того, является ли число 1 бит во входных данных четным или нечетным, и этой проблемы нет в AC ⁰ . С другой стороны, REGULAR не содержит переменного тока. ⁰ , потому что неправильный язык палиндромов или неправильный язык $\{0^{n}1^{n}:n\in \mathbb {N} \}$ оба могут быть распознаны в AC ⁰ .

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

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

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

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

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

• Конечные языки, содержащие только конечное число слов. Это регулярные языки, поскольку можно создать регулярное выражение , представляющее собой объединение каждого слова языка.
• Языки без звезд , те, которые могут быть описаны регулярным выражением, составленным из пустого символа, букв, конкатенации и всех логических операторов (см. Алгебру множеств ), включая дополнение , но не звезду Клини : этот класс включает все конечные языки.

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

Позволять $s_{L}(n)$ обозначают количество слов длины $n$ в $L$. Обычная производящая функция для L представляет собой формальный степенной ряд

$S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .$

Производящая функция языка L является рациональной функцией, если L регулярен. Следовательно, для каждого регулярного языка $L$ последовательность $s_{L}(n)_{n\geq 0}$ является постоянно-рекурсивным ; то есть существует целая константа $n_{0}$, комплексные константы $\lambda _{1},\,\ldots ,\,\lambda _{k}$ и комплексные полиномы $p_{1}(x),\,\ldots ,\,p_{k}(x)$такой, что для каждого $n\geq n_{0}$ число $s_{L}(n)$ слов длиной $n$ в $L$ является $s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}$.

Таким образом, нерегулярность некоторых языков $L'$ можно доказать, посчитав слова заданной длины в $L'$. Рассмотрим, например, язык Дика строк со сбалансированными круглыми скобками. Количество слов длиной $2n$на языке Дейка равно каталонскому числу $C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}$, который не имеет вида $p(n)\lambda ^{n}$,свидетельствуя о нерегулярности языка Дейка. Необходимо соблюдать осторожность, поскольку некоторые собственные значения $\lambda _{i}$ может иметь такую ​​же величину. Например, количество слов длиной $n$ в языке все даже двоичные слова не имеют вида $p(n)\lambda ^{n}$, но количество слов четной или нечетной длины имеет такой вид; соответствующие собственные значения равны $2,-2$. Вообще говоря, для каждого регулярного языка существует константа $d$ такой, что для всех $a$, количество слов длиной $dm+a$ асимптотически $C_{a}m^{p_{a}}\lambda _{a}^{m}$.

Дзета -функция языка L равна

$\zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).$

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

Обобщения

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

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

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

Обучение на примерах

Основная статья: Индукция регулярных языков

Ссылки

• Берстель, Жан ; Ройтенауэр, Кристоф (2011). Некоммутативные рациональные ряды с приложениями . Энциклопедия математики и ее приложений. Том. 137. Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-19022-0 . Збл   1250.68007 .
• Эйленберг, Сэмюэл (1974). Автоматы, языки и машины. Том А. Чистая и прикладная математика. Том. 58. Нью-Йорк: Академик Пресс. Збл   0317.94045 .
• Саломаа, Арто (1981). Жемчужины теории формального языка . Издательство Питман. ISBN  0-273-08522-0 . Збл   0487.68064 .
• Сипсер, Майкл (1997). Введение в теорию вычислений . Издательство ПВС. ISBN  0-534-94728-Х . Збл   1169,68300 . Глава 1: Обычные языки, стр. 31–90. Подраздел «Разрешимые проблемы, касающиеся регулярных языков» раздела 4.1: Разрешимые языки, стр. 152–155.
• Филипп Флажоле и Роберт Седжвик, Аналитическая комбинаторика : символическая комбинаторика. Интернет-книга, 2002.
• Джон Э. Хопкрофт; Джеффри Д. Уллман (1979). Введение в теорию автоматов, языки и вычисления . Аддисон-Уэсли. ISBN  0-201-02988-Х .
• Альфред В. Ахо, Джон Э. Хопкрофт и Джеффри Д. Ульман (1974). Проектирование и анализ компьютерных алгоритмов . Аддисон-Уэсли. ISBN  9780201000290 .

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

• Клини, С.К .: Представление событий в нервных сетях и конечных автоматах. В: Шеннон, К.Э., Маккарти, Дж. (ред.) Исследования автоматов, стр. 3–41. Издательство Принстонского университета, Принстон (1956); это слегка измененная версия его RAND Corporation одноименного отчета 1951 года, RM704 .
• Сакарович, Дж (1987). «Возвращение к теореме Клини». Тенденции, методы и проблемы теоретической информатики . Конспекты лекций по информатике. Том. 1987. стр. 39–50. дои : 10.1007/3540185356_29 . ISBN  978-3-540-18535-2 .

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

• Зоопарк сложности : класс REG