Compilers Principles, Techniques, & Tools (purple dragon book) second edition exercise answers

Exercises for Section 3.7

3.7.1

Convert to DFA's the NFA's of:

  1. Fig. 3.26.
  2. Fig. 3.29.
  3. Fig. 3.30.

Answer

1、

Transition table

NFA State DFA State a b
{0,1,3} A B C
{2} B B ∅
{4} C ∅ C

DFA

3 7 1-1

2、

Transition table

NFA State DFA State 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、

Transition table

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

DFA

3 7 1-3

3.7.2

use Algorithm 3.22 to simulate the NFA's:

  1. Fig. 3.29.
  2. Fig. 3.30.

on input aabb.

Answer

  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

Convert the following regular expressions to deterministic finite automata, using algorithms 3.23 and 3.20:

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

Answer

1、

NFA

3 7 3-1-nfa

Transition table

NFA State DFA State 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

Transition table

NFA State DFA State 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

Transition table

NFA State DFA State 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

Transition table

NFA State DFA State 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