构造正规式相应的DFA

正规式->最小化DFA说明整体的步骤是三步：一，先把正规式转换为NFA（非确定有穷自动机）,二，在把NFA通过“子集构造法”转化为DFA，三，在把DFA通过“分割法”进行最小化。

一步很简单，就是反复运用下图的规则，图1这样就能转换到NFA了。

给出一个例题，来自Google book。

本文主要根据这个例题来讲，图2二.子集构造法。

同样的例题，把转换好的NFA确定化，图3这个表是从NFA到DFA的时候必须要用到的。

第一列第一行I的意思是从NFA的起始节点经过任意个ε所能到达的结点集合。

Ia表示从该集合开始经过一个a所能到达的集合，经过一个a的意思是可以略过前后的ε。

同样Ib也就是经过一个b，可以略过前后任意个ε。

至于第二行以及后面的I是怎么确定的。

我参考了一些题目才明白，原来就是看上面的Ia和Ib哪个还没出现在I列，就拿下来进行运算，该列对应的Ia和Ib就是前面我说的那样推导。

如果还不太明白，看图就是了。

你会发现I中的几个项目都在Ia和Ib中出现了。

而且是完全出现这步做完以后，为了画出最后的DFA，那么肯定得标出一些号来，比如1.2.3.。

或者A。

B。

c，我一般标的方法是先把I列全部标上1.2.3.递增。

然后看1表示的集合和Ia和Ib中的哪个集合一样，就把那个集合也表示为1.继续向下做。

最后会得到这样一个表格。

图4至此，就可以表示出DFA了。

就对照上面那个表，从0节点开始经过a到1.经过b到2，就这样画就行了。

最后的DFA如下图，图5双圈的表示终态，这个是怎么来的呢。

去看看图4，会发现有些项之前有双圈标志，这个是因为在NFA 图2中，9为终态，所以所有包含9的集合都被认为是终态集，改成1.2.3.。

方便画节点后就需要把这些点作为终态了。

三.最小化，分割法。

FA的最小化就是寻求最小状态DFA最小状态DFA的含义:1.没有多余状态(死状态)除多余状态什么是多余状态？从这个状态没有通路到达终态；S1从开始状态出发，任何输入串也不能到达的那个状态。

第四章词法分析1．构造下列正规式相应的DFA：(1)1(0|1) * 101(2)1(1010* | 1(010) * 1)* 0(3)a((a|b) * |ab * a)* b(4)b((ab)* | bb) * ab解：(1)1(0|1) * 101 对应的 NFA为1101012341下表由子集法将NFA 转换为 DFA：I I0=ε-closure(MoveTo(I,0))I1=ε-closure(MoveTo(I,1))A[0]B[1]B[1]B[1]C[1,2]C[1,2]D[1,3]C[1,2]D[1,3]B[1]E[1,4]E[1,4]B[1]B[1]001101A B C D E110,1(2)1(1010 * | 1(010) * 1)* 0 对应的 NFA 为εε1101010 01234561εε101978ε下表由子集法将NFA 转换为 DFA：I I=ε-closure(MoveTo(I,0))I1= ε-closure(MoveTo(I,1))A[0]B[1,6]B[1,6]C[10]D[2,5,7]C[10]D[2,5,7]E[3,8]B[1,6]E[3,8]F[1,4,6,9] F[1,4,6,9]G[1,2,5,6,9,10]D[2,5,7]G[1,2,5,6,9,10]H[1,3,6,9,10]I[1,2,5,6,7] H[1,3,6,9,10]J[1,6,9,10]K[2,4,5,7] I[1,2,5,6,7]L[3,8,10]I[1,2,5,6,7] J[1,6,9,10]J[1,6,9,10]D[2,5,7]K[2,4,5,7]M[2,3,5,8]B[1,6]L[3,8,10]F[1,4,6,9] M[2,3,5,8]N[3]F[1,4,6,9] N[3]O[4]O[4]P[2,5]P[2,5]N[3]B[1,6]1L111111010B I KA D E F M00110 00C11G H J101NP O(3)a((a|b) * |ab * a)* b(略 )(4)b((ab) * | bb) * ab(略 )2．已知 NFA=（ {x,y,z},{0,1},M,{x},{z} ）其中：M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)=φ ,M(z,1)={y},构造相应的 DFA。

二义性的含义: 如果文法存在某个句子对应两棵以上
不同的语法树，或者两种以上不同的最 左/右推导，则称这个文法是二义的。
首先：找到此文法对应的一个句子 iiiei 其次：构造与之对应的两棵语法树
S
S
i SeS
iS
iS
i
i S eS
i
ii
结论：因为该文法存在句子iiiei对应两棵 不同的语法树，因而该文法是二义的。
思路：先写出满足条件的正规式，由正规式构造 NFA，再把NFA确定化和最小化。
满足条件的正规式：(0|10)*
(0|10)*
x
y
1
0
1
0
0
1
2
0
x 1
y
编译原理
确定化： 给状态编号：
0
1
2
0
x 1
{X,1,Y} {1,Y} {2}
0
{1,Y} {1,Y} {1,Y}
0
0
1
1
1
2
1
chapter1~5习题
（1）{0,1}上的含有子串010的所有串。 正规式：(0 | 1)* 010 (0 | 1)*
（2） {0,1}上不含子串010的所有串。 正规式：1*(0|11*1)* 1*( 0 | 11)*1* 1*0*1* (0 | 11)*(0 | 1) DFA做法同第7题。
编译原理
chapter1~5习题
编译原理
chapter1~5习题
8、给出下面正规表达式 （5）沒有重複出現的數字的數字符號串的全體
令ri=i| ,i=0,1,2...9 R0|R1|R2|...|R9記為∑Ri i (0,1,2...,9) P（0,1,2...,9)表示0,1,2...,9的全排列

注意：本题应该理解为对图(a)进行确定化和对图(b)进行最小化。提供的答案没有对图(a)确 定化。
盛威网（）专业的计算机学习网站 14
《编译原理》课后习题答案第四章
第5题 构造一个 DFA，它接收 Σ={0,1}上所有满足如下条件的字符串：每个 1 都有 0 直接跟在 右边。并给出该语言的正规式。 答案： 按题意相应的正规表达式是(0*10)*0*， 或 0*(0 | 10)*0* 构造相应的 DFA， 首先构造 NFA 为
7
《编译原理》课后习题答案第四章
注意：这个题，也可以这样构造 NFA（用最少的ε，但注意不能出错） ：
a,b 0 a a 2 a,b 1 a b 3
盛威网（）专业的计算机学习网站
8
《编译原理》课后习题答 ε X b A ε F B a C b ε b G b H ε ε D ε E a I b Y
除 X，A 外，重新命名其他状态，令 AB 为 B、AC 为 C、ABY 为 D，因为 D 含有 Y（NFA 的终态），所以 D 为终态。 . X A B C D DFA 的状态图：: 0 . A C A C 1 A B B D B
(2)先构造 NFA： 0 ε X 1 A ε ε F B 1 C 1 0 ε 0 D 1 E 1 0 ε 用子集法将 NFA 确定化 ε X T0=X A T1= ABFL Y CG T2= Y T3= CGJ DH K T4= DH EI T5= ABFKL T6= ABEFIL EJY T7= ABEFGJLY EHY CGK T8= ABEFHLY EY CGI T9= ABCFGJKL DHY T10= ABEFLY T11= CGJI DHJ T12= DHY T13= DHJ EIK T14= ABEFIKL ABEFIKL EJY CG DHJ ？正确 DHJG EI EIK DHY EY DHJ CG K ABEFLY CGJI DHY CGK ABEFHLY ABCFGJKL EY CGI ABEFGJLY EHY CGK ABEFIL Y EJY CG CG DH ABFKL EI DH K Y CGJ ABFL Y CG X A 0 1 1 ε L ε K ε J 0 Y