- Распознаваемый язык
-
В математике и информатике распознаваемым языком называется формальный язык, который распознаётся конечным автоматом. Эквивалентным определением является следующее: язык, для которого семейство коэффициентов для синтаксического отношения конечно.
Определение
Для данного моноида M, языком над M называется подмножество
. Такой язык называется распознаваемым над M если существует конечный автомат над M, который принимает L. Конечный автомат над M — это автомат, который принимает на вход элементы из M.
Семейство распознаваемых языков над M обычно обозначается
.
Примеры
Если M — свободный моноид
над алфавитом
, то семейство
является просто семейством регулярных языков
.
Для улучшения этой статьи желательно?: - Воспользоваться подсказкой и установить ссылки из других статей Википедии.
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Категория:- Формальные языки
Wikimedia Foundation. 2010.