正规文法与有限自动机的等价性|编译原理

对于正规文法G和有限自动机M，如果L（G）=L（M），则称G和M是等价的。关于正规文法和有限自动机的等价性，体现在以下两个方面：

（1）对任一右线性或左线性正规文法G，都存在一个有限自动机M，使得L（M）=L（G）；

（2）对任一有限自动机M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L（M）=L（GR）=L（GL）。

1.正规文法转换为有限自动机

已知正规文法（右线性）GR=（VT，VN，S，P），令NFA M=（Q，Σ，δ，S，F），根据正规文法的4个部分求NFA的5个部分的方法是：

（1）输入字母表Σ，为文法终结符号集合VT；

（2）初始状态S，为开始符号S；

（3）状态集合Q：增加一个终态T，将Q=T∪VN作为状态集合；

（4）终态集合F：若P中含有产生式S→ε，则F={T，S}，否则，F={T}；

（5）状态转换函数δ的构造方法：

·对P中的产生式A→aB，δ（A，a）=B，画从A到B的弧，弧上标记a；

·对P中的产生式A→a，δ（A，a）=T，画从A到T的弧，弧上标记a；

·对于VT中的每个a，δ（T，a）=φ，表示在终态下没有动作。

例3.6 假设右线性正规文法GR=（{0，1}，{A，B，C，D}，A，P），其中，P为：

A→0|0B|1D B→0D|1C

C→0|0B|1D D→0D|1D

如图3-13所示，可以得到与之等价的有限自动机M=（{T，A，B，C，D}，{0，1}，δ，A，{T}），δ可由图得到。(www.xing528.com)

图3-13　由GR得到的有限自动机

2.有限自动机转换为正规文法

已知NFA M=（Q，Σ，δ，S0，F），求等价的右线性正规文法GR=（VT，VN，S，P），也就是说，根据NFA的5个部分求正规文法的4个部分，其方法是：

（1）终结符号集合VT，为字母表Σ；

（2）开始符号S，为初始状态S0；

（3）非终结符集合VN，为有限自动机的状态集合Q；

（4）产生式P的构造方法：对任何a∈Σ，A，B∈Q，若有δ（A，a）=B，则

·当B∉F时，令A→aB；

·当B∈F时，令A→a|aB；

·当S0∈F时，令S0→ε。

例3.7 给定如图3-14所示的有限自动机M=（{A，B，C，D}，{0，1}，δ，A，{B}），于是可以得到与之等价的右线性正规文法GR=（VT，VN，A，P），其中，VT={0，1}，VN={A，B，C，D}，P为：

图3-14　给定的有限自动机

A→0|0B|1D B→0D|1C

C→0|0B|1D D→0D|1D