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

4 無回朔一義可解析性
定義4．1 設(shè)上長度為m的串。又設(shè)α→β是一個規(guī)則且β=xixi+1…xi+|β|-1(1≤i≤m)是η的子串，則稱α→β在位置i可逆用于η，且稱(α→β，i)是η的一個逆用項。
對于η中的所有逆用項可以從左到右排列，從而可得到一個序列(α1→β1,i1)，(α2→β2,i2)，…，(αn→βn,in)，注意其中可存在許多相同的逆用項，但序號不同。用RAS(η)來表示該序列，n稱為該序列的長度。
如果從η的第i個位置的逆用項逆向使用規(guī)則α→β推導(dǎo)出ξ，則說ξ是從η第i位直接逆推導(dǎo)出的，記為或簡寫為很明顯當(dāng)且僅當(dāng)
關(guān)系的自反傳遞閉包用表示。關(guān)系的定義類似于的定義。
定義4．2 設(shè)η是G的一個推導(dǎo)句型，且
如果對于任意j(1≤j≤m)存在唯一的ξ和唯一的n使
則稱η是無回朔一義可解析的。如果G的全部句型無回朔可一義解析，則稱G是無回朔一義可解析的。
定義4.3 任一0FG G是無回朔一義可解析的。
證明：用歸納法，一步可推導(dǎo)出的任意推導(dǎo)句型是無回朔一義可解析的。設(shè)k步推導(dǎo)出的句型是無回朔一義可解析的，則可證明k+1步推導(dǎo)出的句型無回朔一義可解析的。具體證明如下。基礎(chǔ)步：如果顯然η是無回朔一義可解析的。歸納步驟：設(shè)滿足是無回朔一義可解析的，即對任意的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文法規(guī)則的無重疊性，η的解析是由ηk的解析中某一步加入逆用(α→β,_)步構(gòu)成，即在使用(α→β,_)逆用項的前后解析均具有ηk的解析性質(zhì)，解析總步數(shù)加1，即

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

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

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

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