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

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

Определение

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

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

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

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

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

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

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

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

См. также

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