可识别语言

数学计算机科学中,可识别语言是可被有限状态机识别的形式语言。等价的说,可识别语言是语法关系的商的家族为有限的的形式语言。

定义

给定一个幺半群 M,在 M 上的语言简单的是子集  。这样的语言被称为在 M可识别的,如果有在 M 上的有限状态机接受 L 作为输入。在 M 上的有限状态机简单的是以 M 的元素作为输入,接受或拒绝它们的有限自动机。

M 上的可识别语言的家族指示为  

例子

如果 M 是在某个字母表  自由幺半群  ,则家族  正则语言   的家族。