無重疊生成文法的一義可解析性及圖林等價性

2 定義
定義2．1一個無重疊生成文法(簡稱0FG)是一個系統(tǒng)式中：N和T分別是非終止符和終止符集合，S是啟始符，它是N的一個元素，$是限界符，它不屬于上面任何一個集合，P是重寫規(guī)則的集合，其中任一重寫規(guī)則具有：

這里α，β∈(N∪T)，α≠β，A∈N，且每個規(guī)則滿足下列條件：
重寫規(guī)則的左部至少有一個非終結(jié)符，其右部不能是$5，S$,$S$或S。
對任意兩個重寫規(guī)則r1=α1→β1和r2=α2→β2，應(yīng)滿足：①不存在δ，β′1,β'2∈(N∪T∪{$})+使得β1=β′1δ和β2=δβ′2，即β1和β2不能有任何相互重疊的部分；②如果存在γ，γ′∈(N∪T∪{$}){$})*使β1=γβ2γ'，則r1=r2。
令η∈{N∪T)+,α→β是P中的任意一個規(guī)則，如果存在γ，δ∈(N∪T∪{$})*，使得η=γaδ，則稱規(guī)則α→β可應(yīng)用于η。通過對η應(yīng)用規(guī)則α→β，可以得到ζ=γβδ,對此，稱在G中ζ可由應(yīng)用規(guī)則α→β從η直接推導(dǎo)而得，記為，或簡記為的自反傳遞閉包記為如果存在ξ1，ξ2，…，ξn-1使得，則記為在G為默認的情況下，分別簡記為
令η∈(N∪T)+，若為G中的一個推導(dǎo)句型，稱η為G中的一個句型。對于任一文法G，其生成的語言定義為：

定義2．2一個確定性圖靈機(簡稱DTM)是一個系統(tǒng)M：

式中：Q是狀態(tài)集合，∑是輸入符號的集合，Г帶符號集合，是一個移動函數(shù)，a0∈Г是一個空白符號，q0是初始狀態(tài)，qf是終止?fàn)顟B(tài)。
假設(shè)M具有一個向右無限的符號帶，M總是從符號帶的最左端位置以初始狀態(tài)開始移動讀寫頭，且讀寫頭右側(cè)永不存在不連續(xù)字符帶(圖林機在任何時候都不向連續(xù)字符帶的中間寫空白字符，只能在最右端寫空白字符)。這樣的假設(shè)并不影響M的通用性。
定義2.3設(shè)C是一類文法系統(tǒng)或一類圖靈機，L[C]表示該類系統(tǒng)所生成或接受的語言的集合，稱為C的語言類，即：
L[C]={L(G)|G∈C}

3 圖靈通用性
引理3．1 OFG所生產(chǎn)的語言類是DTM接受的語言類的子集，即

證明：很顯然，對任何一個0FG文法G均可以容易地構(gòu)造一個等價的Cllomsky O型文法G′，故O型文法]。而三L[Cllomsky 0型文法]=L[DMT]?；蚝唵蔚卣f，L[OFG]是遞歸可枚舉集的子集。
引理3．2 DTM接受的語言類是0FG所生產(chǎn)的語言類的子集，即：

證明：可以用0FG來模擬任一個確定的圖靈機的逆過程。不失一般性，假設(shè)圖靈機具有右無窮長帶，且在任何狀態(tài)下具有連續(xù)的字符序列，在任何時候都不向字符帶中段上寫空白字符。