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

Пусть ${\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)}$[1].

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

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