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

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

Определение

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

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

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

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

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

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

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

См. также

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