编译原理第2章习题课.docx

0 0 1.构造正规式的DFA。 化简后得: 化简后得: Q 1 0 {X} A (ABC} B {ABC} B (BCD} C {BC} D (BCD} C (BCD} C (BCE} E (BC} D (BCD} c (BC} D (BCE} E (BCDY} Y (BC} D (BCDY} Y {BCD} C (BCE} E (3) (3) (Olll^O) * 0 (2) (2) (a|b)?(a|bb) (a|b)? 2 2 NFA 化为 DFA： Q a b (X 1 2) (1 2 3) (1 2 4) (1 2 3) 11 2 3 5 Y (12 4) (1 2 4) 11 2 3] {1 2 4 5 Y| 11 2 3 5 Y} {1 2 3 5 Y| (1 2 4 5 Y} (1 2 3 Y} (1 2 4 5 Y} (1 2 4 Y} (1 2 3 Y} (1 2 4 5 Y} (1 2 3 Y} (1 2 3 5 Y} (1 2 4 ￥}  Q 1 0 (X A Y) X ；（ A {A Y} {B C D} A (C D} Y (A Y} B (A Y} B {B C D) A {A Y} (c 0} Y {C D} Y (A Y} B 2 .将下图确定化和最小化。 解：首先取A= €-CLOSURE({0}) = {0}. NFA确定化后的状态矩阵为: A B Q， a b 10) !0.1l {1} (0.1} 10.1) ⑴ c| {11 {0) 0 NFA确定化后的DFA为: 3.构造一个DFA,它接受￡={0, 1}上所有满足如下条件的字符串, 每个1都有。直接跟在后边。 解：按題意相应的正规表达式是0*(0 10)*0* 构造相应的DFA,首先构造NFA为 用子集法确定化 1 h. L s 0 1 (X.0.L3.Y} (O.1.3.Y) {2} 1 2 3 {O.13Y} {O.1.3.Y} ⑵ 2 2 3 ⑵ {1,3,Y} / 3 4 {1,3,Y} ⑵ 4 4 3 DFA为 4.给出NFA等价的正规式R。 方法一：首先将状态图转化为 匚~*E] 消去（D 得 0,1 匚―￡~消去其余结点 (0 1) *11 NFA等价的正规式为（0丨1） 11 方法二：NFA~*右线性文法一正规式 A-OAllAllB B—1C C-* e A=OA+1A+1B B=1 A=OA+1A+U A=(0+l)-ll—(OlDll 其最简DFA为(2)正规式 其最简DFA为 (2)正规式(a*|b*) ?的NFA为: 5.试证明正规式(a|b) ?与正规式(a |bB) ?是等价的。 证明： ⑴ 正規式(a|b)，的NFA为= a b {X, Ly} H.y} H.y) {l,y} {l,y} {l,y} DFA的状态转换表: a b {x.L2.3.y) (1.2.3.y} H.2.3,y} (l.2.3.y} (1.2.3.y} {1.2.3.y} 由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|b*)*o 6.设字母表￡={a,b},给出E上的正规式R=bab(b|ab)\ 试构造状态最小化的DFA M,使得L (M) =L (R)。 求右线性文法G,使L (G) =L (M). 解：⑴构造NFA： (2)将其化为DFA,转换矩阵为: Q a b (X.1.2) 1 2 (1.21 3 (3} 2 ° 0.5.Y} 4 11.21 3 {3} 2 (1.21 3 14.5.V 4 (6} 5 (5.YI ⑹ 5 0 (5.Y1 6 15.YI 6 (6} 5 (5.Y} ba52再将其最小化得: b a 5 2 再将其最小化得: (2)对应的右线性文法G= ({X,W,Y},{a,b},P,X) P： X—aW|bX W—bY|b y—aW|bY|b 3.8文法G［〈单词〉］为： 〈单词〉■〈标识符〉|〈整数》 〈标识符〉-〉〈标识符〉〈字母〉丨〈标识符〉〈数字〉丨〈字母〉 〈整数〉? (数字〉I〈整数〉〈数字》 (字母〉一〉A|B|C 《数字〉P1|2|3 (1)改写文法G为G，，使L(G )=L(G)o 2)给出相应的有穷自动机。 解：(1)令D代表单词，I代表标识符，Z代表整数，有G，(D)： D-1 | Z I-A | B | C | IA | IB | IC | II | 12 | 13 Z—1 | 2 | 3 | Zl | Z2 | Z3 (2)左线性文法G所对应的有穷自动机为： M=({S,D,I.Z), {1.2,3,A,B,C},f,S,(D}) f： f(S,A)=I, f(S,B)=L f(StC)=I f(S,l) f(I.A) f(Ll)