无重叠生成文法的一义可解析性及图林等价性
高效率可解析文法是计算机科学及其应用领域内很基本和重要的研究课题。高效率可解析性意味着能够节省计算机的空间和时间。著名的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来模拟任一个确定的图灵机的逆过程。不失一般性，假设图灵机具有右无穷长带，且在任何状态下具有连续的字符序列，在任何时候都不向字符带中段上写空白字符。
评论