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

• Язык, распознаваемый машиной Тьюринга (распознаваемый по Тьюрингу язык) — разрешимый язык.
• Язык, распознаваемый недетерминированной машиной Тьюринга — перечислимый язык.
• Язык, распознаваемый конечным автоматом — регулярный язык.
  • Распознаваемое подмножество моноида — обобщения понятия регулярного языка.