第四章 词法分析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 为下表由子集法将NFA 转换为DFA ：(2)1(1010*| 1(010)*1)*0对应的NFA 为 10,1下表由子集法将NFA转换为DFA：(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 。

解：根据题意有NFA 图如下下表由子集法将NFA 转换为DFA ：0，1下面将该DFA最小化：(1)首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}(2)区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。

由于F(B,0)=F(C,0)=C,F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。

有P21={C,F},P22={B}。

(3)区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。

(4)由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。

(5)综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。

所以最小化的DFA如下：3.将图确定化：1101111解：下表由子集法将NFA 转换为DFA ：4.把图的(a)和(b)分别确定化和最小化：(a) (b)解： (a):下表由子集法将NFA 转换为DFA ：0，1a可得图（a1），由于F(A,b)=F(B,b)=C,并且F(A,a)=F(B,a)=B,所以A,B 等价，可将DFA 最小化，即：删除B ，将原来引向B 的引线引向与其等价的状态A ，有图(a2)。

（DFA 的最小化，也可看作将上表中的B 全部替换为A ，然后删除B 所在的行。

）（a1）确定化的DFA （a2）最小化的DFA（b ）:该图已经是DFA 。

下面将该DFA 最小化：(6) 首先将它的状态集分成两个子集：P 1={0},P 2={1,2,3,4,5}(7) 区分P 2：由于F(4,a)=0属于终态集，而其他状态输入a 后都是非终态集，所以区分P 2如下：P 21={4},P 22={1,2,3,5}。

(8) 区分P 22:由于F(1,b)=F(5,b)=4属于P 21,而F(2,b)与F(3,b)不等于4,即不属于P 21，所以区分P 22如下：P 221={1,5},P 222={2,3}。

(9) 区分P 221:由于F(1,b)=F(5,b)=4,即F(1,a)=1,F(5,a)=5,所以1,5等价。

(10) 区分P 222:由于F(2,a)=1属于P 221，而F(3,a)=3属于P222,所以2，3可区分。

P 222区分为P 2221{2}，P 2222{3}。

(11)结论：该DFA 的状态集可分为：P={ {0},{1,5},{2},{3},{4} },其中1,5等价。

删去状态5，将原来引向5的引线引向与其等价的状态1，有图(b1)。

aa(b1)最小化的DFA5．构造一个DFA ，它接收Σ={0，1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。

然后再构造该语言的正则文法。

解：根据题意，DFA 所对应的正规式应为：(0|(10))*。

所以，接收该串的NFA 如下：下表由子集法将NFA 转换为DFA ：II 0 = ε-closure(MoveTo(I,0))I 1 =ε-closure(MoveTo(I,1))A[0] B[0,2] C[1] B[0,2] B[0,2] C[1] C[1] B[0,2]显然，A ，B 等价，所以将上述DFA 最小化后有：对应的正规文法为： G[A]：A 1C|0A |ε C0A1120 εAC 1B1AC1 0θ=dd *|dd *.dd *|.dd *|dd *e(s|ε)dd *|e(s|ε)dd *|.dd *e(s|ε)dd *|dd *.dd *e(s|ε)dd *化简θ,画出θ的DFA ，其中d={0,1,2,…9},s={+,-}解：把原正规式的每2，3项，4，5项，6，7项分别合并后化简有：θ=dd *|d *.dd *|d *e(s|ε)dd *|d *.dd *e(s|ε)dd *=dd *|d *.dd *|(d *|d *.dd *)e(s|ε)dd *=(ε|d *.|(d *|d *.dd *)e(s|ε))dd*=(ε|d *.|d *(ε|.dd *)e(s|ε))dd*下面构造化简后的θ对应的NFA ：下表由子集法将NFA 转换为DFA ：7．给文法G[S]： S aA|bQ A aA|bB|b B bD|aQ Q aQ|bD|b D bB|aA E aB|bFFbD|aE|b构造相应的最小的DFA 。

解：由于从S 出发任何输入串都不能到达状态E 和F ，所以，状态E ，F 为多余的状态，不予考虑。

这样，可以写出文法G[S]对应的NFA ：下表由子集法将NFA 转换为DFA ：II a = ε-closure(MoveTo(I,a)) I b =ε-closure(MoveTo(I,b))ED.ddCGdBd.Ae esFd d da Z SADQ Bbbbaba bbbaa由上表可知：(1)因为4，5是DFA的终态，其他是非终态，可将状态集分成两个子集：P1={1，2，3，6，7}，P2={4，5}(2)在P1中因为2,3输入b后是终态，而1，6，7输入b后是非终态，所以P1可区分为：P11={1，6，7}，P12={2，3}(3)在P11中由于1输入b后为3，6输入b后为7，而3，7分属P11和P12，所以1与6不等价，同理，1与7不等价。

所以P11可区分为：P111={1}，P112={6，7}(4)查看P112={6，7}，由于输入a后为2，3，所以6，7是否等价由2，3是否等价决定。

(5)查看P12={2，3}，由于输入b后为4，5，所以2，3是否等价由4，5是否等价决定。

(6)查看P2={4，5} ，显然4，5是否等价由2，3与6，7是否同时等价决定。

由于有（4）即6，7是否等价由2，3是否等价决定，所以，4，5是否等价由2，3是否等价决定。

由于有（5）即2，3是否等价由4，5是否等价决定，所以有4，5等价，2，3等价,进而6，7也等价。

(7)删除上表中的第3，5，7行，并将剩余行中的3，5，7分别改为对应的等价状态为2，4，6有下表：这样可得最小化的DFA 如下：8．给出下述文法所对应的正规式： S 0A|1B A 1S|1B0S|0解：把后两个产生式代入第一个产生式有： S=01|01S S=10|10S有:S=01S|10S|01|10=(01|10)S|(01|10)=(01|10)*(01|10)即:(01|10)*(01|10)为所求的正规式。

9．将图的DFA 最小化，并用正规式描述它所识别的语言：图解：(1) 因为6，7是DFA 的终态，其他是非终态，可将状态集分成两个子集：P1={1，2，3，4，5}，P2={6，a6 2 b aa 1babba72bcbdb1 34c 6aabbd5b47}。

(2) 由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。

(3) 由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等价，所以3,4等价。

(1) 由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2等价。

(2) 由于状态5没有输入字符b,所以与1，2，3，4都不等价。

(3) 综上所述，上图DFA 的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。

该DFA 用正规式表示为：b *a(c|da)*bb *10．构造下述文法G[S]的自动机： S A0 AA0|S1|0该自动机是确定的吗若不确定，则对它确定化。

该自动机相应的语言是什么解：由于该文法的产生式SA0，AA0|S1中没有字符集V T 的输入，所以不是确定的自动机。

要将其他确定化，必须先用代入法得到它对应的正规式。

把S A0代入产生式AS1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。

代入S A0有该文法的正规式：0(0|01)*0，所以，改写该文法为确定的自动机为：由于状态A 有3次输入0的重复输入，所以上图只是NFA ，下面将它确定化：下表由子集法将NFA 转换为DFA ：II 0 = ε-closure(MoveTo(I,0))I b =ε-closure(MoveTo(I,1))abb13c 6bd5aWX0 ZY1由上表可知DFA为：1。