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

1 引言
高效率可解析文法是计算机科学及其应用领域内很基本和重要的研究课题。高效率可解析性意味着能够节省计算机的空间和时间。著名的LL(k)和LR(k)文法已被证明可无回溯地线性时间或线性空间解析。对于上下文自由文法CFL的一般解析算法是著名的CKY和Earley算法，两者的时间和空间复杂度分别都是0(n3)和0(n2)。等价于对称矩阵文法IAG(成员问题为NP完全问题，等价问题为不可决定问题)的UPAG(Unicluely Parsable Arrav Grammar)文法被证明可无回朔解析，其真子集可线性时间解析。在文献中讨论了一般短语结构生成文法的无回朔可一义解析性及其图灵等价性，定义了称为UPG(Uniquely arsable Gmmmar)的文法类，并证明了该类文法的无回朔一义可解析性及其图灵等价性。这里讨论一般短语结构生成文法的无回朔可一义解析性及其图灵等价性。首先定义一个称作OFG(Ovedap―Free Grammar)的生成文法系统，其对规则的限制条件比UPG的限制条件更强，但证明它仍然具有图灵通用性(与图灵机的等价性)和无回朔一义可解析性(无回溯无失败可解析)。最后讨论了OFG文法解析等问题。

2 定义
定义2．1一个无重叠生成文法(简称0FG)是一个系统式中：N和T分别是非终止符和终止符集合，S是启始符，它是N的一个元素，$是限界符，它不属于上面任何一个集合，P是重写规则的集合，其中任一重写规则具有：

这里α，β∈(N∪T)，α≠β，A∈N，且每个规则满足下列条件：
重写规则的左部至少有一个非终结符，其右部不能是$5，S$,$S$或S。
对任意两个重写规则r1=α1→β1和r2=α2→β2，应满足：①不存在δ，β′1,β'2∈(N∪T∪{$})+使得β1=β′1δ和β2=δβ′2，即β1和β2不能有任何相互重叠的部分；②如果存在γ，γ′∈(N∪T∪{$}){$})*使β1=γβ2γ'，则r1=r2。
令η∈{N∪T)+,α→β是P中的任意一个规则，如果存在γ，δ∈(N∪T∪{$})*，使得η=γaδ，则称规则α→β可应用于η。通过对η应用规则α→β，可以得到ζ=γβδ,对此，称在G中ζ可由应用规则α→β从η直接推导而得，记为，或简记为的自反传递闭包记为如果存在ξ1，ξ2，…，ξn-1使得，则记为在G为默认的情况下，分别简记为
令η∈(N∪T)+，若为G中的一个推导句型，称η为G中的一个句型。对于任一文法G，其生成的语言定义为：

定义2．2一个确定性图灵机(简称DTM)是一个系统M：

式中：Q是状态集合，∑是输入符号的集合，Г带符号集合，是一个移动函数，a0∈Г是一个空白符号，q0是初始状态，qf是终止状态。
假设M具有一个向右无限的符号带，M总是从符号带的最左端位置以初始状态开始移动读写头，且读写头右侧永不存在不连续字符带(图林机在任何时候都不向连续字符带的中间写空白字符，只能在最右端写空白字符)。这样的假设并不影响M的通用性。
定义2.3设C是一类文法系统或一类图灵机，L[C]表示该类系统所生成或接受的语言的集合，称为C的语言类，即：
L[C]={L(G)|G∈C}

3 图灵通用性
引理3．1 OFG所生产的语言类是DTM接受的语言类的子集，即

证明：很显然，对任何一个0FG文法G均可以容易地构造一个等价的Cllomsky O型文法G′，故O型文法]。而三L[Cllomsky 0型文法]=L[DMT]。或简单地说，L[OFG]是递归可枚举集的子集。
引理3．2 DTM接受的语言类是0FG所生产的语言类的子集，即：

证明：可以用0FG来模拟任一个确定的图灵机的逆过程。不失一般性，假设图灵机具有右无穷长带，且在任何状态下具有连续的字符序列，在任何时候都不向字符带中段上写空白字符。

依据上面的定义，文法G将逆向地来模拟确定的图灵机M的动作。如果M最终能接受一个带而停止，则一定存在一个G能模拟M。因此L(G)和L(M)相等。由于M的确定性，这样构造的G是满足OFG的规则要求的。故结论得证。

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，即