Convert to DFA's the NFA's of:
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
use Algorithm 3.22 to simulate the NFA's:
on input aabb.
Convert the following regular expressions to deterministic finite automata, using algorithms 3.23 and 3.20:
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