Implementation of Automata Manipulations - The Unknown Component Problem: Theory and Applications - page 112

else for (all a 2 ˙ )
if(ı.p; a/ ¤ ı.q; a/) put .p; q/ on the list for .ı.p; a/; ı.q; a//;

g
return(U );

g
(c) fast-minimize has worst-case complexity O.n log n/. Due to Hopcroft [14,62],
the best exposition is by Gries [51].
(d) brzozowski has worst-case complexity O.kn2 2n / (but is practice is classified as
often good) and it uses a series of four operations: reverse, subset construction,
reverse, subset construction. Brzozowski described first the algorithm in 1962
and it has been rediscovered more than once since then, see [18] for the whole
story.
Consider the automaton A Dh S A ;˙ A ; A ;r A ;Q A i , defined as follows:
S A Df s0; s1; s2 g , ˙ A Df 0; 1 g , A Df .1; s0; s0/, .0; s0; s1/, .1; s1; s2/,
.0; s1; s1/, .1; s2; s1/, .0; s2; s2/, Q A Df s1; s2 g , r A D s0.
Minimize the automaton A with algorithms (a) and (b).
Retrieve from the literature algorithms (c) and (d) and minimize the automa-
ton A with them.

6.3. Show that if A 1 and A 2 are minimal deterministic finite automata recognizing

a language L ,thenA 1 and A 2 are isomorphic, i.e., their graphs are identical up to

renaming of states.
Give a counter-example to the previous statement for non-deterministic finite
automata.