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

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

葛寒松，柴晓辉

葛寒松，柴晓辉

（商丘师范学院计算机科学系，河南商丘476000）

摘要：通过证明正规文法和有限自动机之间的等价性定理，给出正规文法和有限自动机之间的等价构造方法。

关键词：正规文法；有限自动机；等价性；构造方法

中图分类号：TP301.1文献标识码：A文章编号：1007-9599(2010)05-0000-02

EquivalentStudyBetweenRegularGrammarandFiniteAutomata

GeHansong,ChaiXiaohui

(DepartmentofComputerScience,ShangqiuTeachersCollege,Shangqiu476000,China)

Abstract:Itgivestheequivalentconstitutionmethodbetweentheregulargrammarandthefiniteautomatabyprovingthetheoremofequivalencebetweenthem.

Keywords:Regulargrammar;Finiteautomata;Equivalence;Structuringmethod

一、引言

在乔姆斯基的文法分类中，正规文法包括左线性文法和右线性文法。由于正规文法和正规表达式在描述语言的能力上是等价的，而正规表达式和有限自动机在描述语言的能力上也是等价的，因此，正规文法和有限自动机之间也存在着等价性。通常，对于正规文法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{ε}，P中有产生式A→a，则令d(A，a)=f；②对任意的AVN及aVT{ε}，设P中左端为A右端第一个符号为a的所有产生式为A→aA1∣aA2∣…∣aAk（不包括A→a），则令d(A，a)={A1，A2，…，Ak}。

显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该右线性文法对应，下面说明它们的等价性(L(GR)=L(M))。

对右线性正规文法GR，在SW的最左推导过程中，利用A→aB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态B(包括a=ε的情形)。在推导过程的最后，利用A→a一次则相当于在Ｍ中从状态A出发经标记为a的箭弧到达终态f(包括a=ε的情形)。综上所述，在正规文法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{ε}，P中有产生式A→a，则令d(q，a)=A；

②对任意的AVN及aVT{ε}，设P中所有右端第一个符号为A，第二个符号为a的所有产生式为A1→Aa，A2→Aa，…，AK→Aa，则令d(A，a)={A1，A2，…，Ak}。

显然上述得到的M为一个NFA。到此，已说明存在一个FAM与该左线性文法对应，下面说明它们的等价性(L(GL)=L(M))。

对左线性正规文法GL，在SW的最左推导过程中，利用B→Aa一次就相当于从状态A出发经标记为a的箭弧到达状态B(包括a=ε的情形)。在推导的最后，利用A→a一次则相当于在Ｍ中从状态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})的方法如下：

①将VN中每个符号视为一个状态符号，增加一个新的终态符号f，fVN；

②对于产生式A→a（aVT{ε}），则构造d(A，a)=f；

③对于产生式A→aA1（aVT{ε}），则构造d(A，a)=A1。

从左线性正规文法GL=(VT,VN,S,P)构造有限自动机M=(VN

{q}，VT，d，q，{S})的方法如下：

①将VN中每个符号视为一个状态符号，增加一个新的初态符号q，qVN；

②对于产生式A→a（aVT{ε}），则构造d(q，a)=A；

③对于产生式A1→Aa（aVT{ε}），则构造d(A，a)=A1。

三、从有限自动机到正规文法

（一）有限自动机到正规文法的等价性证明

定理2：对于每一个有限自动机M，都存在一个右线性正规文法GR和左线性正规文法GL与之等价。

证明：

1.设DFAM=(S，∑，d，S0，F)，分以下两种情况进行证明：

（1）若S0F，则令GR=(∑,S,S0,P)，其中P是由以下规则定义的产生式集合，对任何a∑及A,BS，若d(A，a)=B，则：

①当BF时，令A→aB；

②当BF时，令A→aB∣a；

显然，上述得到的文法为一个右线性正规文法，下面说明它们的等价性(L(M)=L(GR))。

在DFAM中，对任何w∑*，不妨设w=a1a2…ak，其中ai∑(i=1,2,…,k)，若SW，则存在一个最左推导：S0a1A1a1a2A2…a1…aiAia1…aiai+1Ai+1…a1…ak，因而，在M中存在一条从S0出发一次经过A1，…，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1，…，ak。反之亦然。所以，wL(GR)当且仅当wL(M)，故L(M)=L(GR)。

（2）若S0F，因为d(S0,ε)=S0，所以εL(M)，但上面构造的L(GR)中不含ε。因此，需在文法中添加产生式S0→ε，这样，就有L(M)=L(GR)。

2.设DFAM=(S，∑，d，S0，F)，分以下两种情况进行证明：

（1）若S0F，则令GL=(∑,S,X,P)，其中XF，P是由以下规则定义的产生式集合，对任何a∑及A,BS，若d(A，a)=B，则：

①当A≠S0时，令B→Aa；

②当A=S0时，令B→a∣Aa；

显然，上述得到的文法为一个左线性正规文法，下面说明它们的等价性(L(M)=L(GL))。

在DFAM中，对任何w∑*，不妨设w=a1a2…ak，其中ai∑(i=1,2,…,k)，若存在一条从S0到X的通路，通路上所有箭弧的标记依次为a1，…，ak，则在GL中一定存在一个最左推导：XAkakAk-1ak-1ak…A2a2…ak…a1…ak，即wL(GL)。反之亦然。所以，wL(GL)当且仅当wL(M)，故L(M)=L(GL)。

（2）若S0F，则εL(M)，但上面构造的L(GL)中不含ε。因此，需在文法中添加产生式X→ε，这样，就有L(M)=L(GL)。

（二）有限自动机到正规文法的构造方法

上述定理的证明采用了构造性的证明方法，由此可以得出由有限自动机到正规文法的构造方法。

从有限自动机M=(S，∑，d，S0，F)构造右线性正规文法GR的方法如下：

令GR=(∑,S,S0，P)，其中P是由以下规则定义的产生式集合：

对任何d(A，a)=B,

①若BF，则令A→aB；

②若BF，并且B状态有箭弧射出，则令A→aB∣a；若BF，并且B状态没有箭弧射出，则令A→a；

③若S0F，则令S0→ε。

从有限自动机M=(S，∑，d，S0，F)构造左线性正规文法GL的方法如下：

令GL=(∑,S,X，P)，其中P是由以下规则定义的产生式集合：

对任何d(A，a)=B,

①若A不是初始状态，则令B→Aa；

②若A是初始状态，并且A状态有箭弧射入，则令B→Aa∣a；若A是初始状态，并且A状态没有箭弧射入，则令B→a；

③若S0F，则令X→ε。

四、结束语

有限自动机用于构造词法分析程序，正规文法用于构造语法分析程序，它们分别是语言的识别工具和定义工具，在构造高级程序设计语言的编译程序时占有举足轻重的地位。有限自动机作为语言词法的识别工具，必须能够识别由文法定义的所有词法范畴；而文法作为语言语法的定义工具，也必须有能力定义有限自动机能识别的所有词法范畴的规则。从这一意义上讲，有限自动机和正规文法在描述语言的能力上就存在着等价性，而由这些等价性推导出来的相互转换方法，在构造编译程序时具有一定的检测和指导作用。

参考文献：

[1]陈火旺等.程序设计语言编译原理(第3版)[M].北京:国防工业出版社,2000,1

[2]胡元义.编译原理教程（第二版）[M].西安:西安电子科技大学出版社,2006.5

[3]刘坚.编译原理基础[M].西安:西安电子科技大学出版社,2002,1

[4]吕映芝.编译原理[M].北京:清华大学出版社,1998,1

[5]胡元义等.编译原理课程辅导与习题解析[M].北京:人民邮电出版社,2002,7

作者简介：葛寒松（1978—），男，河南虞城人，商丘师范学院讲师，主要从事数据库理论和编译原理方面的研究与教学工作。