跳至內容

可識別語言

維基百科,自由的百科全書

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

定義

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

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

例子

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