Обычный язык

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

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

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

Альтернативно, регулярный язык можно определить как язык, распознаваемый конечным автоматом . Эквивалентность регулярных выражений и конечных автоматов известна как теорема Клини. (в честь американского математика Стивена Коула Клини ). В иерархии Хомского регулярные языки — это языки, порожденные грамматиками типа 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 года сначала в другом значении (имея в виду то, что сегодня называется « нормальной формой Хомского » ), но заметил, что его «конечные государственные языки» были эквивалентны «регулярным мероприятиям» Клини .

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

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

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

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

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

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

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