编译原理第二版习题3.7
Exercises for Section 3.7
3.7.1
Convert to DFA’s the NFA’s of:
- Fig. 3.26.
- Fig. 3.29.
- 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
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:
- Fig. 3.29.
- Fig. 3.30.
on input aabb.
Answer
- -start->{0}-a->{0,1}-a->{0,1,2}-b->{0,2,3}-b->{0,2,3}
- -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:
- (a|b)*
- (a*|b*)*
- ((ε|a)|b*)*
- (a|b)*abb(a|b)*
Answer
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