• Introduction
• 1. 1.Introduction
• 2. 2.A Simple Syntax-Directed Translator
• 3. 3.Lexical Analysis
• 4. 4.Syntax Analysis
• 5. 5.Syntax-Directed Translation
• 6. 6.Intermediate-Code Generation
• 7. 7.Run-Time Environments
• 8. 8.Code Generation
• 9. 12.InterProcedural Analysis
• Published with GitBook

# 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.

1、

Transition table

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

DFA

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、

Transition table

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

DFA

### 3.7.2

use Algorithm 3.22 to simulate the NFA's:

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

on input 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

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)*

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

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、

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

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