查看“︁可识别语言”︁的源代码

{{unreferenced|time=2019-03-13T13:18:59+00:00}}
在[[数学]]和[[计算机科学]]中，'''可识别语言'''是可被[[有限状态机]]识别的[[形式语言]]。等价的说，可识别语言是[[语法关系]]的商的家族为有限的的形式语言。

==定义==
给定一个[[幺半群]] ''M''，在 ''M'' 上的'''语言'''简单的是子集 <math>L\subset M</math>。这样的语言被称为在 ''M'' 上'''可识别'''的，如果有在 ''M'' 上的有限状态机接受 ''L'' 作为输入。在 ''M'' 上的有限状态机简单的是以 ''M'' 的元素作为输入，接受或拒绝它们的有限自动机。

在 ''M'' 上的可识别语言的家族指示为 <math>REC(M)</math>。

==例子==
如果 ''M'' 是在某个[[字母表 (计算机科学)|字母表]] <math>\Sigma</math> 上[[自由幺半群]] <math>\Sigma^*</math>，则家族 <math>REC\left(\Sigma^*\right)</math> 是[[正则语言]] <math>REG\left(\Sigma^*\right)</math> 的家族。

{{logic-stub}}
[[Category:形式语言|K]]

[[en:Recognizable language]]