-
遞歸可枚舉語言
鎖定
- 中文名
- 遞歸可枚舉語言
- 別 名
- 部分可判定語言
- 性 質
- 形式語言類型
- 領 域
- 計算機
目錄
遞歸可枚舉語言形式定義
遞歸可枚舉語言定義
遞歸可枚舉語言定義:設S⊆ Σ為一個語言,E是一個枚舉器,若L(E) =S,則稱E枚舉了語言S。若存在這樣 的E,S就稱為遞歸可枚舉語言。
注意,枚舉器E可以以任意的順序枚舉語言L(E),而且L(E) 中的某個串可能會被E多次重複地打印。
圖靈可識別語言定義:設
是一台圖靈機,若在輸入串
上
運行後可進入接受狀態並停機,則稱
接受串
。
所接受的所有字符串的集合稱為
所識別的語言,簡稱
的語言,記作
。
遞歸可枚舉語言兩個定義的等價性
下列定理揭示了遞歸可枚舉語言和圖靈可識別語言的聯繫。
定理:一個語言是圖靈可識別的,當且僅當它是遞歸可枚舉的。
證明:若有枚舉器E枚舉語言S,構造一個圖靈機M如下:
對於輸入ω
- 運行E,依次生成字符串s1,s2, ...;
- 若遇到某個si= ω則進入接受狀態並停機。
注意當ω ∉S時,M可能永不停機,但M所接受的語 言集合恰好是S,所以M識別了S。
假設我們有圖靈機M識別語言S,構造一個枚舉器E如下:
忽略輸入
- 對i= 1, 2, 3, ...重複下列步驟;
- 設Σ= {s1,s2, ...},分別將s1,s2, ... ,si作為M的輸入,模擬M執行i步;
- 若某個sj, 1 ≤ j ≤ i,在i步內可被M接受,則將其輸出。
遞歸可枚舉語言閉包性質
遞歸可枚舉語言在下列運算下是閉合的。就是説,如果L和P是兩個遞歸可枚舉語言,則下列語言也是遞歸可枚舉的:
L的Kleene星號:
L和P的串接:
並集:
交集:
遞歸可枚舉語言圖靈可識別語言與圖靈可判定語言的關係
注意圖靈可識別語言和圖靈可判定語言的區別:若
是圖靈可識別語言,則只需存在一台圖靈機
,當
的輸入
時,
一定會停機並進入接受狀態;當
的輸入
時,
可能停機並進入拒絕狀態,或者永不停機。而若
是圖靈可判定語言,則必須存在圖靈機
,使得對於任意輸入串
,
總能停機,並根據
屬於或不屬於
分別進入接受或拒絕狀態。
- 詞條統計
-
- 瀏覽次數:次
- 編輯次數:2次歷史版本
- 最近更新: 知百科行天下