可識別語言

在數學和計算機科學中，可識別語言是可被有限狀態機識別的形式語言。等價的說，可識別語言是語法關係的商的家族為有限的的形式語言。

定義

給定一個么半群 M，在 M 上的語言簡單的是子集 $L\subset M$。這樣的語言被稱為在 M 上可識別的，如果有在 M 上的有限狀態機接受 L 作為輸入。在 M 上的有限狀態機簡單的是以 M 的元素作為輸入，接受或拒絕它們的有限自動機。

在 M 上的可識別語言的家族指示為 $REC(M)$。

例子

如果 M 是在某個字母表 $\Sigma$ 上自由么半群 $\Sigma ^{*}$，則家族 $REC\left(\Sigma ^{*}\right)$ 是正則語言 $REG\left(\Sigma ^{*}\right)$ 的家族。