正规文法与有限自动机的相互转换(2)

2.4正规式与有限自动机之间的转换

任意的正规式都可以转换为上述三种的表现形式。

在一个有限自动机转换为正规式时，就是考虑从初态到终态可以输入哪些数据到达。而这些数据可以用哪种正规式概括进来。

3系统设计

3.1从正规文法到有限自动机

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

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

证明：

1.设右线性文法GR=（VT,VN,S,P），将VN中每个非终结符视为状态符号，

6

并增加一个新的终止符号f，（f VN）。令M=(VN {f}，VT，d，S，{f})，其中状态转换函数d由以下规则定义：①若对某个A VN及a VT {ε}，P中有产生式A→a，则令d(A，a)=f；

②对任意的A VN及a VT {ε}，设P中左端为A右端第一个符号为a的所有产生式为A→aA1∣aA2∣?∣aAk（不包括A→a），则令d(A，a)={ A1，A2，?，Ak}。

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

对右线性正规文法GR，在S W的最左推导过程中，利用A→aB一次就相当于在M中从状态A出发经标记为a的箭弧到达状态B(包括a=ε的情形)。在推导过程的最后，利用A→a一次则相当于在Ｍ中从状态A出发经标记为a的箭弧到达终态f(包括a=ε的情形)。

综上所述，在正规文法GR中，S W的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于W，这就是说，W L(GR)当且仅当W L(M)，故L(GR)=L(M)。

2. 设左线性文法GL=（VT,VN,S,P），将VN中每个非终结符视为状态符号，并增加一个新的初始状态符号q，（q VN）。令M=(VN {q}，VT，d，q，{S})，其中状态转换函数d由以下规则定义：

①若对某个A VN及a VT {ε}，P中有产生式A→a，则令d(q，a)=A； ②对任意的A VN及a VT {ε}，设P中所有右端第一个符号为A，第二个符号为a的所有产生式为A1→Aa，A2→Aa，?，AK→Aa，则令d(A，a)={ A1，A2，?，Ak}。

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

对左线性正规文法GL，在S W的最左推导过程中，利用B→Aa一次就相当于从状态A出发经标记为a的箭弧到达状态B(包括a=ε的情形)。在推导的最后，利用A→a一次则相当于在Ｍ中从状态q出发经标记为a的箭弧到达状态A(包括a=ε的情形)。综上所述，在正规文法GL中，S W的充要条件是：在M中，从状态q到状态S有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于

7

W，这就是说，W L(GL)当且仅当W L(M)，故L(GL)=L(M)。 3.12 正规文法到有限自动机的构造方法

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

从右线性正规文法GR=(VT,VN,S,P)构造有限自动机M=( VN {f}，VT，d，S，{f})的方法如下：

①将VN中每个符号视为一个状态符号，增加一个新的终态符号f，f VN； ②对于产生式A→a（a VT {ε}），则构造d(A，a)=f； ③对于产生式A→aA1（a VT {ε}），则构造d(A，a)= A1。

从左线性正规文法GL=(VT,VN,S,P)构造有限自动机M=( VN {q}，VT，d，q，{S})的方法如下：

①将VN中每个符号视为一个状态符号，增加一个新的初态符号q，q VN； ②对于产生式A→a（a VT {ε}），则构造d(q，a)=A； ③对于产生式A1→Aa（a VT {ε}），则构造d(A，a)= A1。

3.2从有限自动机到正规文法

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

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

证明：

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

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

①当B F时，令A→aB； ②当B F时，令A→aB∣a；

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

在DFAM中，对任何w ∑*，不妨设w=a1a2?ak，其中ai ∑(i=1,2,?,k)，若S W，则存在一个最左推导：S0 a1A1 a1a2A2 ? a1?aiAi a1?aiai+1Ai+1 ?

8

a1?ak，因而，在M中存在一条从S0出发一次经过A1，?，Ak-1到达终态的通路，该通路上所有箭弧的标记依次为a1，?，ak。反之亦然。所以，w L(GR)当且仅当w L(M)，故L(M)=L(GR)。

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

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

（1）若S0 F，则令GL=(∑,S, X, P)，其中X F，P是由以下规则定义的产生式集合，对任何a ∑及A,B S，若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中一定存在一个最左推导：X Akak Ak-1ak-1ak ? A2a2?ak ? a1?ak，即w L(GL)。反之亦然。所以，w L(GL)当且仅当w L(M)，故L(M)=L(GL)。

（2）若S0 F，则ε L(M)，但上面构造的L(GL)中不含ε。因此，需在文法中添加产生式X→ε，这样，就有L(M)=L(GL)。 3.22 有限自动机到正规文法的构造方法

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

从有限自动机M=( S，∑，d，S0，F)构造右线性正规文法GR的方法如下： 令GR=(∑,S, S0，P)，其中P是由以下规则定义的产生式集合： 对任何d(A，a)=B, ①若B F，则令A→aB；

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

③若S0 F，则令S0→ε。

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

9

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

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

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

③若S0 F，则令X→ε。

4代码编写

#include using namespace std;

int main() {

int n, m;

//n为自动机状态的总数目 //m为自动机终结符的数目 int n_midd_stat, n_final_stat; //n_midd_stat为中间状态的数目 //n_final_stat为终态的数目

cout << \请输入自动机共有的状态数目：\ cin >> n;

char* stat = new char[n];

cout << \请输入开始状态：\ cin >> stat[0];

cout << \请输入中间状态的个数：\ cin >> n_midd_stat;

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库正规文法与有限自动机的相互转换(2)在线全文阅读。