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

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.

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

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