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

---

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

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

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

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

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

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

---