Обычный язык - Regular language

Чтобы узнать о регулируемом естественном языке, см. Список языковых регуляторов.
«Теорема Клини» перенаправляется сюда. По поводу его теорем для рекурсивных функций см. Теорема Клини о рекурсии.

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

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

Обычные языки особенно полезны при вводе разбор и язык программирования дизайн.

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

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

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

Видеть регулярное выражение за его синтаксис и семантику. Обратите внимание, что приведенные выше случаи являются определяющими правилами регулярного выражения.

Примеры

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

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

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

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

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

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

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

  • теоретико-множественные булевы операции: союз K ∪ L, пересечение K ∩ L, и дополнять L, следовательно, также относительное дополнение K - L.[10]
  • регулярные операции: K ∪ L, конкатенация K ∘ L, и Клини звезда L*.[11]
  • то трио операции: гомоморфизм струн, обратный гомоморфизм строк и пересечение с регулярными языками. Как следствие, они закрываются при произвольном конечные преобразования, подобно частное K / L с обычным языком. Более того, регулярные языки закрываются относительно частных с произвольный языки: Если L регулярно тогда L / K регулярно для любого K.[нужна цитата ]
  • обратное (или зеркальное отображение) Lр.[12] Учитывая недетерминированный конечный автомат для распознавания L, автомат для Lр можно получить, изменив все переходы и поменяв местами начальное и конечное состояния. Это может привести к нескольким стартовым состояниям; Для их соединения можно использовать ε-переходы.

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

Для двух детерминированных конечных автоматов А и B, решаемо, принимают ли они один и тот же язык.[13]Как следствие, использование над свойства замыкания, следующие задачи также разрешимы для произвольно заданных детерминированных конечных автоматов А и B, с принятыми языками LА и LB, соответственно:

  • Сдерживание: есть LА ⊆ LB ?[примечание 10]
  • Несвязанность: есть LА ∩ LB = {} ?
  • Пустота: есть LА = {} ?
  • Универсальность: есть LА = Σ* ?
  • Членство: дано а ∈ Σ*, является а ∈ LB ?

Для регулярных выражений проблема универсальности НП-полный уже для одноэлементного алфавита.[14]Для более крупных алфавитов эта проблема PSPACE-полный.[15] Если регулярные выражения расширены, чтобы разрешить также оператор возведения в квадрат, с "А2"означает то же, что и"AA", по-прежнему можно описывать только регулярные языки, но проблема универсальности имеет экспоненциальную пространственную нижнюю границу,[16][17][18] и фактически является полным для экспоненциального пространства относительно редукции за полиномиальное время.[19]

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

В теория сложности вычислений, то класс сложности всех обычных языков иногда называют ОБЫЧНЫЙ или же REG и равно DSPACE (O (1)), проблемы решения которая может быть решена в постоянном пространстве (используемое пространство не зависит от размера ввода). ОБЫЧНЫЙ ≠ AC0, поскольку он (тривиально) содержит проблему четности для определения того, является ли количество 1 битов на входе четным или нечетным, и этой проблемы нет в AC0.[20] С другой стороны, ОБЫЧНЫЙ не содержит AC0, потому что нерегулярный язык палиндромы, или нерегулярный язык оба могут быть признаны в AC0.[21]

Если язык нет обычный, для этого требуется машина с как минимум Ω (журнал журнал п) пространство для распознавания (где п - размер ввода).[22] Другими словами, DSPACE (о (журнал журнал п)) равен классу обычных языков. На практике большинство нестандартных задач решает машины с минимальной логарифмическое пространство.

Расположение в иерархии Хомского

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

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

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

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

Позволять обозначают количество слов длины в . В обычная производящая функция за L это формальный степенной ряд

Производящая функция языка L это рациональная функция если L регулярно.[27] Следовательно, для каждого обычного языка последовательность является константно-рекурсивный; то есть существует целочисленная константа , комплексные константы и комплексные многочлены так что для каждого номер слов длины в является.[28][29][30][31]

Таким образом, нерегулярность некоторых языков можно доказать путем подсчета слов заданной длины в. Рассмотрим, например, Язык Дайка строк сбалансированных круглых скобок. Количество слов длины на языке Дейка равно Каталонский номер , который не имеет формы , свидетельствуя о нерегулярности языка Дейка. Следует соблюдать осторожность, поскольку некоторые из собственных значений мог иметь такую ​​же величину. Например, количество слов длины на языке всех даже двоичных слов не имеет формы , но количество слов четной или нечетной длины имеют эту форму; соответствующие собственные значения . В общем, для каждого регулярного языка существует постоянная такой, что для всех , количество слов длины асимптотически .[32]

В дзета-функция языка L является[27]

Дзета-функция регулярного языка в общем не рациональна, но дзета-функция произвольного циклический язык является.[33][34]

Обобщения

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

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

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

Индукция

Основная статья: Индукция обычных языков

Примечания

  1. ^ 1. ⇒ 2. по Алгоритм построения Томпсона
  2. ^ 2. ⇒ 1. по Алгоритм Клини или используя Лемма Ардена
  3. ^ 2. ⇒ 3. конструкция электростанции
  4. ^ 3. ⇒ 2. так как первое определение сильнее, чем последний
  5. ^ 2. ⇒ 4. см. Hopcroft, Ullman (1979), теорема 9.2, стр.219.
  6. ^ 4. ⇒ 2. см. Hopcroft, Ullman (1979), теорема 9.1, стр. 218.
  7. ^ 3. ⇔ 10. Теорема Майхилла – Нероде
  8. ^ ты~v определяется как: уф∈L если и только если vw∈L для всех ш∈Σ*
  9. ^ 3. ⇔ 11. см. Доказательство в Синтаксический моноид статью и см. стр. 160 в Холкомб, W.M.L. (1982). Теория алгебраических автоматов. Кембриджские исследования в области высшей математики. 1. Издательство Кембриджского университета. ISBN  0-521-60492-3. Zbl  0489.68046.
  10. ^ Проверить, если LА ∩ LB = LА. Решив, что это свойство NP-жесткий в целом; видеть Файл: RegSubsetNP.pdf для иллюстрации идеи доказательства.

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

  1. ^ а б Руслан Митков (2003). Оксфордский справочник по компьютерной лингвистике. Издательство Оксфордского университета. п. 754. ISBN  978-0-19-927634-9.
  2. ^ а б c Марк В. Лоусон (2003). Конечные автоматы. CRC Press. С. 98–103. ISBN  978-1-58488-255-8.
  3. ^ Шэн Ю (1997). «Обычные языки». В Гжегоже Розенберге; Арто Саломаа (ред.). Справочник формальных языков: Том 1. Слово, язык, грамматика.. Springer. п. 41. ISBN  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. ISBN  978-0-321-57351-3.
  7. ^ Жан-Поль Аллуш; Джеффри Шаллит (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. п. 129. ISBN  978-0-521-82332-6.
  8. ^ Кеннет Розен (2011). Дискретная математика и ее приложения 7-е издание. McGraw-Hill Science. С. 873–880.
  9. ^ Хорст Бунке; Альберто Санфелиу (январь 1990 г.). Распознавание синтаксических и структурных образов: теория и приложения. World Scientific. п. 248. ISBN  978-9971-5-0566-0.
  10. ^ Саломаа (1981) стр.28
  11. ^ Саломаа (1981) стр.27
  12. ^ Хопкрофт, Ульман (1979), глава 3, упражнение 3.4g, стр. 72
  13. ^ Хопкрофт, Ульман (1979), теорема 3.8, с.64; см. также теорему 3.10, с.67.
  14. ^ Ахо, Хопкрофт, Ульман (1974), Упражнение 10.14, стр.401
  15. ^ Ахо, Хопкрофт, Ульман (1974), теорема 10.14, стр. 399
  16. ^ Хопкрофт, Ульман (1979), теорема 13.15, с.351
  17. ^ A.R. Мейер и Л.Дж. Стокмейер (октябрь 1972 г.). Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства (PDF). 13-й ежегодный симпозиум IEEE. по теории переключений и автоматов. С. 125–129.
  18. ^ Штокмейер и А. Мейер (1973). Проблемы со словами, требующие экспоненциального времени (PDF). Proc. 5-е ан. симп. по теории вычислений (STOC). ACM. С. 1–9.
  19. ^ Хопкрофт, Ульман (1979), Следствие с.353
  20. ^ Ферст, Меррик; Сакс, Джеймс Б.; Сипсер, Майкл (1984). «Четность, схемы и полиномиальная иерархия». Математическая теория систем. 17 (1): 13–27. Дои:10.1007 / BF01744431. МИСТЕР  0738749.
  21. ^ Повар, Стивен; Нгуен, Фыонг (2010). Логические основы сложности доказательства (1-е изд.). Итака, штат Нью-Йорк: Ассоциация символической логики. п. 75. ISBN  978-0-521-51729-4.
  22. ^ Дж. Хартманис, П. Л. Льюис II и Р. Э. Стернс. Иерархии вычислений с ограничением памяти. Труды 6-го ежегодного симпозиума IEEE по теории коммутационных цепей и логическому проектированиюС. 179–190. 1965 г.
  23. ^ «Как доказать, что язык не является регулярным?». cs.stackexchange.com. Получено 10 апреля 2018.
  24. ^ Громкович, Юрай (2004). Теоретическая информатика: введение в автоматы, вычислимость, сложность, алгоритмику, рандомизацию, коммуникацию и криптографию. Springer. С. 76–77. ISBN  3-540-14015-8. OCLC  53007120.
  25. ^ Конечный язык не следует путать с (обычно бесконечным) языком, порожденным конечным автоматом.
  26. ^ Фолькер Дикерт; Пол Гастин (2008). "Определимые языки первого порядка" (PDF). В Йорге Флуме; Эрих Гредель; Томас Уилке (ред.). Логика и автоматы: история и перспективы. Издательство Амстердамского университета. ISBN  978-90-5356-576-6.
  27. ^ а б Хонкала, Джуха (1989). «Необходимое условие рациональности дзета-функции регулярного языка». Теор. Comput. Наука. 66 (3): 341–347. Дои:10.1016 / 0304-3975 (89) 90159-х. Zbl  0675.68034.
  28. ^ Flajolet & Sedgweick, раздел V.3.1, уравнение (13).
  29. ^ "Количество слов в обычном языке $ (00) ^ * $". cs.stackexchange.com. Получено 10 апреля 2018.
  30. ^ Доказательство теоремы для произвольных ДКА.
  31. ^ «Количество слов заданной длины в обычном языке». cs.stackexchange.com. Получено 10 апреля 2018.
  32. ^ Флажолет и Седжвик (2002) Теорема V.3
  33. ^ Берстель, Жан; Ройтенауэр, Кристоф (1990). «Дзета-функции формальных языков». Пер. Являюсь. Математика. Soc. 321 (2): 533–546. CiteSeerX  10.1.1.309.3005. Дои:10.1090 / с0002-9947-1990-0998123-х. Zbl  0797.68092.
  34. ^ Berstel & Reutenauer (2011) стр.222
  35. ^ Сэмюэл Эйленберг. Автоматы, языки и машины. Академическая пресса. в двух томах «А» (1974 г., ISBN  9780080873749) и «Б» (1976 г., ISBN  9780080873756), последний с двумя главами Брета Тилсона.
  36. ^ Штраубинг, Ховард (1994). Конечные автоматы, формальная логика и сложность схемы. Успехи теоретической информатики. Базель: Биркхойзер. п.8. ISBN  3-7643-3719-2. Zbl  0816.68086.
  37. ^ Berstel & Reutenauer (2011) стр.47.
  38. ^ Сакарович, Жак (2009). Элементы теории автоматов. Перевод с французского Рувима Томаса. Кембридж: Издательство Кембриджского университета. п. 86. ISBN  978-0-521-84425-3. Zbl  1188.68177.

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

  • Kleene, S.C.: Представление событий в нервных сетях и конечных автоматах. В: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Принстон (1956); это немного измененная версия его 1951 г. RAND Corporation отчет с таким же названием, RM704.
  • Сакарович, J (1987). "Повторное обращение к теореме Клини". Конспект лекций по информатике. 1987: 39–50. Дои:10.1007/3540185356_29. ISBN  978-3-540-18535-2. Цитировать журнал требует | журнал = (помощь)

внешняя ссылка