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