无重叠生成文法的一义可解析性及图林等价性

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文法将有较广泛的应用。