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

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

ОпределениеПравить

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

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

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

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

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

Запрос «Распознаваемое подмножество моноида»^[d] перенаправляется сюда. На эту тему нужно создать отдельную статью.

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

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

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

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

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

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

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

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

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

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

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

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

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

См. такжеПравить

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

ЛитератураПравить

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