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

《正规文法与有限自动机的等价性研究[]》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、正规文法与有限自动机的等价性研究[]葛寒松，柴晓辉(商丘师范学院计算机科学系，河南商丘476000)摘要：通过证明正规文法和有限自动机之间的等价性定理，给出正规文法和有限自动机之间的等价构造方法。关键词：正规文法；有限自动机；等价性；构造方法中图分类号：TP301.1文献标识码：A文章编号：1007-9599(2010)05-0000-02EquivalentStudyBetweenRegularGrammarandFiniteAutomataGeHansong,ChaiXiaohui(DepartmentofComputerScience,ShangqiuTeacher

2、sCollege,Shangqiu476000,China)AbstractJtgivestheequivalentconstitutionmethodbetweentheregulargrammarandthefiniteautomatabyprovingthetheoremofequivalencebetweenthem.Keywords:Regulargrammar;Finiteautomata;Equivalence;Structuringmethod一、引言在乔姆斯基的文法分类中，正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等

3、价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法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）o令M=（VN｛f｝，VT,d，S，｛f｝）,其中状态转

4、换函数d由以下规则定义：①若对某个AVN及aVT｛ε｝，P中有产生式A→a，则令d（A，a）=f；②对任意的AVN及aVT｛ε｝，设P中左端为A右端第一个符号为a的所有产生式为A→aAlIaA2

5、…

6、aAk（不包括A→a），则令d（A,a）=｛Al,A2,…,Ak｝。显然上述得到的M为一个NFA。到此，己说明存在一个FAM与该右线性文法对应，下面说明它们的等价性（L（GR）=L（M）＞。对右线性正规文法GR，在SW的最左推导过程中，利用A→aB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态B（

7、包括a=ε的情形）。在推导过程的最后，利用A→a一次则相当于在M中从状态A出发经标记为a的箭弧到达终态f（包括a=ε的情形）。综上所述，在正规文法GR中，SW的充要条件是：在M中，从状态S到状态f有一条通路，艽上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，WL（GR）当且仅当WL（M）,故L（GR）=L（M）O2.设左线性文法GL=（VT,VN,S,P）,将VN中每个非终结符视为状态符号，并增加一个新的初始状态符号q，（qVN）o令M=（VN｛q｝，VT，d,q，⑸）,其中状态转换函数d由以下规则定义：①若对某个AVN及a

8、VT｛ε｝，P中有产生式A→a，则令d（q，a）=A；②对任意的AVN及aVT｛ε｝，设P中所有右端第一个符号为A，第二个符号为a的所有产生式为Al→Aa，A2→Aa，…，AK→Aa，则令d（A，a）=｛A1，A2,…，Ak｝。显然上述得到的M为一个NFA。到此，己说明存在一个FAM与该左线性文法对应，下面说明它们的等价性（L（GL）=L（M））。对左线性正规文法GL，在SW的最左推导过程中，利用B&nmAa—次就相当于从状态A出发经标记为a的箭弧到达状态B（包括a=ε的情形）。在推导

9、的最后，利用A→a一次则相当于在M中从状态q出发经标记为a的箭弧到达状态A（包括a=ε的情形）。综上所述，在正规文法GL中，SW的充要条件是：在M中，从状态q到状态S有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，WL(GL)当且仅当WL(M),故L(GL)=L(M)。(二)正规文法到冇限自动机的构造方法上述定理的证明采用了构造性的证明方法，由此可以得出由正规文法到有限自动机的构造方法。从右线性正规文法GR=(VT,VN,S,P)构造冇限自动机M=(VN{f}，VT，d，S,{f}