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

4 無回朔一義可解析性
定義4．1 設上長度為m的串。又設α→β是一個規則且β=xixi+1…xi+|β|-1(1≤i≤m)是η的子串，則稱α→β在位置i可逆用于η，且稱(α→β，i)是η的一個逆用項。
對于η中的所有逆用項可以從左到右排列，從而可得到一個序列(α1→β1,i1)，(α2→β2,i2)，…，(αn→βn,in)，注意其中可存在許多相同的逆用項，但序號不同。用RAS(η)來表示該序列，n稱為該序列的長度。
如果從η的第i個位置的逆用項逆向使用規則α→β推導出ξ，則說ξ是從η第i位直接逆推導出的，記為或簡寫為很明顯當且僅當
關系的自反傳遞閉包用表示。關系的定義類似于的定義。
定義4．2 設η是G的一個推導句型，且
如果對于任意j(1≤j≤m)存在唯一的ξ和唯一的n使
則稱η是無回朔一義可解析的。如果G的全部句型無回朔可一義解析，則稱G是無回朔一義可解析的。
定義4.3 任一0FG G是無回朔一義可解析的。
證明：用歸納法，一步可推導出的任意推導句型是無回朔一義可解析的。設k步推導出的句型是無回朔一義可解析的，則可證明k+1步推導出的句型無回朔一義可解析的。具體證明如下。基礎步：如果顯然η是無回朔一義可解析的。歸納步驟：設滿足是無回朔一義可解析的，即對任意的i，存在逆用項(αi→βi，ji)和唯一的ξk和n(ηk,i)使得
對滿足的任意η，存在且ξ是無回朔一義可解析的(回朔解析步為h)。很顯然，RAS(ξ)由RAS(ξ1)，(α→β，j)，RAS(ξ2)組成，且RAS(ξ1)和RAS(ξ2)均在RAS(ξ)中。η可能的解析如下：

(b)從RAS(ξ1)或RAS(ξ2)逆用項(αξ→βξ,i)開始，注意OFG文法規則的無重疊性，η的解析是由ηk的解析中某一步加入逆用(α→β,_)步構成，即在使用(α→β,_)逆用項的前后解析均具有ηk的解析性質，解析總步數加1，即

顯然，n+1和ηk對于iξ是唯一的。

無回朔一義可解析性表明．對于推導句型中的任意位置的逆用項可以在任何需要的時候應用它而不會改變解析的成功。任何解析步中出現的逆用項也可以被同時并行替換。

5 OFG的解析算法
根據定理4．1，可以直接得到如下異常簡單的解析算法，其對于OFG全集可無回朔一義解析。
算法5．1
(1)cw=$x$，x是一個被解析的字。
(2)if cw=$s$則成功解析并終止。
(3)隨機地在cw中找一逆用項(α→β,i)，且將其應用于
cw，這里α→β,∈P。如果無逆用項則解析失敗并終止。
(4)跳到(2)。
定理5．1 x在L(G)中當且僅當算法5．1終止并成功解析。
證明：由無回朔一義可解析性定理可證明。
算法中采用了隨機選擇的策略，也可以使用最左優先或任意的解析策略。

6 結論
根據上面的討論，0FG具有下列性質：
OFG具有通用性(與圖靈機等價性)(定理3．1)，
OFG具有一義可解析性(定理4．1)，
OFG存在十分簡單的解析算法(算法5．1)。
需要進一步討論的問題是能否找到有用的OFG文法子集，在該子集上實現更有效的解析。另一個問題是希望能找到CFG與0FG子集的轉換關系，因為CFG的簡明方便性，與CFG對應的OFG文法將有較廣泛的應用。