# automaton.minimize(algo="auto")¶

Minimize an automaton.

The algorithm can be:

• "auto": same as "signature" for Boolean automata on free labelsets, otherwise "weighted".
• "brzozowski": run determinization and codeterminization.
• "hopcroft": requires free labelset and Boolean automaton.
• "moore": requires a deterministic automaton.
• "signature"
• "weighted": same as "signature" but accept non Boolean weightsets.

Preconditions:

• the automaton is trim
• "brzozowski"
• the labelset is free
• the weightset is $\mathbb{B}$
• "hopcroft"
• the labelset is free
• the weightset is $\mathbb{B}$
• "moore"
• the automaton is deterministic
• the weightset is $\mathbb{B}$
• "signature"
• the weightset is $\mathbb{B}$

Postconditions:

• the result is equivalent to the input automaton

Caveat:

• the resulting automaton might not be minimal if the input automaton is not deterministic.

### Examples¶

In :
import vcsn


### Weighted¶

Using minimize or minimize("weighted").

In :
%%automaton -s a1
context = "lal_char(abc), z"
$-> 0 0 -> 1 <2>a 0 -> 2 <3>a 1 -> 1 a 1 -> 3 <4>a 2 -> 2 a 2 -> 4 a 3 ->$
4 -> $ In : a1.minimize()  Out: The following example is taken from lombardy.2005.tcs, Fig. 4. In : %%automaton -s a context = "lal_char, z"$ -> 0
$-> 1 <2> 0 -> 0 a 0 -> 1 b 0 -> 2 <3>a,b 0 -> 3 b 1 -> 1 a, b 1 -> 2 a, <2>b 1 -> 3 <2>a 2 ->$ <2>
3 -> $<2>  In : a.minimize()  Out: ### Signature¶ In : %%automaton -s a2 context = "lal_char(abcde), b"$ -> 0
0 -> 1 a
0 -> 3 b
1 -> 1 a
1 -> 2 b
2 -> 2 a
2 -> 5 b
3 -> 3 a
3 -> 4 b
4 -> 4 a
4 -> 5 b
5 -> 5 a, b
5 -> \$

In :
a2.minimize("signature")

Out:

### Moore¶

In :
a2.is_deterministic()

Out:
True
In :
a2.minimize("moore")

Out:

### Brzozowski¶

In :
a2.minimize("brzozowski")

Out:

### Hopcroft¶

In :
a2.minimize("hopcroft")

Out:

### Minimization of transposed automaton¶

For minimization and cominimization to produce automata of the same implementation types, the minimization of a transposed automaton produces a transposed partition automaton, instead of the converse.

In :
a = vcsn.b.expression('ab+ab').standard()
a.transpose().type()

Out:
'transpose_automaton<mutable_automaton<context<letterset<char_letters>, b>>>'
In :
a.transpose().minimize().type()

Out:
'transpose_automaton<partition_automaton<mutable_automaton<context<letterset<char_letters>, b>>>>'
In :
a.minimize().transpose().type()

Out:
'transpose_automaton<partition_automaton<mutable_automaton<context<letterset<char_letters>, b>>>>'

### Repeated Minimization/Cominimization¶

The minimizations algorithms other than Brzozowski build decorated automata (whose type is partition_automaton). Repeated minimizarion and/or cominization does not stack these decorations, they are collapsed into a single layer.

For instance:

In :
z = vcsn.context('lal_char, z')
a1 = z.expression('<2>abc', 'trivial').standard()
a2 = z.expression('ab<2>c', 'trivial').standard()
a

Out:
In :
a.minimize()

Out:
In :
m = a.minimize().cominimize()
m

Out:

Note that the initial and final states are labeled 0,4 and 3,7 , not {0}, {4} and {3,7} as would have been the case if the two levels of decorations had been kept. Indeed, the type of m is simple:

In :
m.type()

Out:
'partition_automaton<mutable_automaton<context<letterset<char_letters>, z>>>'

We obtain the exact same result (including decorations) even with repeated invocations, even in a different order:

In :
m2 = a.cominimize().cominimize().minimize().minimize()
m2

Out:
In :
m == m2

Out:
True