资源描述：
《正规文法与有限自动机的等价性研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、计算机光盘软件与应用2010年第5期ComputerCDSoftwareandApplications工程技术正规文法与有限自动机的等价性研究葛寒松，柴晓辉（商丘师范学院计算机科学系，河南商丘476000）摘要：通过证明正规文法和有限自动机之间的等价性定理，给出正规文法和有限自动机之间的等价构造方法。关键词：正规文法；有限自动机；等价性；构造方法中图分类号：TP301.1文献标识码：A文章编号：1007-9599（2010）05-0117-02EquivalentStudyBetweenRegularGrammarandFinite
2、AutomataGeHansong,ChaiXiaohui(DepartmentofComputerScience,ShangqiuTeachersCollege,Shangqiu476000,China)Abstract:Itgivestheequivalentconstitutionmethodbetweentheregulargrammarandthefiniteautomatabyprovingthetheoremofequivalencebetweenthem.Keywords:Regulargrammar;Finitea
3、utomata;Equivalence;Structuringmethod一、引言状态q出发经标记为a的箭弧到达状态A(包括a=ε的情形)。综+在乔姆斯基的文法分类中，正规文法包括左线性文法和右线上所述，在正规文法GL中，S⇒W的充要条件是：在M中，从状态性文法。由于正规文法和正规表达式在描述语言的能力上是等价q到状态S有一条通路，其上所有箭弧的标记符号依次连接起来的，而正规表达式和有限自动机在描述语言的能力上也是等价的，恰好等于W，这就是说，W∈L(GL)当且仅当W∈L(M)，故因此，正规文法和有限自动机之间也存在着等价性。通常，
4、对于L(GL)=L(M)。正规文法G和有限自动机M，G所定义的语言记作L(G)，M所能识（二）正规文法到有限自动机的构造方法别的语言记作L(M)，如果有L(G)=L(M),则称G和M是等价的。上述定理的证明采用了构造性的证明方法，由此可以得出由二、从正规文法到有限自动机正规文法到有限自动机的构造方法。（一）正规文法到有限自动机的等价性证明从右线性正规文法GR=(VT,VN,S,P)构造有限自动机定理1：对于每一个右线性正规文法GR和左线性正规文法GL，M=(VNU{f}，VT，δ，S，{f})的方法如下：都存在一个有限自动机M与之等
5、价。①将VN中每个符号视为一个状态符号，增加一个新的终态符证明：号f，f∉VN；1.设右线性文法GR=（VT,VN,S,P），将VN中每个非终结符视为②对于产生式A→a（a∈VTU{ε}），则构造δ(A，a)=f；状态符号，并增加一个新的终止符号f，（f∉VN）。令M=(VNU{f}，③对于产生式A→aA1（a∈VTU{ε}），则构造δ(A，a)=A1。VT，δ，S，{f})，其中状态转换函数δ由以下规则定义：①若对某从左线性正规文法GL=(VT,VN,S,P)构造有限自动机个A∈VN及a∈VTU{ε}，P中有产生式A→a，则令δ(
6、A，a)=f；M=(VNU{q}，VT，δ，q，{S})的方法如下：②对任意的A∈VN及a∈VTU{ε}，设P中左端为A右端第一个符①将VN中每个符号视为一个状态符号，增加一个新的初态符号为a的所有产生式为A→aA1∣aA2∣…∣aAk（不包括A→a），则号q，q∉VN；令δ(A，a)={A1，A2，…，Ak}。②对于产生式A→a（a∈VTU{ε}），则构造δ(q，a)=A；显然上述得到的M为一个NFA。到此，已说明存在一个FAM③对于产生式A1→Aa（a∈VTU{ε}），则构造δ(A，a)=A1。与该右线性文法对应，下面说明它们的
7、等价性(L(GR)=L(M))。三、从有限自动机到正规文法+对右线性正规文法GR，在S⇒W的最左推导过程中，利用A→（一）有限自动机到正规文法的等价性证明aB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态定理2：对于每一个有限自动机M，都存在一个右线性正规文B(包括a=ε的情形)。在推导过程的最后，利用A→a一次则相当法GR和左线性正规文法GL与之等价。于在Ｍ中从状态A出发经标记为a的箭弧到达终态f(包括a=ε的证明：+情形)。综上所述，在正规文法GR中，S⇒W的充要条件是：在M1.设DFAM=(S，∑，δ，S0，F)，分以
8、下两种情况进行证明：中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依（1）若S0∉F，则令GR=(∑,S,S0,P)，其中P是由以下规次连接起来恰好等于W，这就是说，W∈L(GR)当且仅当W∈L(M)，则定义的产生式集合，对任
