Обычный язык

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Производящая функция языка L является рациональной функцией, если L регулярен. ^{[ 32 ]} Следовательно, для каждого регулярного языка $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}$ . ^{[ 33 ]}^{[ 34 ]}^{[ 35 ]}^{[ 36 ]}

Таким образом, нерегулярность некоторых языков $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}$ . ^{[ 37 ]}

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

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

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

Обобщения

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

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

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

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

Примечания

^ 1. ⇒ 2. по алгоритму построения Томпсона.
^ 2. ⇒ 1. по алгоритму Клини или по лемме Ардена.
^ 2. ⇒ 3. по конструкции степенного набора
^ 3. ⇒ 2. поскольку первое определение сильнее второго.
^ 2. ⇒ 4. см. Хопкрофт, Ульман (1979), теорема 9.2, стр. 219.
^ 4. ⇒ 2. см. Хопкрофт, Ульман (1979), теорема 9.1, стр. 218.
^ 3. ⇔ 10. по теореме Майхилла – Нерода.
^ u ~ v определяется как: uw € L тогда и только тогда, когда vw € L для всех w €Σ ^*
^ 3. ⇔ 11. см. доказательство в статье Синтаксический моноид и см. стр. 160 в Холкомб, WML (1982). Алгебраическая теория автоматов . Кембриджские исследования по высшей математике. Том. 1. Издательство Кембриджского университета . ISBN 0-521-60492-3 . Збл 0489.68046 .
^ Проверьте, есть ли 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 .

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

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

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

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

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

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

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

[7] 2. ⇒ 3. по конструкции степенного набора

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

[9] 2. ⇒ 4. см. Хопкрофт, Ульман (1979), теорема 9.2, стр. 219.

[10] 4. ⇒ 2. см. Хопкрофт, Ульман (1979), теорема 9.1, стр. 218.

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

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

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

[27] Проверьте, есть ли L _A ∩ L _{B знак} равно L _A . Решение об этом свойстве является NP-сложным вообще ; см. файл:RegSubsetNP.pdf для иллюстрации идеи доказательства.

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

[Lawson2003-2] Jump up to: ^а ^б ^с Марк В. Лоусон (2003). Конечные автоматы . ЦРК Пресс. стр. 98–103. ISBN 978-1-58488-255-8 .

[RozenbergSalomaa1997-3] Шэн Юй (1997). «Регулярные языки» . В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник по формальным языкам: Том 1. Слово, язык, грамматика . Спрингер. п. 41. ИСБН 978-3-540-60420-4 .

[4] Эйленберг (1974), с. 16 (Пример II, 2.8) и с. 25 (пример II, 5.2).

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

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

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

[Rosen2011-17] Кеннет Розен (2011). Дискретная математика и ее приложения. 7-е издание . МакГроу-Хилл Наука. стр. 873–880.

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

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

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

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

[Sal28-22] Саломаа (1981) стр.28

[Sal27-23] Саломаа (1981) стр.27

[24] Товарищи, Майкл Р .; Лэнгстон, Майкл А. (1991). «Проблемы конструктивности в графовых алгоритмах». В Майерсе, Дж. Поле младшем; О'Доннелл, Майкл Дж. (ред.). Конструктивность в информатике, Летний симпозиум, Сан-Антонио, Техас, США, 19–22 июня, Материалы . Конспекты лекций по информатике. Том. 613. Спрингер. стр. 150–158. дои : 10.1007/BFB0021088 .

[25] Хопкрофт, Ульман (1979), Глава 3, Упражнение 3.4g, с. 72

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

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

[29] Ахо, Хопкрофт, Ульман (1974), теорема 10.14, стр. 399

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

[31] А. Р. Мейер и Л. Дж. Стокмейер (октябрь 1972 г.). Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF) . 13-й ежегодный симпозиум IEEE. по теории коммутации и автоматов. стр. 125–129.

[32] Л. Дж. Стокмейер; А. Р. Мейер (1973). «Словесные задачи, требующие экспоненциального времени». Учеб. 5-летие. симп. по теории вычислений (STOC) (PDF) . АКМ. стр. 1–9.

[33] Хопкрофт, Ульман (1979), Следствие, стр.353

[34] Вейер, Марк (2002). «Разрешимость S1S и S2S» . Автоматы, логика и бесконечные игры . Конспекты лекций по информатике. Том. 2500. Спрингер. стр. 207–230. дои : 10.1007/3-540-36387-4_12 . ISBN 978-3-540-00388-5 .

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

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

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

[38] «Как доказать, что язык неправильный?» . cs.stackexchange.com . Проверено 10 апреля 2018 г.

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

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

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

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

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

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

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

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

[47] Флажоле и Седжвик (2002) Теорема V.3

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

[49] Берстель и Ройтенауэр (2011) стр.222

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

[51] Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы . Прогресс в теоретической информатике. Базель: Биркхойзер. п. 8 . ISBN 3-7643-3719-2 . Заказ № 0816.68086 .

[52] Берстель и Ройтенауэр (2011) стр.47

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

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ примечание 1 ]

[ примечание 2 ]

[ примечание 3 ]

[ примечание 4 ]

[ примечание 5 ]

[ примечание 6 ]

[ 5 ]

[ примечание 7 ]

[ примечание 8 ]

[ примечание 9 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ примечание 10 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]