Hardware Reference
In-Depth Information
Problems
6.1.
Show that the subset construction to convert a non-deterministic finite automa-
ton into a deterministic finite automaton can be performed in O.kn2
n
/ time, where
k is the alphabet size and n is the number of states.
6.2. State Minimization
Algorithms of different complexity and ease of implementation for state minimiza-
tion of deterministic automata have been reported in the literature. For this problem
we rely on the excellent discussion available in [126], where four algorithms are
mentioned:
naive-minimize
,
minimize
,
fast-minimize
and
brzozowski
.
(a)
naive-minimize
has worst-case complexity O.n
3
/. The following pseudo-code
is proposed in [126], p. 83:
naive-minimize
(A
u
t)
f
for (all unordered pairs .p; q/, p
¤
q)
U Œ.p; q/
WD
0;
for (all unordered pairs .p; q/, p
2
F; q
2
Q
n
F )
U Œ.p; q/
WD
1;
done := false;
while (not(done))
f
done := true;
T:= U;
for (each unordered pair .p; q/, with T Œ.p; q/
D
0)
for (each a
2
˙ )
if (T Œ.ı.p; a/; ı.q; a//
D
1)
f
U Œ.p; q/
WD
1;
done := false;
g
return(U )
g
(b)
minimize
has worst-case complexity O.n
2
/. The following pseudo-code is
proposed in [126], p. 87:
minimize
(A
u
t )
f
for (all unordered pairs .p; q/, p
¤
q)
U Œ.p; q/
WD
0;
for (all unordered pairs .p; q/, p
2
F; q
2
Q
n
F )
U Œ.p; q/
WD
1;
for (each unordered pair .p; q/, with either p; q
2
F or p; q
62
F )
if (U Œ.ı.p; a/; ı.q; a//
D
1 for some symbol a
2
˙ )
f
U Œ.p; q/
WD
1;
recursively set UŒ.p
0
;q
0
/
WD
1 for all unmarked pairs .p
0
;q
0
/ on
the
list for .p; q/, and all pairs on those lists, etc.;
Search WWH ::
Custom Search