第三章课后作业

第三章课后作业解析解题步骤：1.由正规式R构造NFA2.构造确定化后的DFA的状态矩阵(子集法)3.生成确定化后的DFA的状态转换图4.化简DFA3.1构造正规式相应的DFA(1)1(0|1)*101XY1(0|1)*101Ycde101Xa1(0|1)*Ycde101Xa1b10

由正规式构造NFAYcde101Xa1b10

Q’10A{X}{a,b,c}

B{a,b,c}{b,c,d}{b,c}C{b,c,d}{b,c,d}{b,c,e}D{b,c}{b,c,3}{b,c}E{b,c,e}{b,c,d,Y}{b,c}F{b,c,d,Y}{b,c,d}{b,c,e}

构造确定化后的DFA的状态矩阵BFDE010C11100A101Q’10A{X}{a,b,c}

B{a,b,c}{b,c,d}{b,c}C{b,c,d}{b,c,d}{b,c,e}D{b,c}{b,c,d}{b,c}E{b,c,e}{b,c,d,Y}{b,c}F{b,c,d,Y}{b,c,d}{b,c,e}根据状态矩阵写状态转换图BFDE01C11100A1010最小化DFA首先M的状态分成两组：终态组{F}，非终态组{A,B,C,D,E}考察{A,B,C,D,E}，由于{A,B,C,D,E}1

属于{B,C,F},

它既不包含在{A,B,C,D,E}中也不包含在{F}之中，因此，应把{A,B,C,D,E}一分为二。因为状态E经1弧到达状态F，而状态A、B,C,D经1弧都到达{B,C}，因此，应把E分出来，形成{A,B,C,D}、{E}、{F}。{A,B,C,D}0

属于{D,E},它不含在任何划分中，因为状态C经0弧到达状态E，而状态{A,B,D}经0弧都到达D，因此，应把C分出来，形成{A,B,D}、{C}、{E}、{F}。由于{A,B,D}1={B,C}，它不包含在任何划分之中，因此，应把{A,B,D}一分为二。因为状态B、D经1弧都到达{C}，经0弧都到达{D}因此，应把A分出来，形成{A}、{B,D}、{C}、{E}、{F}。{B,D}无法再分。

至此，整个分划含有四组：{A}、{B,D}、{C}、{E}、{F}

。每个组都不可再分。ABlllFEC00l0l0(2)(a|b)*(aa|bb)(a|b)*Y56

X1

2ba

34abbaba

由正规式构造NFAQ’abA{X,1,2}{1,3,2}{1,4,2}B{1,3,2}{1,5,3,2,6,Y}{1,4,2}C{1,5,3,2,6,Y}{1,5,3,6,2,Y}{1,4,6,2,Y}D{1,4,2}{1,3,2}{1,5,4,2,6,Y}E{1,4,6,2,Y}{1,6,3,2,Y}{1,5,6,4,2,Y}F{1,5,4,2,6,Y}{1,3,6,2,Y}{1,5,4,6,2,Y}G{1,6,3,2,Y}{1,6,5,3,2,Y}{1,6,4,2,Y}

构造确定化后的DFA的状态矩阵Y56

X1

2ba

34abbaba状态矩阵写状态转换图Q’abA{X,1,2}{1,3,2}B{1,4,2}DB{1,3,2}{1,5,3,2,6,Y}C{1,4,2}DC{1,5,3,2,6,Y}{1,5,3,6,2,Y}C{1,4,6,2,Y}ED{1,4,2}{1,3,2}B{1,5,4,2,6,Y}FE{1,4,6,2,Y}{1,6,3,2,Y}G{1,5,6,4,2,Y}FF{1,5,4,2,6,Y}{1,3,6,2,Y}G{1,5,4,6,2,Y}FG{1,6,3,2,Y}{1,6,5,3,2,Y}C{1,6,4,2,Y}EABaGDbbCaaEbaFbabaabb最小化DFA{A,B,D}{C,E,F,G}{A,B,D}a={B,C,B}->{A,D}{B}{A,D}b={D,F}->{A}{D}{C,E,F,G}a={C,G,G,E}{C,E,F,G}b={E,F,F,E}{A}{B}{D}{C,E,F,G}ABaGDbbCaaEbaFbabaabbABaDbbCaaabb(3)((0|1)*

|(11))*XYA(0|1)*1B

1XYA1B

1C

10

由正规式构造NFAQ’01S{X,A,C,Y}{A,C,Y}{A,B,C,Y}D{A,C,Y}{A,C,Y}{A,B,C,Y}E{A,B,C,Y}{A,C,Y}{A,B,C,Y}0101E01S10DS

构造确定化后的DFA的状态矩阵状态矩阵写状态转换图最小化DFA(4)(0|11*0)*XYA1B

001Q’01X{X,A,Y}{A,Y}{B}Y{A,Y}{A,Y}{B}B{B}{A,Y}{B}xB1001XYB0110013.2确定化和最小化a,baa01(a)Q’abA{0}{0,1}{1}B{0,1}{0,1}{1}C{1}{0}

baaACababaCAB5042a3ba1abaaabbbb(b)已经是确定化，对其最小化。{0,1},{2,3,4,5}{0,1}a={0,1}{0,1}b={2,4}{2,3,4,5}a={1,3,0,5}{0,1},{2,4},{3,5}{2,4}b={3,5}{3,5}b={2,4}baa02bb3a3.3构造DFA,接收{0，1}上所有满足每个1都有0直接跟在后面的字符串

(10|0)*XY1012

0Q’01A{X,1,Y}{1,Y}{2}B{1,Y}{1,Y}{2}C{2}{1,Y}

01010ABC100AC3.4给出文法G[S]，构造相应最小的DFA。S->aS|bA|bA->aSSADbbaaQ’abA{S}{S}{A,D}B{A,D}{S}

SBbaa3.5给出文法对应的正规式首先给出相应的正规式方程组（+代替|）

S=aA ………(1) A=bA+aB+b ………(2)

B=aA ………(3)将(3)代入(2)式得

A=(b+aa)A+b ………(4)对(4)使用规则得 A=(b|aa)*b带入(1)得正规文法所生成语言的正规式是 a(b|aa)*b SaAAbAaBb

BaA 3.6给出NFA等价的正规文法GG=({A,B,C,D},{a,b},P,A),其中P为：

AaBbD

BbC

CaAbDDaBbDABCbDaaabbb3.7给出与NFA等价的正规式R等价的正规式：R=（0|1）*11ABC110,1ABY110,1C

X

AY110|1C

X

Y(0|1)*11X3.8(1)等价文法L(G’):T→I|NI→A|B|C|IA|IB|IC|I1|I2|I3N→1|2|3|N1|N2|N3(2)有穷自动机:M=({S,I,N,T},{1,2,3,A,B,C},f,S,{T})f:f(S,A)=If(S,B)=If(S,C)=If(S,1)=Nf(S,2)=Nf(S,3)=Nf(I,A)=If(I,B)=If(I,C)=If(I,1)=If(I,2)=If(I,3)=If(I,ε)=Tf(N,1)=Nf(N,2)=Nf(N,3)=Nf(N,ε)=T<单词>T<标识符>I<整数>N3.9

试证明正规式(a|b)*与正规式(a*|b*)*是等价的。X1Y

a,b(a|b)*Ya,b(a*|b*)*YX1

23

a

bYa,b3.10给出文法对应的正规式首先给出相应的正规式方程组（+代替|）

S=0A+1B

………(1) A=1S+1 ………(2)

B=0S+0

………(3)将(2)(3)代入(1)式得

S=01S+01+10S+10 ………(4)对(4)使用规则得 S=(01|10)*(01|10)即正规文法所生成语言的正规式是 (01|10)*(01|10) S0A1BA1S1

B0S03.11R=b*ab（b|ab）*（1）

X1Y234abb

b

56abQ’abA{X,1,2}{3}{1