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

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

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

Определение

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

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

Примеры

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


Wiki letter w.svg
 Для улучшения этой статьи желательно?:
  • Связать?
    Воспользоваться подсказкой и установить ссылки из других статей Википедии.
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Полезное


Смотреть что такое "Распознаваемый язык" в других словарях:

  • Рекурсивно перечислимый язык — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источни …   Википедия

  • ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ — формальный язык, распознаваемый машиной, множество всех тех слов, при работе над к рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек рой Тьюринга… …   Математическая энциклопедия

  • Видеонаблюдение — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Викифицировать статью …   Википедия

  • Портрет — Питер Пауль Рубенс. «Портрет камеристки инфанты Изабеллы» …   Википедия

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс ZPP — В теории вычислительной сложности, ZPP (zero error probabilistic polynomial time  безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам:… …   Википедия

  • ZPP — В теории вычислительной сложности, ZPP (zero error probabilistic polynomial time безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам: Она… …   Википедия

  • АДИАГНОСТИЧЕСКИЙ — (от греч. a отриц. част., и diagnosis различение). В медицине: не распознаваемый или трудно различаемый недуг. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. АДИАГНОСТИЧЕСКИЙ от греч. а, отриц. част., и diagnosis …   Словарь иностранных слов русского языка


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»