DOC《第三章习题解答》

s'

―― s \c――\c *――.* ?――. [s]――[s] (Aho)3.16 使用Thompson构造法为下列正规式构造NFA,写出每个NFA处理符号串ababbab过程中的状态转换序列 (a | b)* 解:NFA为ababbab状态转换序列: 0(1(2(4(6(1(3(5(6(1(2(4(6(1(3(5(6(1(3(5(6(1(2(4(6(1(3(5(6(7 (a* | b*)* 解:NFA为ababbab状态转换序列: 0(1(2(4(6(8(10(1(3(5(7(9(10(1(2(4(6(8(10(1(3(5(7(5(7(9(10(1(2(4(6(8(10(1(3(5(7(9(10(11 ((? | a)b*)* 解:NFA为ababbab状态转换序列: 0(1(3(5(6(7(8(9(1(3(5(6(7(8(7(8(9(1(3(5(6(7(8(9(10 (a | b)*abb(a | b)* 解:NFA为ababbab状态转换序列: 0(1(2(4(6(1(3(5(6(7(8(9(10(11(12(14(16(11(13(15(16(17 (Aho)3.17 利用子集构造法将3.16题得到的NFA转换为DFA,同样写出分析符号串ababbab过程中的状态转换. 解: ?-closure({0}) = { 0, 1, 2, 3,

7 } = A ?-closure(?(A, a)) = {1, 2, 3, 4, 6, 7} = B ?-closure(?(A, b)) = {1, 2, 3, 5, 6, 7} = C ?-closure(?(B, a)) = B ?-closure(?(B, b)) = C ?-closure(?(C, a)) = B ?-closure(?(C, b)) = C ababbab状态转换序列: A(B(C(B(C(C(B(C 解: ?-closure({0}) = { 0, 1, 2, 3, 4, 5, 8, 9, 10,

11 } = A ?-closure(?(A, a)) = {1, 2, 3, 4, 5, 6, 8, 9, 10,

11 } = B ?-closure(?(A, b)) = {1, 2, 3, 4, 5, 7, 8, 9, 10, 11} = C ?-closure(?(B, a)) = B ?-closure(?(B, b)) = C ?-closure(?(C, a)) = B ?-closure(?(C, b)) = C ababbab状态转换序列: A(B(C(B(C(C(B(C 解: ?-closure({0}) = { 0, 1, 2, 3, 4, 6, 7, 9,

10 } = A ?-closure(?(A, a)) = {1, 2, 3, 4, 5, 6, 7, 9,

10 } = B ?-closure(?(A, b)) = {1, 2, 3, 4, 6, 7, 8, 9, 10} = C ?-closure(?(B, a)) = B ?-closure(?(B, b)) = C ?-closure(?(C, a)) = B ?-closure(?(C, b)) = C ababbab状态转换序列: A(B(C(B(C(C(B(C 解: ?-closure({0}) = { 0, 1, 2, 3,

7 } = A ?-closure(?(A, a)) = {1, 2, 3, 4, 6, 7,

8 } = B ?-closure(?(A, b)) = {1, 2, 3, 5, 6,

7 } = C ?-closure(?(B, a)) = B ?-closure(?(B, b)) = {1, 2, 3, 5, 6, 7,

9 } = D ?-closure(?(C, a)) = B ?-closure(?(C, b)) = C ?-closure(?(D, a)) = B ?-closure(?(D, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13,

17 } = E ?-closure(?(E, a)) = {1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 16,

17 } = F ?-closure(?(E, b)) = {1, 2, 3, 5, 6, 7, 11, 12, 13, 15, 16, 17} = G ?-closure(?(F, a)) = F ?-closure(?(F, b)) = {1, 2, 3, 5, 6, 7, 9, 11, 12, 13, 15, 16,

17 } = H ?-closure(?(G, a)) = F ?-closure(?(G, b)) = G ?-closure(?(H, a)) = F ?-closure(?(H, b)) = {1, 2, 3, 5, 6, 7, 10, 11, 12, 13, 15, 16,

17 } = I ?-closure(?(I, a)) = F ?-closure(?(I, b)) = G ababbab状态转换序列: A(B(D(B(D(E(F(H (Aho)3.18 为3.16的正规式直接构造DFA,比较得到结果与3.17结果的状态数. 解: followpos

1 {1, 2, 3}

2 {1, 2, 3}

3 firstpos(root) = {1, 2, 3} = A ?(A, a) = followpos(1) = { 1, 2,

3 } = A ?(A, b) = followpos(1) = { 1, 2,

3 } = A 解: followpos

1 {1, 2, 3}

2 {1, 2, 3}

3 firstpos(root) = {1, 2, 3} = A ?(A, a) = followpos(1) = { 1, 2,

3 } = A ?(A, b) = followpos(1) = { 1, 2,

3 } = A 解: followpos

1 {1, 2, 3}

2 {1, 2, 3}

3 firstpos(root) = {1, 2, 3} = A ?(A, a) = followpos(1) = { 1, 2,

3 } = A ?(A, b) = followpos(1) = { 1, 2,

3 } = A 解: followpos

1 {1, 2, 3}

2 {1, 2, 3}

3 {4}

4 {5}

5 {6, 7, 8}

6 {6, 7, 8}

7 {6, 7, 8}

8 firstpos(root) = {1, 2, 3} = A ?(A, a) = followpos(1)∪followpos(3) = { 1, 2, 3,

4 } = B ?(A, b) = followpos(2) = A ?(B, a) = followpos(1)∪followpos(3) = B ?(B, b) = followpos(2)∪followpos(4) = { 1, 2, 3,

5 } = C ?(C, a) = followpos(1)∪followpos(3) = B ?(C, b) = followpos(2)∪followpos(5) = { 1, 2, 3, 6, 7, 8} = D ?(D, a) = followpos(1)∪followpos(3)∪followpos(6) = { 1, 2, 3, 4, 6, 7,