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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Определение[править | править вики-текст]

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

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

Примеры[править | править вики-текст]

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