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

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

Определение

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

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