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

定義

編輯

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

M 上的可識別語言的家族指示為  

例子

編輯

如果 M 是在某個字母表  自由么半群  ,則家族  正則語言   的家族。