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

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

Определение

Пусть Σ — конечный алфавит. Регулярный язык R(Σ) в алфавите Σ определяется следующими рекурсивными свойствами:
Ничто другое, кроме следующего из перечисленного, не является регулярным множеством в алфавите Σ

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

Данное понятие можно обобщить на произвольный моноид. Подмножество L моноида M называется распознаваемым над M, если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M. Семейство распознаваемых подмножеств моноида M обычно обозначается Rec(M). Так если M — свободный моноид Σ над алфавитом Σ, то семейство Rec(Σ) является просто семейством регулярных языков Reg(Σ).