可識別語言
外觀
此條目沒有列出任何參考或來源。 (2019年3月13日) |
在數學和計算機科學中,可識別語言是可被有限狀態機識別的形式語言。等價的說,可識別語言是語法關係的商的家族為有限的的形式語言。
定義
[編輯]給定一個么半群 M,在 M 上的語言簡單的是子集 。這樣的語言被稱為在 M 上可識別的,如果有在 M 上的有限狀態機接受 L 作為輸入。在 M 上的有限狀態機簡單的是以 M 的元素作為輸入,接受或拒絕它們的有限自動機。
在 M 上的可識別語言的家族指示為 。
例子
[編輯]如果 M 是在某個字母表 上自由么半群 ,則家族 是正則語言 的家族。
![]() | 這是一篇與邏輯學相關的小作品。您可以透過編輯或修訂擴充其內容。 |