Распознаваемый язык

В математике и информатике распознаваемым языком называется формальный язык, который распознаётся конечным автоматом. Эквивалентным определением является следующее: язык, для которого семейство коэффициентов для синтаксического отношения конечно.

Определение

Для данного моноида M, языком над M называется подмножество $L\subset M$. Такой язык называется распознаваемым над M если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M.

Семейство распознаваемых языков над M обычно обозначается $REC(M)$.

Примеры

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