import vcsn

"""
Explanation: 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.
See also:
- automaton.is_deterministic
- automaton.cominimize
- automaton.reduce
Examples
End of explanation
"""


%%automaton 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 -> $

a1.minimize()

"""
Explanation: Weighted
Using minimize or minimize("weighted").
End of explanation
"""


%%automaton 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>

a.minimize()

"""
Explanation: The following example is taken from lombardy.2005.tcs, Fig. 4.
End of explanation
"""


%%automaton 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 -> $

a2.minimize("signature")

"""
Explanation: Signature
End of explanation
"""


a2.is_deterministic()

a2.minimize("moore")

"""
Explanation: Moore
End of explanation
"""


a2.minimize("brzozowski")

"""
Explanation: Brzozowski
End of explanation
"""


a2.minimize("hopcroft")

"""
Explanation: Hopcroft
End of explanation
"""


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

a.transpose().minimize().type()

a.minimize().transpose().type()

"""
Explanation: 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.
End of explanation
"""


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

a.minimize()

m = a.minimize().cominimize()
m

"""
Explanation: 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:
End of explanation
"""


m.type()

"""
Explanation: 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:
End of explanation
"""


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

m == m2

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


