正规文法与有限自动机的等价性研究[].docVIP

精品论文 参考文献 正规文法与有限自动机的等价性研究[] 葛寒松，柴晓辉 （商丘师范学院计算机科学系，河南商丘 476000） 摘要：通过证明正规文法和有限自动机之间的等价性定理，给出正规文法和有限自动机之间的等价构造方法。 关键词：正规文法；有限自动机；等价性；构造方法 中图分类号：TP301.1 文献标识码：A 文章编号：1007-9599 (2010) 05-0000-02 Equivalent Study Between Regular Grammar and Finite Automata Ge Hansong,Chai Xiaohui (Department of Computer Science,Shangqiu Teachers College,Shangqiu 476000,China) Abstract:It gives the equivalent constitution method between the regular grammar and the finite automata by proving the theorem of equivalence between them. Keywords:Regular grammar;Finite automata;Equivalence;Structuring method 一、引言 在乔姆斯基的文法分类中，正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。 二、从正规文法到有限自动机 （一）正规文法到有限自动机的等价性证明 定理1：对于每一个右线性正规文法GR和左线性正规文法GL，都存在一个有限自动机M与之等价。 证明： 1.设右线性文法GR=（VT,VN,S,P），将VN中每个非终结符视为状态符号，并增加一个新的终止符号f，（fVN）。令M=(VN{f}，VT，d，S，{f})，其中状态转换函数d由以下规则定义：①若对某个AVN及aVT{epsilon;}，P中有产生式Ararr;a，则令d(A，a)=f；②对任意的AVN及aVT{epsilon;}，设P中左端为A右端第一个符号为a的所有产生式为Ararr;aA1∣aA2∣…∣aAk（不包括Ararr;a），则令d(A，a)={ A1，A2，…，Ak}。 显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该右线性文法对应，下面说明它们的等价性(L(GR)=L(M))。 对右线性正规文法GR，在SW的最左推导过程中，利用Ararr;aB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态B(包括a=epsilon;的情形)。在推导过程的最后，利用Ararr;a一次则相当于在Ｍ中从状态A出发经标记为a的箭弧到达终态f(包括a=epsilon;的情形)。综上所述，在正规文法GR中，SW的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，WL(GR)当且仅当WL(M)，故L(GR)=L(M)。 2.设左线性文法GL=（VT,VN,S,P），将VN中每个非终结符视为状态符号，并增加一个新的初始状态符号q，（qVN）。令M=(VN{q}，VT，d，q，{S})，其中状态转换函数d由以下规则定义： ①若对某个AVN及aVT{epsilon;}，P中有产生式Ararr;a，则令d(q，a)=A； ②对任意的AVN及aVT{epsilon;}，设P中所有右端第一个符号为A，第二个符号为a的所有产生式为A1rarr;Aa，A2rarr;Aa，…，AKrarr;Aa，则令d(A，a)={ A1，A2，…，Ak}。 显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该左线性文法对应，下面说明它们的等价性(L(GL)=L(M))。 对左线性正规文法GL，在SW的最左推导过程中，利用Brarr;Aa一次就相当于从状态A出发经标记为a的箭弧到达状态B(包括a=epsilon;的情形)。在推导的最后，利用Ararr;a一次则相当于在Ｍ中从状态q出发经标记为a的箭弧到达状态A(包括a=epsilon;的情形)。综上所述，在正规文法GL中，SW的充要条件是：在M中，从状态q到状态S有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，WL(GL)当且仅当WL(M)，故L(GL)=L(M)。 （二）正规文法到有限自动机的构造方法 上述定理的证明采用了构造性的证