Обычный язык

Формальный язык, который можно выразить с помощью регулярного выражения.

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Некоторые из приведенных выше эквивалентностей, особенно среди первых четырех формализмов, в учебниках называются теоремой Клини . Какой именно из них (или какое подмножество) называется таковым, варьируется у разных авторов. В одном учебнике эквивалентность регулярных выражений и NFA («1» и «2» выше) названа «теоремой Клини». ^[6] Другой учебник называет эквивалентность регулярных выражений и ДКА («1.» и «3.» выше) «теоремой Клини». ^[7] Два других учебника сначала доказывают выразительную эквивалентность NFA и DFA («2.» и «3.»), а затем формулируют «теорему Клини» как эквивалентность между регулярными выражениями и конечными автоматами (последние, как говорят, описывают «узнаваемые языки»). ^{[2] [8]} Лингвистически ориентированный текст сначала приравнивает регулярные грамматики («4.» выше) к DFA и NFA, называет языки, порожденные (любым из) этих языков, «регулярными», после чего вводит регулярные выражения, которые он называет описывают «рациональные языки» и, наконец, формулируют «теорему Клини» как совпадение регулярных и рациональных языков. ^[9] Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками». ^{[1] [2]}

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

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

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

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

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

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

• Сдерживание: L _A ⊆ L _B  ? ^{[примечание 10]}
• Дизъюнктность: L _A ∩ L _B = {}?
• Пустота: L _A = {}?
• Универсальность: L _A = Σ ^*  ?
• Членство: если a ∈ Σ ^* , является ли a ∈ L _B  ?

Для регулярных выражений проблема универсальности NP-полна уже для одноэлементного алфавита. ^[17] Для больших алфавитов эта проблема является PSPACE-полной . ^[18] Если регулярные выражения расширить, чтобы допустить также оператор возведения в квадрат , где « A ² » обозначает то же самое, что и « AA », все равно можно описать только регулярные языки, но проблема универсальности имеет нижнюю границу экспоненциального пространства, ^{[19] [20] [21]} и фактически является полным для экспоненциального пространства относительно полиномиальной редукции по времени. ^[22]

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

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

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

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

Место в иерархии Хомского

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

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

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

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

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

Примечания

1. 1. ⇒ 2. по алгоритму построения Томпсона.
2. 2. ⇒ 1. по алгоритму Клини или по лемме Ардена.
3. 2. ⇒ 3. по конструкции степенного набора
4. 3. ⇒ 2. поскольку первое определение сильнее второго .
5. 2. ⇒ 4. см. Хопкрофт, Ульман (1979), теорема 9.2, стр. 219.
6. 4. ⇒ 2. см. Хопкрофт, Ульман (1979), теорема 9.1, стр. 218.
7. 3. ⇔ 10. по теореме Майхилла – Нерода.
8. u ~ v определяется как: uw € L тогда и только тогда, когда vw € L для всех w € Σ ^*
9. 3. ⇔ 11. см. доказательство в статье «Синтаксический моноид» и см. стр. 160 в Holcombe, WML (1982). Алгебраическая теория автоматов . Кембриджские исследования по высшей математике. Том. 1. Издательство Кембриджского университета . ISBN 0-521-60492-3. Збл  0489.68046.
10. Проверьте, есть ли L _A ∩ L _B знак равно L _A . Решение об этом свойстве вообще является NP-сложным ; см. файл:RegSubsetNP.pdf для иллюстрации идеи доказательства.

Рекомендации

• Берстель, Жан ; Ройтенауэр, Кристоф (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.

1. Руслан Митков (2003). Оксфордский справочник по компьютерной лингвистике. Издательство Оксфордского университета. п. 754. ИСБН 978-0-19-927634-9.
2. Марк В. Лоусон (2003). Конечные автоматы. ЦРК Пресс. стр. 98–103. ISBN 978-1-58488-255-8.
3. Шэн Ю (1997). «Регулярные языки». В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник по формальным языкам: Том 1. Слово, язык, грамматика . Спрингер. п. 41. ИСБН 978-3-540-60420-4.
4. Эйленберг (1974), с. 16 (Пример II, 2.8) и с. 25 (пример II, 5.2).
5. М. Вейер: Глава 12 - Разрешимость S1S и S2S, с. 219, теорема 12.26. В: Эрих Гредель, Вольфганг Томас, Томас Вильке (ред.): Автоматы, логика и бесконечные игры: Путеводитель по текущим исследованиям. Конспекты лекций по информатике 2500, Springer 2002.
6. Роберт Седжвик; Кевин Дэниел Уэйн (2011). Алгоритмы. Аддисон-Уэсли Профессионал. п. 794. ИСБН 978-0-321-57351-3.
7. Жан-Поль Аллуш; Джеффри Шалит (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. п. 129. ИСБН 978-0-521-82332-6.
8. Кеннет Розен (2011). Дискретная математика и ее приложения 7-е издание. МакГроу-Хилл Наука. стр. 873–880.
9. Хорст Бунке; Альберто Санфелиу (январь 1990 г.). Распознавание синтаксических и структурных образов: теория и приложения. Всемирная научная. п. 248. ИСБН 978-9971-5-0566-0.
10. Стивен Коул Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечном автомате (PDF) (Меморандум об исследовании). ВВС США/Корпорация РЭНД.Здесь: стр.46
11. Ноам Хомский (1959). «О некоторых формальных свойствах грамматик» (PDF) . Информация и контроль . 2 (2): 137–167. дои : 10.1016/S0019-9958(59)90362-6 .Здесь: Определение 8, стр.149.
12. Хомский 1959, сноска 10, стр. 150.
13. Саломаа (1981) стр.28
14. Саломаа (1981) стр.27
15. Хопкрофт, Ульман (1979), Глава 3, Упражнение 3.4g, с. 72
16. Хопкрофт, Ульман (1979), теорема 3.8, стр.64; см. также теорему 3.10, с.67
17. Ахо, Хопкрофт, Ульман (1974), Упражнение 10.14, стр.401
18. Ахо, Хопкрофт, Ульман (1974), теорема 10.14, стр. 399
19. Хопкрофт, Ульман (1979), Теорема 13.15, стр.351
20. А. Р. Мейер и Л. Дж. Стокмейер (октябрь 1972 г.). Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF) . 13-й ежегодный симпозиум IEEE. по теории коммутации и автоматов. стр. 125–129.
21. Л. Дж. Стокмейер и А. Р. Мейер (1973). Словесные задачи, требующие экспоненциального времени (PDF) . АКМ. стр. 1–9. {{cite book}}: |work=игнорируется ( помощь )
22. Хопкрофт, Ульман (1979), Следствие, стр.353
23. Вейер, Марк (2002). «Разрешимость S1S и S2S». Автоматы, логика и бесконечные игры . Конспекты лекций по информатике. Том. 2500. Спрингер. стр. 207–230. дои : 10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
24. Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Теория математических систем . 17 (1): 13–27. дои : 10.1007/BF01744431. MR  0738749. S2CID  14677270.
25. Кук, Стивен; Нгуен, Фуонг (2010). Логические основы сложности доказательства (1-е изд.). Итака, Нью-Йорк: Ассоциация символической логики. п. 75. ИСБН 978-0-521-51729-4.
26. Дж. Хартманис, П.Л. Льюис II и Р.Э. Стернс. Иерархии вычислений с ограниченной памятью. Труды 6-го ежегодного симпозиума IEEE по теории переключающих схем и проектированию логики , стр. 179–190. 1965.
27. «Как доказать, что язык неправильный?». cs.stackexchange.com . Проверено 10 апреля 2018 г.
28. Хромкович, Юрай (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмика, рандомизация, коммуникация и криптография. Спрингер. стр. 76–77. ISBN 3-540-14015-8. ОСЛК  53007120.
29. Конечный язык не следует путать с (обычно бесконечным) языком, порожденным конечным автоматом.
30. Фолькер Дикерт; Пол Гастин (2008). «Определимые языки первого порядка» (PDF) . В Йорге Флуме; Эрих Гредель; Томас Уилк (ред.). Логика и автоматы: история и перспективы . Издательство Амстердамского университета. ISBN 978-90-5356-576-6.
31. Хонкала, Джуха (1989). «Необходимое условие рациональности дзета-функции регулярного языка». Теор. Вычислить. Наука . 66 (3): 341–347. дои : 10.1016/0304-3975(89)90159-х . Збл  0675.68034.
32. Flajolet & Sedgweick, раздел V.3.1, уравнение (13).
33. "Количество слов в обычном языке $(00)^*$" . cs.stackexchange.com . Проверено 10 апреля 2018 г.
34. «Доказательство теоремы для произвольных ДКА».
35. «Количество слов заданной длины в обычном языке». cs.stackexchange.com . Проверено 10 апреля 2018 г.
36. Флажоле и Седжвик (2002) Теорема V.3
37. Берстель, Жан; Ройтенауэр, Кристоф (1990). «Дзета-функции формальных языков». Пер. Являюсь. Математика. Соц . 321 (2): 533–546. CiteSeerX 10.1.1.309.3005 . doi : 10.1090/s0002-9947-1990-0998123-x. Збл  0797.68092. 
38. Берстель и Ройтенауэр (2011) стр.222
39. Сэмюэл Эйленберг. Автоматы, языки и машины . Академическая пресса.в двух томах «A» (1974, ISBN 9780080873749 ) и «B» (1976, ISBN 9780080873756 ), последний с двумя главами Брета Тилсона.  
40. Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. п. 8. ISBN 3-7643-3719-2. Збл  0816.68086.
41. Берстель и Ройтенауэр (2011) стр.47
42. Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рубена Томаса. Кембридж: Издательство Кембриджского университета . п. 86. ИСБН 978-0-521-84425-3. Збл  1188.68177.

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

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

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

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