В теоретической информатики и теории формальных языков , регулярный язык (также называемый рациональный язык ) [1] [2] представляет собой формальный язык , который может быть определен с помощью регулярного выражения , в строгом смысле , в теоретической информатике (в отличие от многие современные механизмы регулярных выражений, которые дополнены функциями , позволяющими распознавать нерегулярные языки).
В качестве альтернативы, обычный язык можно определить как язык, распознаваемый конечным автоматом . Эквивалентность регулярных выражений и конечных автоматов известна как теорема Клини [3] (в честь американского математика Стивена Коула Клини ). В иерархии Хомского регулярные языки - это языки, генерируемые грамматиками типа 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}. [4] Интуитивно это невозможно распознать с помощью конечного автомата, поскольку конечный автомат имеет конечную память и не может запомнить точное количество а. Методы строгого доказательства этого факта приведены ниже .
Эквивалентные формализмы [ править ]
Регулярный язык удовлетворяет следующим эквивалентным свойствам:
- это язык регулярного выражения (согласно приведенному выше определению)
- это язык, принятый недетерминированным конечным автоматом (NFA) [примечание 1] [примечание 2]
- это язык, принятый детерминированным конечным автоматом (DFA) [примечание 3] [примечание 4]
- его можно сгенерировать с помощью обычной грамматики [примечание 5] [примечание 6]
- это язык, принятый переменным конечным автоматом
- это язык, принятый двусторонним конечным автоматом
- он может быть сгенерирован префиксной грамматикой
- он может быть принят машиной Тьюринга только для чтения
- его можно определить в монадической логике второго порядка ( теорема Бюхи – Элгота – Трахтенброта ) [5]
- он распознается некоторым конечным синтаксическим моноидом M , т. е. является прообразом { w ∈ Σ * | f ( w ) ∈ S } подмножества S конечного моноида M при гомоморфизме моноида f : Σ * → M из свободного моноида на его алфавите [примечание 7]
- число классов эквивалентности его синтаксической конгруэнтности конечно. [примечание 8] [примечание 9] (Это число равно числу состояний минимального детерминированного конечного автомата, принимающего L. )
Свойства 10. и 11. представляют собой чисто алгебраические подходы к определению регулярных языков; аналогичный набор утверждений можно сформулировать для моноида M ⊆ Σ * . В этом случае эквивалентность над M приводит к понятию узнаваемого языка.
Некоторые авторы используют одно из вышеперечисленных свойств, отличное от «1». как альтернативное определение обычных языков.
Некоторые из приведенных выше эквивалентностей, особенно те, что относятся к первым четырем формализмам, в учебниках называют теоремой Клини . Какой именно из них (или какое подмножество) называть таковыми, зависит от авторов. Один учебник называет эквивалентность регулярных выражений и NFA («1» и «2» выше) «теоремой Клини». [6] В другом учебнике эквивалентность регулярных выражений и DFA («1» и «3» выше) называется «теоремой Клини». [7] Два других учебника сначала доказывают выразительную эквивалентность NFA и DFA («2» и «3»), а затем заявляют «теорему Клини» как эквивалентность между регулярными выражениями и конечными автоматами (последний, как говорят, описывает »узнаваемые языки »). [2] [8]Лингвистически ориентированный текст сначала приравнивает обычные грамматики («4.» выше) к DFA и NFA, называет языки, созданные (любым из) этими «регулярными», после чего вводит регулярные выражения, которые он называет «рациональными языками», и, наконец, утверждает «теорему Клини» как совпадение регулярных и рациональных языков. [9] Другие авторы просто определяют «рациональное выражение» и «регулярные выражения» как синонимы и делают то же самое с «рациональными языками» и «регулярными языками». [1] [2]
Очевидно, термин «регулярный» происходит из технического отчета 1951 года, в котором Клини ввел «регулярные мероприятия» и явно приветствовал «любые предложения относительно более описательного термина» . [10] Ноам Хомский в своей основополагающей статье 1959 года сначала использовал термин «регулярный» в другом значении (имея в виду то, что сегодня называют « нормальной формой Хомского » ), [11] но заметил, что его «языки с конечным числом состояний» были эквивалентны «регулярным мероприятиям» Клини . [12]
Свойства закрытия [ править ]
Регулярные языки закрыты относительно различных операций, то есть, если языки K и L регулярны, то это является результатом следующих операций:
- заданные теоретико - булевы операции: объединение K ∪ L , пересечение K ∩ L , и дополнение L , а значит , и относительное дополнение K - L . [13]
- регулярные операции: K ∪ L , конкатенация K ∘ L и звезда Клини L * . [14]
- в трио операции: строка гомоморфизм , обратная струна гомоморфизм, и пересечения с регулярными языками. Как следствие, они замкнуты относительно произвольных конечных преобразований , как фактор 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 2 » означает то же, что и « AA », все еще могут быть описаны только регулярные языки, но проблема универсальности имеет экспоненциальную пространственную нижнюю границу, [19] [20] [21] и фактически является полным для экспоненциального пространства относительно редукции за полиномиальное время. [22]
Результаты сложности [ править ]
В теории сложности вычислений , то класс сложности всех регулярных языков иногда называют REGULAR или REG и равна DSPACE (O (1)), то проблемы решения , которые могут быть решены в постоянном пространстве (пространство используется не зависит от размера входного ). ОБЫЧНЫЙ ≠ AC 0 , поскольку он (тривиально) содержит проблему четности для определения того, является ли количество 1 битов на входе четным или нечетным, и эта проблема не в AC 0 . [23] С другой стороны, REGULAR не содержит AC 0., потому что нерегулярный язык палиндромов или нерегулярный язык могут быть распознаны в AC 0 . [24]
Если язык не является регулярным, для его распознавания требуется машина с пространством не менее Ω (log log n ) (где n - размер ввода). [25] Другими словами, DSPACE ( o (log log n )) соответствует классу обычных языков. На практике большинство нерегулярных задач решаются машинами, занимающими хотя бы логарифмическое пространство .
Расположение в иерархии Хомского[ редактировать ]
Чтобы найти обычные языки в иерархии Хомского , нужно заметить, что каждый регулярный язык контекстно-независим . Обратное неверно: например, язык, состоящий из всех строк, имеющих такое же количество букв a , что и b , является контекстно-независимым, но не регулярным. Чтобы доказать, что язык не является регулярным, часто используют теорему Майхилла – Нероде и лемму о накачке . Другие подходы включают использование закрывающих свойств регулярных языков [26] или количественное определение колмогоровской сложности . [27]
Важные подклассы обычных языков включают
- Конечные языки, содержащие только конечное количество слов. [28] Это обычные языки, так как можно создать регулярное выражение , представляющее собой объединение всех слов в языке.
- Языки без звезд , те, которые могут быть описаны регулярным выражением, построенным из пустого символа, букв, конкатенации и всех логических операторов, включая дополнение, но не звезды Клини : этот класс включает все конечные языки. [29]
Количество слов в обычном языке [ править ]
Пусть обозначим число слов длины в . Обыкновенная производящая функция для L представляет собой формальный степенной ряд
Производящая функция языка L является рациональной функцией, если L регулярен. [30] Следовательно , для каждого регулярного языка последовательность является постоянной рекурсивной ; то есть существуют целочисленная константа , комплексные константы и комплексные многочлены такие, что для каждого количество слов длины в равно . [31] [32] [33] [34]
Таким образом, нерегулярность некоторых языков может быть доказана путем подсчета слов заданной длины в . Рассмотрим, например, язык Дейка строк сбалансированных круглых скобок. Количество слов длины в языке Дейка равно каталонскому числу , которое не имеет формы , что свидетельствует о нерегулярности языка Дейка. Следует проявлять осторожность, поскольку некоторые собственные значения могут иметь одинаковую величину. Например, количество слов длины в языке всех четных двоичных слов не имеет формы , а количество слов четной или нечетной длины имеет эту форму; соответствующие собственные значения . В общем, для каждого регулярного языка существует такая константа , что для всех количество слов длины асимптотически . [35]
Дзета - функция языкового L является [30]
Дзета-функция регулярного языка в общем случае не рациональна, в отличие от произвольного циклического языка . [36] [37]
Обобщения [ править ]
Понятие регулярного языка было обобщено на бесконечные слова (см. Ω-автоматы ) и деревья (см. Древовидный автомат ).
Рациональный набор обобщает понятие (регулярного / рационального языка) на моноиды, которые не обязательно свободны . Точно так же понятие распознаваемого языка (с помощью конечного автомата) имеет тезку как узнаваемое множество над моноидом, который не обязательно является свободным. Говард Штраубинг отмечает в связи с этими фактами: «Термин« обычный язык »несколько неудачен. Статьи, написанные под влиянием монографии Эйленберга [38]часто используют либо термин «узнаваемый язык», который относится к поведению автоматов, либо «рациональный язык», который относится к важным аналогиям между регулярными выражениями и рациональными степенными рядами. (Фактически, Эйленберг определяет рациональные и узнаваемые подмножества произвольных моноидов; эти два понятия, в общем, не совпадают.) Эта терминология, хотя и лучше мотивированная, никогда не прижилась, а «обычный язык» используется почти повсеместно ». [39]
Рациональный ряд - еще одно обобщение, на этот раз в контексте формального степенного ряда над полукольцом . Этот подход приводит к взвешенным рациональным выражениям и взвешенным автоматам . В этом алгебраическом контексте регулярные языки (соответствующие логическим взвешенным рациональным выражениям) обычно называются рациональными языками . [40] [41] Также в этом контексте теорема Клини находит обобщение, называемое теоремой Клини-Шютценбергера .
Учимся на примерах [ править ]
Заметки [ править ]
- ^ 1. ⇒ 2. алгоритмом построения Томпсона.
- ^ 2. ⇒ 1. по алгоритму Клини или по лемме Ардена
- ^ 2. ⇒ 3. по построению powerset
- ^ 3. ⇒ 2. поскольку первое определение сильнее второго
- ^ 2. ⇒ 4. см. Hopcroft, Ullman (1979), теорема 9.2, стр.219.
- ^ 4. ⇒ 2. см. Hopcroft, Ullman (1979), теорема 9.1, стр.218.
- ^ 3. ⇔ 10. по теореме Майхилла – Нероде
- ^ u ~ v определяется как: uw ∈ L тогда и только тогда, когда vw ∈ L для всех w ∈Σ *
- ^ 3. ⇔ 11. см. Доказательство встатьео синтаксических моноидах и см. Стр. 160 в Holcombe , WML (1982). Теория алгебраических автоматов . Кембриджские исследования в области высшей математики. 1 . Издательство Кембриджского университета . ISBN 0-521-60492-3. Zbl 0489.68046 .
- ^ Проверьтеесли L ∩ L B = L A . Определить это свойствов целом NP-сложно ; см. File: RegSubsetNP.pdf для иллюстрации идеи доказательства.
Ссылки [ править ]
- Берстель, Жан ; Ройтенауэр, Кристоф (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). Дизайн и анализ компьютерных алгоритмов . Эддисон-Уэсли.
- ^ a b Руслан Митков (2003). Оксфордский справочник компьютерной лингвистики . Издательство Оксфордского университета. п. 754. ISBN 978-0-19-927634-9.
- ^ a b c Марк В. Лоусон (2003). Конечные автоматы . CRC Press. С. 98–103. ISBN 978-1-58488-255-8.
- Перейти ↑ Sheng Yu (1997). «Обычные языки» . В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник формальных языков: Том 1. Слово, язык, грамматика . Springer. п. 41. ISBN 978-3-540-60420-4.
- ↑ Eilenberg (1974), стр. 16 (Пример II, 2.8) и стр. 25 (Пример II, 5.2).
- ^ М. Вейер: Глава 12 - Разрешимость S1S и S2S, стр. 219, теорема 12.26. В: Эрих Грэдель, Вольфганг Томас, Томас Вильке (ред.): Автоматы, логика и бесконечные игры: руководство по текущим исследованиям. Конспект лекций по информатике 2500, Springer 2002.
- ^ Роберт Седжвик; Кевин Дэниел Уэйн (2011). Алгоритмы . Эддисон-Уэсли Профессионал. п. 794. ISBN 978-0-321-57351-3.
- ^ Жан-Поль Аллуш; Джеффри Шаллит (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета. п. 129. ISBN 978-0-521-82332-6.
- ^ Кеннет Розен (2011). Дискретная математика и ее приложения 7-е издание . McGraw-Hill Science. С. 873–880.
- ^ Хорст Бунке; Альберто Санфелиу (январь 1990 г.). Распознавание синтаксических и структурных образов: теория и приложения . World Scientific. п. 248. ISBN 978-9971-5-0566-0.
- ↑ Стивен Коул Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечном автомате (PDF) (меморандум об исследовании). ВВС США / RAND Corporation. Здесь: стр.46
- ↑ Ноам Хомский (1959). «О некоторых формальных свойствах грамматик» (PDF) . Информация и контроль . 2 (2): 137–167. DOI : 10.1016 / S0019-9958 (59) 90362-6 . Здесь: Определение 8, с.149.
- ↑ Хомский, 1959, сноска 10, стр.150
- ^ Salomaa (1981) стр.28
- ^ Salomaa (1981) стр.27
- ^ Hopcroft Ульмана (1979), глава 3, упражнения 3.4g, стр. 72
- ^ Хопкрофт, Ульман (1979), теорема 3.8, стр.64; см. также теорему 3.10, с.67.
- ^ Ах, Hopcroft Ульман (1974), упражнения 10,14, p.401
- ^ Ахо, Хопкрофт, Ульман (1974), теорема 10.14, p399
- ^ Хопкрофт, Ульман (1979), теорема 13.15, стр.351
- ↑ AR Meyer & LJ Stockmeyer (октябрь 1972 г.). Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF) . 13-й ежегодный симпозиум IEEE. по теории переключений и автоматов . С. 125–129.
- ^ LJ Стокмайер & Р. Мейер (1973). Проблемы со словами, требующие экспоненциального времени (PDF) . Proc. 5-е ан. симп. по теории вычислений (STOC) . ACM. С. 1–9.
- ^ Hopcroft Ульмана (1979), следствие p.353
- ^ Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / BF01744431 . Руководство по ремонту 0738749 . S2CID 14677270 .
- ^ Кук, Стивен; Нгуен, Фыонг (2010). Логические основы сложности доказательства (1-е изд.). Итака, штат Нью-Йорк: Ассоциация символической логики. п. 75. ISBN 978-0-521-51729-4.
- ↑ Дж. Хартманис, П. Л. Льюис II и Р. Р. Стернс. Иерархии вычислений с ограничением памяти. Труды 6-го ежегодного симпозиума IEEE по теории коммутационных цепей и логическому проектированию , стр. 179–190. 1965 г.
- ^ "Как доказать, что язык не является регулярным?" . cs.stackexchange.com . Проверено 10 апреля 2018 года .
- ^ Hromkovič, Юрай (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмику, рандомизацию, коммуникацию и криптографию . Springer. С. 76–77. ISBN 3-540-14015-8. OCLC 53007120 .
- ^ Конечный язык не следует путать с (обычно бесконечным) языком, порожденным конечным автоматом.
- ^ Фолькер Дикерт; Пол Гастин (2008). «Определяемые языки первого порядка» (PDF) . В Йорге Флуме; Эрих Гредель; Томас Уилке (ред.). Логика и автоматы: история и перспективы . Издательство Амстердамского университета. ISBN 978-90-5356-576-6.
- ^ a b Хонкала, Джуха (1989). «Необходимое условие рациональности дзета-функции регулярного языка». Теор. Comput. Sci . 66 (3): 341–347. DOI : 10.1016 / 0304-3975 (89) 90159-х . Zbl 0675.68034 .
- ^ Flajolet & Sedgweick, раздел V.3.1, уравнение (13).
- ^ "Количество слов в обычном языке $ (00) ^ * $" . cs.stackexchange.com . Проверено 10 апреля 2018 года .
- ^ Доказательство теоремы для произвольных ДКА
- ^ «Количество слов заданной длины в обычном языке» . cs.stackexchange.com . Проверено 10 апреля 2018 года .
- ^ Flajolet & Седжвик (2002) теорема V.3
- ^ Berstel, Жан; Ройтенауэр, Кристоф (1990). «Дзета-функции формальных языков». Пер. Являюсь. Математика. Soc . 321 (2): 533–546. CiteSeerX 10.1.1.309.3005 . DOI : 10.1090 / s0002-9947-1990-0998123-х . Zbl 0797.68092 .
- ^ Berstel & Reutenauer (2011) с.222
- ^ Сэмюэл Эйленберг. Автоматы, языки и машины . Академическая пресса.в двух томах «А» (1974, ISBN 9780080873749 ) и «В» (1976, ISBN 9780080873756 ), последний с двумя главами Брета Тилсона.
- Перейти ↑ Straubing, Howard (1994). Конечные автоматы, формальная логика и сложность схем . Успехи теоретической информатики. Базель: Биркхойзер. п. 8 . ISBN 3-7643-3719-2. Zbl 0816.68086 .
- ^ Berstel & Reutenauer (2011) стр.47
- ^ Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета . п. 86. ISBN 978-0-521-84425-3. Zbl 1188.68177 .
Дальнейшее чтение [ править ]
- Клини, SC : Представление событий в нервных сетях и конечных автоматах. В: Shannon, CE, McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956); это слегка измененная версия его одноименного отчета корпорации RAND за 1951 год , RM704 .
- Сакарович, J (1987). «Повторный визит к теореме Клини». Тенденции, методы и проблемы теоретической информатики . Конспект лекций по информатике. 1987 . С. 39–50. DOI : 10.1007 / 3540185356_29 . ISBN 978-3-540-18535-2.
Внешние ссылки [ править ]
- СМИ, связанные с обычным языком на Викискладе?
- Зоопарк сложности : Класс REG