Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
348 lines (292 sloc) 5 KB

3.7 节的练习

3.7.1

将下图中的 NFA 转换成 DFA.

解答

1、

转换表

NFA状态 DFA状态 a b
{0,1,3} A B C
{2} B B
{4} C C

DFA

3 7 1-1

2、

转换表

NFA状态 DFA状态 a b
{0} A B A
{0,1} B C B
{0,1,2} C C D
{0,2,3} D C D

DFA

3 7 1-2

3、

转换表

NFA状态 DFA状态 a b
{0,1,2,3} A A A

DFA

3 7 1-3

3.7.2

用算法 3.22 模拟下图中的 NFA 在处理输入 aabb 时的过程。

解答

  1. -start->{0}-a->{0,1}-a->{0,1,2}-b->{0,2,3}-b->{0,2,3}
  2. -start->{0,1,2,3}-a->{0,1,2,3}-a->{0,1,2,3}-b->{0,1,2,3}-b->{0,1,2,3}

3.7.3

使用算法 3.23 和 3.20 将下列正则表达式转换成 DFA。

  1. (a|b)*
  2. (a*|b*)*
  3. ((ε|a)|b*)*
  4. (a|b)*abb(a|b)*

解答

1、

NFA

3 7 3-1-nfa

转换表

NFA状态 DFA状态 a b
{0,1,2,3,7} A B C
{1,2,3,4,6,7} B B C
{1,2,3,5,6,7} C B C

DFA

3 7 3-1-dfa

2、

NFA

3 7 3-2-nfa

转换表

NFA状态 DFA状态 a b
{0,1,2,3,4,5,8,9,10,11} A B C
{1,2,3,4,5,6,8,9,10,11} B B C
{1,2,3,4,5,7,8,9,10,11} C B C

DFA

3 7 3-2-dfa

3、

NFA

3 7 3-3-nfa

转换表

NFA状态 DFA状态 a b
{0,1,2,3,4,6,7,9,10} A B C
{1,2,3,4,5,6,7,9,10} B B C
{1,2,3,4,6,7,8,9,10} C B C

DFA

3 7 3-3-dfa

4、

NFA

3 7 3-4-nfa

转换表

NFA状态 DFA状态 a b
{0,1,2,4,7} A B C
{1,2,3,4,6,7,8} B B D
{1,2,4,5,6,7} C B C
{1,2,4,5,6,7,9} D B E
{1,2,4,5,6,7,10,11,12,14,17} E F G
{1,2,3,4,6,7,8,11,12,13,14,16,17} F F H
{1,2,4,5,6,7,11,12,13,15,16,17} G F G
{1,2,4,5,6,7,9,11,12,14,15,16,17} H F I
{1,2,4,5,6,7,10,11,12,14,15,16,17} I F G

DFA

3 7 3-4-dfa