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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Примечания

Литература

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