Регулярный язык

Регуля́рный язык (регуля́рное мно́жество) в теории формальных языков — множество слов, которое распознает некоторый конечный автомат. Класс регулярных множеств удобно изучать в целом, а полученные результаты оказываются применимы для достаточно широкого спектра формальных языков.

Определение

Пусть $\Sigma$ — конечный алфавит. Регулярными языками в алфавите $\Sigma$ называются множества слов, определяемые по индукции следующим образом:

1. Пустое множество ($\varnothing$) является регулярным языком.
2. Множество, состоящее из одной лишь пустой строки ($\{\epsilon \}$) является регулярным языком.
3. Множество, состоящее из одного однобуквенного слова ($\{a\}$, где $a\in \Sigma$) является регулярным языком.
4. Если $\alpha$ и $\beta$ — регулярные языки, то их объединение ($\alpha \cup \beta$), конкатенация ($\alpha \beta$) и взятие звёздочки Клини (${\alpha }^{\ast }$) тоже являются регулярными языками.
5. Других регулярных языков нет.

Связь автоматных и регулярных языков

Теорема Клини утверждает, что класс регулярных языков совпадает с классом языков распознаваемых конечным автоматом. Это значит, что для любого конечного автомата множество слов, которое он допускает является регулярным языком. И обратно, для любого регулярного языка существует автомат, которые допускает слова из этого языка и только их.

Распознаваемое подмножество моноида

Шаблон:Falseredirect Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается $\mathrm{R}\mathrm{e}\mathrm{c}(M)$.

Так если M — свободный моноид ${\Sigma }^{\ast }$ над алфавитом $\Sigma$, то семейство $\mathrm{R}\mathrm{e}\mathrm{c}\left({\Sigma }^{\ast }\right)$ является просто семейством регулярных языков $\mathrm{R}\mathrm{e}\mathrm{g}\left({\Sigma }^{\ast }\right)$.

Общерегулярное множество

Существует аналог регулярного языка для множеств из сверхслов, бесконечных последовательностей над алфавитом. Индуктивно введём понятие общерегулярного множества (сверхслов), далее просто общерегулярное множество, над алфавитом $A$:

1. Для любого регулярного языка $R$ множество $R^{\mathrm{\infty }}$ - общерегулярно, где $R^{\mathrm{\infty }}$ - все возможные бесконечные последовательности слов из $R$.
2. Объединение общерегулярных множеств - общерегулярно.
3. Конкатенация регулярного языка и общерегулярного множества - общерегулярна, заметим, что конкатенация здесь имеет смысл только в этом порядке.

Верен и аналог теоремы Клини - теорема Мак-Нотона, для её описания потребуется ввести ряд определений.

Буква $a$ сверхслова $\alpha$ называется предельной, если существует последовательность ${\{j_i\}}_{i=1}^{\mathrm{\infty }}$, такая что $\mathrm{\forall }i\alpha (j_i)=a$.

Множество предельных букв сверхслова $\alpha$ называют его пределом и пишут: $lim(\alpha )$.

Естественным образом можно определить работу автомата при подаче на него сверхслова.

Пусть $V=(A,Q,B,\varphi ,\psi ,q)$ - инициальный конечный автомат, ${\{B_i\}}_{i=1}^N$ - множество подмножеств алфавита $B$, тогда автомат $V$ представляет $E\subset A^{\mathrm{\infty }}$ с помощью выделенного набора подмножеств ${\{B_i\}}_{i=1}^N$, если $\alpha \in E\iff \mathrm{\exists }i<N:lim(\overline{\psi }(q,\alpha ))=B_i$.

Подмножество $A^{\mathrm{\infty }}$ называют сверхсобытием в алфавите $A$.

Сверхсобытие называют представимым, если существует автомат $V=(A,Q,B,\varphi ,\psi ,q)$ и набор подмножеств ${\{B_i\}}_{i=1}^N$ множества $B$, такие что автомат $V$ представляет это сверхсобытие с помощью ${\{B_i\}}_{i=1}^N$.

Итак теорема Мак-Нотона утверждает, что множество представимых сверхсобытий совпадает с множеством общерегулярных множеств.

См. также

• Свойство замкнутости регулярных языков

Литература

• В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Введение в теорию автоматов. М., "Наука", 1985.
• В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. Элементы теории автоматов. М., изд-во МГУ, 1978.