Обычный язык

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

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

Формальное определение [ править ]

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

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

См регулярное выражение для синтаксиса и семантики регулярных выражений.

Примеры [ править ]

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

Простым примером языка, который не является регулярным, является набор строк { a ⁿ b ⁿ | 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 ² » означает то же, что и « AA », все еще могут быть описаны только регулярные языки, но проблема универсальности имеет экспоненциальную пространственную нижнюю границу, ^[19]^[20]^[21] и фактически является полным для экспоненциального пространства относительно редукции за полиномиальное время. ^[22]

Результаты сложности [ править ]

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

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

Расположение в иерархии Хомского[ редактировать ]

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

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

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

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

Количество слов в обычном языке [ править ]

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

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

Производящая функция языка L является рациональной функцией, если L регулярен. ^[30] Следовательно , для каждого регулярного языка последовательность является постоянной рекурсивной ; то есть существуют целочисленная константа , комплексные константы и комплексные многочлены такие, что для каждого количество слов длины в равно . ^[31]^[32]^[33]^[34] ${\ displaystyle L}$ ${\ Displaystyle s_ {L} (п) _ {п \ geq 0}}$ ${\ displaystyle 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$ . В общем, для каждого регулярного языка существует такая константа , что для всех количество слов длины асимптотически . ^[35] $d$ $a$ $dm+a$ $C_{a}m^{p_{a}}\lambda _{a}^{m}$

Дзета - функция языкового L является ^[30]

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

Дзета-функция регулярного языка в общем случае не рациональна, в отличие от произвольного циклического языка . ^[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
^ Hopcroft Ульмана (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

[5] 1. ⇒ 2. алгоритмом построения Томпсона.

[6] 2. ⇒ 1. по алгоритму Клини или по лемме Ардена

[7] 2. ⇒ 3. по построению powerset

[8] 3. ⇒ 2. поскольку первое определение сильнее второго

[9] 2. ⇒ 4. см. Hopcroft, Ullman (1979), теорема 9.2, стр.219.

[10] 4. ⇒ 2. см. Hopcroft, Ullman (1979), теорема 9.1, стр.218.

[12] 3. ⇔ 10. по теореме Майхилла – Нероде

[13] u ~ v определяется как: uw ∈ L тогда и только тогда, когда vw ∈ L для всех w ∈Σ^*

[14] 3. ⇔ 11. см. Доказательство встатьео синтаксических моноидах и см. Стр. 160 в Holcombe , WML (1982). Теория алгебраических автоматов . Кембриджские исследования в области высшей математики. 1 . Издательство Кембриджского университета . ISBN 0-521-60492-3. Zbl 0489.68046 .

[26] Проверьтеесли L ∩ L _B = L _A . Определить это свойствов целом NP-сложно ; см. File: RegSubsetNP.pdf для иллюстрации идеи доказательства.

[Mitkov2003-1] Руслан Митков (2003). Оксфордский справочник компьютерной лингвистики . Издательство Оксфордского университета. п. 754. ISBN 978-0-19-927634-9.

[Lawson2003-2] Марк В. Лоусон (2003). Конечные автоматы . CRC Press. С. 98–103. ISBN 978-1-58488-255-8.

[RozenbergSalomaa1997-3] Перейти ↑ Sheng Yu (1997). «Обычные языки» . В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник формальных языков: Том 1. Слово, язык, грамматика . Springer. п. 41. ISBN 978-3-540-60420-4.

[4] Eilenberg (1974), стр. 16 (Пример II, 2.8) и стр. 25 (Пример II, 5.2).

[11] М. Вейер: Глава 12 - Разрешимость S1S и S2S, стр. 219, теорема 12.26. В: Эрих Грэдель, Вольфганг Томас, Томас Вильке (ред.): Автоматы, логика и бесконечные игры: руководство по текущим исследованиям. Конспект лекций по информатике 2500, Springer 2002.

[SedgewickWayne2011-15] Роберт Седжвик; Кевин Дэниел Уэйн (2011). Алгоритмы . Эддисон-Уэсли Профессионал. п. 794. ISBN 978-0-321-57351-3.

[AlloucheShallit2003-16] Жан-Поль Аллуш; Джеффри Шаллит (2003). Автоматические последовательности: теория, приложения, обобщения . Издательство Кембриджского университета. п. 129. ISBN 978-0-521-82332-6.

[Rosen2011-17] Кеннет Розен (2011). Дискретная математика и ее приложения 7-е издание . McGraw-Hill Science. С. 873–880.

[BunkeSanfeliu1990-18] Хорст Бунке; Альберто Санфелиу (январь 1990 г.). Распознавание синтаксических и структурных образов: теория и приложения . World Scientific. п. 248. ISBN 978-9971-5-0566-0.

[19] Стивен Коул Клини (декабрь 1951 г.). Представление событий в нервных сетях и конечном автомате (PDF) (меморандум об исследовании). ВВС США / RAND Corporation. Здесь: стр.46

[Chomsky.1959a-20] Ноам Хомский (1959). «О некоторых формальных свойствах грамматик» (PDF) . Информация и контроль . 2 (2): 137–167. DOI : 10.1016 / S0019-9958 (59) 90362-6 . Здесь: Определение 8, с.149.

[21] Хомский, 1959, сноска 10, стр.150

[Sal28-22] Salomaa (1981) стр.28

[Sal27-23] Salomaa (1981) стр.27

[24] Hopcroft Ульмана (1979), глава 3, упражнения 3.4g, стр. 72

[25] Hopcroft Ульмана (1979), теорема 3.8, с.64; см. также теорему 3.10, с.67.

[27] Ах, Hopcroft Ульман (1974), упражнения 10,14, p.401

[28] Ахо, Хопкрофт, Ульман (1974), теорема 10.14, p399

[29] Хопкрофт, Ульман (1979), теорема 13.15, стр.351

[30] AR Meyer & LJ Stockmeyer (октябрь 1972 г.). Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF) . 13-й ежегодный симпозиум IEEE. по теории переключений и автоматов . С. 125–129.

[31] LJ Стокмайер & Р. Мейер (1973). Проблемы со словами, требующие экспоненциального времени (PDF) . Proc. 5-е ан. симп. по теории вычислений (STOC) . ACM. С. 1–9.

[32] Hopcroft Ульмана (1979), следствие p.353

[33] Ферст, Меррик; Сакс, Джеймс Б .; Сипсер, Майкл (1984). «Четность, схемы и иерархия полиномиального времени». Математическая теория систем . 17 (1): 13–27. DOI : 10.1007 / BF01744431 . Руководство по ремонту 0738749 . S2CID 14677270 .

[34] Кук, Стивен; Нгуен, Фыонг (2010). Логические основы сложности доказательства (1-е изд.). Итака, штат Нью-Йорк: Ассоциация символической логики. п. 75. ISBN 978-0-521-51729-4.

[35] Дж. Хартманис, П. Л. Льюис II и Р. Р. Стернс. Иерархии вычислений с ограничением памяти. Труды 6-го ежегодного симпозиума IEEE по теории коммутационных цепей и логическому проектированию , стр. 179–190. 1965 г.

[36] "Как доказать, что язык не является регулярным?" . cs.stackexchange.com . Проверено 10 апреля 2018 года .

[37] Hromkovič, Юрай (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмику, рандомизацию, коммуникацию и криптографию . Springer. С. 76–77. ISBN 3-540-14015-8. OCLC 53007120 .

[38] Конечный язык не следует путать с (обычно бесконечным) языком, порожденным конечным автоматом.

[39] Фолькер Дикерт; Пол Гастин (2008). «Определяемые языки первого порядка» (PDF) . В Йорге Флуме; Эрих Гредель; Томас Уилке (ред.). Логика и автоматы: история и перспективы . Издательство Амстердамского университета. ISBN 978-90-5356-576-6.

[Honkala-40] Хонкала, Джуха (1989). «Необходимое условие рациональности дзета-функции регулярного языка». Теор. Comput. Sci . 66 (3): 341–347. DOI : 10.1016 / 0304-3975 (89) 90159-х . Zbl 0675.68034 .

[41] Flajolet & Sedgweick, раздел V.3.1, уравнение (13).

[42] "Количество слов в обычном языке $ (00) ^ * $" . cs.stackexchange.com . Проверено 10 апреля 2018 года .

[43] Доказательство теоремы для произвольных ДКА

[44] «Количество слов заданной длины в обычном языке» . cs.stackexchange.com . Проверено 10 апреля 2018 года .

[45] Flajolet & Седжвик (2002) теорема V.3

[46] Berstel, Жан; Ройтенауэр, Кристоф (1990). «Дзета-функции формальных языков». Пер. Являюсь. Математика. Soc . 321 (2): 533–546. CiteSeerX 10.1.1.309.3005 . DOI : 10.1090 / s0002-9947-1990-0998123-х . Zbl 0797.68092 .

[47] Berstel & Reutenauer (2011) с.222

[Eilenberg1974-48] Сэмюэл Эйленберг. Автоматы, языки и машины . Академическая пресса.в двух томах «А» (1974, ISBN 9780080873749 ) и «В» (1976, ISBN 9780080873756 ), последний с двумя главами Брета Тилсона.

[49] Перейти ↑ Straubing, Howard (1994). Конечные автоматы, формальная логика и сложность схем . Успехи теоретической информатики. Базель: Биркхойзер. п. 8 . ISBN 3-7643-3719-2. Zbl 0816.68086 .

[50] Berstel & Reutenauer (2011) стр.47

[51] Сакарович, Жак (2009). Элементы теории автоматов . Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета . п. 86. ISBN 978-0-521-84425-3. Zbl 1188.68177 .

[1]