Русская Википедия:Регулярный язык
Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.
Определение
Пусть <math>\Sigma</math> — конечный алфавит. Регулярными языками в алфавите <math>\Sigma</math> называются множества слов, определяемые по индукции следующим образом:
- Пустое множество (<math>\varnothing</math>) является регулярным языком.
- Множество, состоящее из одной лишь пустой строки (<math>\{ \varepsilon \}</math>) является регулярным языком.
- Множество, состоящее из одного однобуквенного слова (<math>\{ a \}</math>, где <math>a \in \Sigma</math>) является регулярным языком.
- Если <math>\alpha</math> и <math>\beta</math> — регулярные языки, то их объединение (<math>\alpha \cup \beta</math>), конкатенация (<math>\alpha \beta</math>) и взятие звёздочки Клини (<math>\alpha^*</math>) тоже являются регулярными языками.
- Других регулярных языков нет.
Связь автоматных и регулярных языков
Теорема Клини утверждает, что класс регулярных языков совпадает с классом языков распознаваемых конечным автоматом. Это значит, что для любого конечного автомата множество слов, которое он допускает является регулярным языком. И обратно, для любого регулярного языка существует автомат, которые допускает слова из этого языка и только их.
Распознаваемое подмножество моноида
Шаблон:Falseredirect Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается <math>\mathrm{Rec}(M)</math>[1].
Так если M — свободный моноид <math>\Sigma^*</math> над алфавитом <math>\Sigma</math>, то семейство <math>\mathrm{Rec}\left(\Sigma^*\right)</math> является просто семейством регулярных языков <math>\mathrm{Reg}\left(\Sigma^*\right)</math>.
Общерегулярное множество
Существует аналог регулярного языка для множеств из сверхслов, бесконечных последовательностей над алфавитом. Индуктивно введём понятие общерегулярного множества (сверхслов), далее просто общерегулярное множество, над алфавитом <math>A</math>:
- Для любого регулярного языка <math>R</math> множество <math>R^{\infty}</math> - общерегулярно, где <math>R^{\infty}</math> - все возможные бесконечные последовательности слов из <math>R</math>.
- Объединение общерегулярных множеств - общерегулярно.
- Конкатенация регулярного языка и общерегулярного множества - общерегулярна, заметим, что конкатенация здесь имеет смысл только в этом порядке.
Верен и аналог теоремы Клини - теорема Мак-Нотона, для её описания потребуется ввести ряд определений.
Буква <math>a</math> сверхслова <math>\alpha</math> называется предельной, если существует последовательность <math>{\{j_i\}}_{i = 1}^{\infty}</math>, такая что <math>\forall i\; \alpha(j_i) = a</math>.
Множество предельных букв сверхслова <math>\alpha</math> называют его пределом и пишут: <math>lim(\alpha)</math>.
Естественным образом можно определить работу автомата при подаче на него сверхслова.
Пусть <math>V = (A, Q, B, \phi, \psi, q)</math> - инициальный конечный автомат, <math>{\{B_i\}}_{i = 1}^{N}</math> - множество подмножеств алфавита <math>B</math>, тогда автомат <math>V</math> представляет <math>E\subset A^{\infty}</math> с помощью выделенного набора подмножеств <math>{\{B_i\}}_{i = 1}^{N}</math>, если <math>\alpha \in E \Leftrightarrow \exist i < N:lim(\bar{\psi}(q, \alpha)) = B_i</math>.
Подмножество <math>A^{\infty}</math> называют сверхсобытием в алфавите <math>A</math>.
Сверхсобытие называют представимым, если существует автомат <math>V = (A, Q, B, \phi, \psi, q)</math> и набор подмножеств <math>{\{B_i\}}_{i = 1}^{N}</math> множества <math>B</math>, такие что автомат <math>V</math> представляет это сверхсобытие с помощью <math>{\{B_i\}}_{i = 1}^{N}</math>.
Итак теорема Мак-Нотона утверждает, что множество представимых сверхсобытий совпадает с множеством общерегулярных множеств.
См. также
Примечания
Литература
- В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Введение в теорию автоматов. М., "Наука", 1985.
- В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Элементы теории автоматов. М., изд-во МГУ, 1978.
Шаблон:Rq Шаблон:Формальные языки
- ↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Шаблон:Wayback, Chapter IV: Recognisable and rational sets
