3.2请标识出下列Pascal程序段中的单词符号，并给出这些单词符号的属性值 function max():interger, return maximum of interger I and I begin if i>j then max:=i else max=i end. 单词符号单词种别 属性值 function Function(保留字) max 标识符 指向max的符号表入口的指针 圆括号) Identifier(标识符) 指向1的符号表入口的指针 Com(逗号) Identifier(标识符) 指向的符号表入口的指针 Colon(E号) interger Interger(保留字) Rpar(右圆括号) Semc0l0n(分号) Lbar(左大括号) Rhar右大括号 begin Begin(保留字)】 (保留字) Relational-OP(关系运算符) LT then Then(保留字)】 = Assign-OP(赋值号) else Es(保留字) End End(保留字) 补弃颗： 1:解释下面每个有限自动机识别的语言是什么？ (a) 0110 (72→(374一→*5) 一一 0,10,10,1 a∈0,1yAa≠0110} *(234一才5 a {a5mln≥0}
3.2 请标识出下列 Pascal 程序段中的单词符号,并给出这些单词符号的属性值. function max (i , j :interger ): interger; { return maximum of interger I and I } begin if i>j then max := i else max := j end; 单词符号 单词种别 属性值 function Function(保留字) － max Identifier(标识符) 指向 max 的符号表入口的指针 ( Lpar(左圆括号) － i Identifier(标识符) 指向 i 的符号表入口的指针 , Comma(逗号) － j Identifier(标识符) 指向 j 的符号表入口的指针 : Colon(冒号) － interger Interger(保留字) － ) Rpar(右圆括号) － ; Semicolon(分号) － { Lbar(左大括号) － } Rbar 右大括号 － begin Begin(保留字) － if If(保留字) — > Relational-OP(关系运算符) LT then Then(保留字) － := Assign-OP(赋值号) － else Else(保留字) － End End(保留字) － 补充题： 1：解释下面每个有限自动机识别的语言是什么? (a) 0,1 0110 4 a a a (b) 0 5 1 + a n n 0 1 1 0 (1) (2) (3) (4) (5) 1 0 0 1 (6) (7) (8) ((9)) 0,1 0,1 0,1 a a a a (1) ((2)) (3) (4) (5) a
p1f01010咸正规表达式：0*110101*0) 2:对于下列各语言，分别写出它们的正规表达式 (a)字母表{ab,c;上的串，其中第一个a先于第一个b (ac)alabc) (b)具有偶数个a的字母表{ab,c上的串 (bc)(a(blc)a(blc)) (@)0,1}上的串，该串看成二进制是4的倍数 (1j00 (d)不含有子串011的由0,1组成的符号串全体 1(011*00100*)*(10*1e) (心)带有偶数个0和奇数个1，由0、1组成的符号串全体 r1→(0(00)*1(11)*0(00)*11(11)*)* r2→(0011)*(01川10(0011)*(01100011))* r2r1 英文字母组成的符号串，要求符号串顺序包含五个元音 令Letter为除元音之外的英文字母 (Letter)*(Aja)(LetterlAja)*(EleX(LetterEle)*(Ii)(LetterIi)*(Olo)(LetterOlo)*(UluX(Let terlUlu)" 34给出接收下列在字母表0,1上的语言的DFA a)所有以00结尾的符号串的集合 b)所有具有3个0的符号串的集合 a(1)正规表达式(01*o0 (2)正规文法：S→B0:B→A0:A→A0Ae (3)构造DFA M=(《0,1,{q0,q1,q2,q0,{q2,6) 8(q0.0)=q1,8(g1,0)=q2,8(g2,0)=02 δ(q1,1)=q0,8(q2,1)=q0,6(q0,1)=q0
(c) * * * * 0 110 1,01 0 或正规表达式：0*1(10*1)|01*0))* 2： 对于下列各语言,分别写出它们的正规表达式. (a) 字母表{a,b,c}上的串,其中第一个 a 先于第一个 b ( ) ( ) * * a c a a b c (b) 具有偶数个 a 的字母表{a,b,c}上的串 ( ) ( ( ) ( ) ) * * * * b c a b c a b c (c) {0,1}上的串,该串看成二进制是 4 的倍数 (01) 00 * (d) 不含有子串 011 的由 0，1 组成的符号串全体 1*| (0|11*0)(0|100*)*(10*| ε ) (e) 带有偶数个 0 和奇数个 1，由 0、1 组成的符号串全体 r1→(0(00)*1(11)*0(00)*|1(11)*)* r2→(00|11)*((01|10)(00|11)*(01|10)(00|11)*)* r→r1r2 | r2r1 (f) 英文字母组成的符号串，要求符号串顺序包含五个元音 令 Letter 为除元音之外的英文字母 (Letter)*(A|a)(Letter|A|a)*(E|e)(Letter|E|e)*(I|i)(Letter|I|i)*(O|o)(Letter|O|o)*(U|u)(Let ter|U|u)* 3.4 给出接收下列在字母表{0,1}上的语言的 DFA a) 所有以 00 结尾的符号串的集合 b) 所有具有 3 个 0 的符号串的集合 解： a)(1) 正规表达式(0|1)*00 (2) 正规文法： S→B0；B→A0；A→A0|A1| ε (3) 构造 DFA M =({0,1}, {q0, q1, q2}, q0, {q2}, ) (q0, 0)=q1， (q1, 0)=q2， (q2, 0)=q2， (q1, 1)=q0， (q2, 1)=q0， (q0, 1)=q0， 1 0 (0) ((1)) (2) 0 1
状态转换图 b)构造DFA M=({0,1h.{AB.CDH.AD.6),其中： 6(A1)=A 8(A.0)=B ,6(B,1)=B,8(B,0)=C 0(C,1)=C,6(C,0)=D,8(D,1)=D 状态转换图： 心 补充题：构造等价于正规表达式的NFA, (a)ab(abba'b )a34b5) 一→(1t6rat7)6→（￥&9tt13) (10tt11)→12) o,《abbb)j (8)b 3.3描述下列表达式表示的语言 a)0(01)*0
状态转换图： b) 构造 DFA M＝({0,1},{A,B,C,D},A,D, )，其中： (A,1)=A， (A,0)= B ， (B,1)=B， (B,0)= C (C,1)=C， (C,0)= D， (D,1)=D 状态转换图： 补充题： 构造等价于正规表达式的 NFA. (a) ab (a bb)a b * (b) (( ) ( )) * * a b bb 3.3 描述下列表达式表示的语言 a) 0(0|1)*0 0 0 q0 q1 q2 0 1 1 1 0 0 0 A B C D 1 1 1 1 (2) a (3) (4) b (5) a (1) (6) a (7) (8) (9) b ((13)) (10) b (11) b (12) (4) a (3) (6) b (1) (2) (5) (10) (11) (7) b (8) b (9)
以0开头并且以0结尾，由0、1组成的符号串，长度大于等于2： b)(e101*y 由0、 1组成的所有符号串 c)(01)0(01)(01 由0、1组成的长度大于等于3的符号串，其中倒数第三位为0： d)0*10*10*10* 由0、】组成的符号串，其中包含而日只句含3个1： 00 )*(0110X001)*y 由0、1组成的符号串 其中0和1的个数均为偶数 3.9对于下列正规表达式构造非确定的有限自动机。并给出每个自动机在处理符号串 ababbab过程中的动作序列 a)(ab) 解：M=({a,b,{0,12,3,4,56,70,{7,其中 ò(0，e)=7 6(0,e)=1,8(1,e)=2,6(2,a=3,6(3.e)=6, 8(1.e=4,8(4.a=5,65.e)=6,86.e)=1 6(6.e)=7 动作序列：0,1,2,3.6.1,45.6,12,36,1,45,61,4,56,12,36,1,45,6,7 b)(a"lb) 解：M=({a,b},{0,1,2,3,4,5,6,7,89,10,11,0,{11,6},其中： 8(0.e)=118(0.2)=1, 6(1,e)=2,6(2.e)=3,6(2,e)=5,6(3,a=4,8(4,e)=3 6(4,e =5,6(5,e)=10,6(10,e)1 6(1,e)=6,d(6,e)=7,6(6,e)=9,6(7,b)=8,6(8e)=7 6(8,e)=9,6(9,e)=10,6(10,e)=11 动作序列：0,1,2,3,4,510,1,6,7,8910,12,34,5,10,1,6,7,8,910,1,6,7,89,10,1 23.4.5.10.1.6.7.89.10.11 c)((e la)b*)* 解：M=({a,b},{0,1,2,3,4,5,6,7,8,9,10,11,12,0,{12,6},其中 ò(0，e)=11ò(0，e)=1, 6(1,e)=2,6(2,e)=3,6(3.e)=6 6(1.2)=4,6(4.a)=5,6(5.2)=6, 6(6,e)=7,6(7,e)=8,6(7,e)=10,6(8,b)=9,δ(9.e)=8, e)=10, 5(10,e)=1 (10,e 八11 动作序列：01,4,5,67,89,10.14,5,67,89,8,9,10.1,4,56,7,8,9.10.1 d)(alb)"abb(a|b) 解：M=({ab,0,1,21},0,{12,8,其中： 80.2=78(0.2)=1, ,e 2,6(2,a)=3,6(3,e)=6 6(1,e)卢4,6(4，b)=5,6(5,e)=6,8(6,e)=1, 6(6,e)=7,6(7,e)=8,6(8,a)=9,6(9,e)=10,6(10,b)=11, 6(11,e)=12,6(12,b)=13,6(13,e)=14,8(14,e)=15,6(14,e)=21, δ(15.e)=16.δ(16.a=17,δ(17.e)=20
以 0 开头并且以 0 结尾，由 0、1 组成的符号串，长度大于等于 2； b) (( ε |0)1*)* 由 0、1 组成的所有符号串； c) (0|1)*0(0|1) (0|1) 由 0、1 组成的长度大于等于 3 的符号串，其中倒数第三位为 0； d) 0*10*10*10* 由 0、1 组成的符号串，其中包含而且只包含 3 个 1； e) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)* 由 0、1 组成的符号串，其中 0 和 1 的个数均为偶数。 3.9 对于下列正规表达式构造非确定的有限自动机。并给出每个自动机在处理符号串 ababbab 过程中的动作序列 。 a) (a|b)* 解：M＝({a,b}，{0,1,2,3,4,5,6,7,},0,{7}, }，其中： (0, ε )=7 (0, ε )=1， (1, ε )=2， (2,a)=3， (3, ε )=6， (1, ε )=4， (4,a)=5， (5, ε )=6， (6, ε )=1， (6, ε )=7 动作序列：0,1,2,3,6,1,4,5,6,1,2,3,6,1,4,5,6,1,4,5,6,1,2,3,6,1,4,5,6,7 b) (a*|b*)* 解：M＝({a,b}，{0,1,2,3,4,5,6,7,8,9,10,11},0,{11}, }，其中： (0, ε )=11 (0, ε )=1， (1, ε )=2， (2, ε )=3， (2, ε )=5， (3, a)=4， (4, ε )=3， (4, ε )=5， (5, ε )=10， (10, ε )=1， (1, ε )=6， (6, ε )=7， (6, ε )=9， (7,b)=8， (8, ε )=7， (8, ε )=9， (9, ε )=10, (10, ε )=11 动作序列： 0,1,2,3,4,5,10,1,6,7,8,9,10,1,2,3,4,5,10,1,6,7,8,9,10,1,6,7,8,9,10,1, 2,3,4,5,10,1, 6,7,8,9,10,11 c) (( ε |a)b*)* 解：M＝({a,b}，{0,1,2,3,4,5,6,7,8,9,10,11,12},0,{12}, }，其中： (0, ε )=11 (0, ε )=1， (1, ε )=2， (2, ε )=3， (3, ε )=6 (1,ε )=4， (4,a)=5， (5, ε )=6， (6, ε )=7， (7, ε )=8， (7, ε )=10， (8,b)=9， (9, ε )=8， (9, ε )=10， (10, ε )=1， (10, ε )=11 动作序列：0,1,4,5,6,7,8,9,10,1,4,5,6,7,8,9,8,9,10,1, 4,5,6,7,8,9,10,11 d) (a|b)*abb(a|b)* 解：M＝({a,b}，{0,1,.,21},0,{12}, }，其中： (0, ε )=7 (0, ε )=1， (1, ε )=2， (2,a)=3， (3, ε )=6 (1,ε )=4， (4,b)=5， (5, ε )=6， (6,ε )=1， (6, ε )=7， (7, ε )=8， (8,a)=9， (9, ε )=10， (10,b)=11， (11,ε )=12， (12, b)=13, (13,ε )=14， (14, ε )=15， (14, ε )=21， (15, ε )=16， (16,a)=17， (17, ε )=20
6(15,e)=18,6(18.b)=19,6(19.e)=20,6(20.e)=15, 动作序列0.12.3614567.89101,12131415,1617.20151819,2021 3.10转换练习3.9中的NFA为DFA,并给出每个DFA处理符号串ababbab的动作序列 a）(ab* 解：M=(abABC,AABC,6,其中 (A.a) 0(A,b)=( 6(B,a=B,6(B,b)=C,6(C,a=B,6(C,b)=0 动作序列：ABCBCCBC b)(a"lb")* 解：同 c)(ea)b*)* 解：同a) d)(ab)"abb(a|b) 解：M=({a,by,{A,B,C,D,E,FG,HI}A,{E,FG,H,I,8},其中： 6(Aa)=B,8(Ab)=C,6(B.a=B,6(C,a=B,8(C,b=C,8(B,b)=D. 6(D,a=B,6(D,b)=E,6(E,a=F,6(E,b)=G,6(F,a)=F,6(Fb)=H, 6(G.a动=F,6(G,b G,6(H,a)=f,6(H.b)=l,6(,a)= δ(0，b=G, 动作序 l. ABDBDEF 3.11把3.10得到的DFA最小化 解： a).b).c) M=(ab,{A,A{A,6其中： ò(Aa=A,O(Ab)=A dM=({a,b,{AB,C,D,A{D,6},其中： 8(Ab)=A,8(Aa)=B.8(B.a=B.δ(B.b)=C.8(C.a=B.8(C.b=D 6(D,a=D,6(D,b)=D 3.12说明下列正规表达式等价 a)(alb) b)(a*b*)* c)((8 la)b*)* 解：由3.川可知，三个正规表达式的最小状态DFA相同，从而三个正规表达式等价
(15, ε )=18， (18,b)=19， (19, ε )=20， (20, ε )=15， 动作序列:0,1,2,3,6,1,4,5,6,7,8,9,10,11,12,13,14,15,16,17,20,15,18,19,20,21 3.10 转换练习 3.9 中的 NFA 为 DFA，并给出每个 DFA 处理符号串 ababbab 的动作序列 a) (a|b)* 解：M＝({a,b}，{A,B,C},A,{A,B,C}, }，其中： (A,a)=B， (A,b)=C， (B,a)=B， (B,b)=C， (C,a)=B， (C,b)=C 动作序列：ABCBCCBC b) (a*|b*)* 解：同 a) c) (( ε |a)b*)* 解：同 a) d) (a|b)*abb(a|b)* 解：M＝({a,b}，{A,B,C,D,E,F,G,H,I},A,{ E,F,G,H,I }, }，其中： (A,a)=B， (A,b)=C， (B,a)=B， (C,a)=B， (C,b)=C， (B,b)=D， (D,a)=B， (D,b)=E， (E,a)=F， (E,b)=G， (F,a)=F， (F,b)=H， (G,a)=F， (G,b)=G， (H,a)=F， (H,b)=I， (I,a)=F， (I,b)=G， 动作序列：ABDBDEFH 3.11 把 3.10 得到的 DFA 最小化 解： a),b) ,c) M＝({a,b}，{A},A,{A} , }，其中： (A,a)=A， (A,b)=A d) M＝({a,b}，{A,B,C,D },A,{D}, }，其中： (A,b)=A， (A,a)=B， (B,a)=B， (B,b)=C， (C,a)=B， (C,b)=D (D,a)=D， (D,b)=D 3.12 说明下列正规表达式等价 a) (a|b)* b) (a*|b*)* c) (( ε |a)b*)* 解：由 3.11 可知，三个正规表达式的最小状态 DFA 相同，从而三个正规表达式等价