import vcsn

"""
Explanation: expression.derived_term(algo="expansion")
Generate the derived-term automaton from an expression.
The algorithm can be:
- "derivation": rely on the expression.derivation.
- "derivation,breaking": likewise, but split the polynomials at each step
- "expansion": rely on the expression.expansion.
- "expansion,breaking": likewise, but split the polynomials at each step
- "expansion,deterministic": rely on the expression.expansion and force determinism
Preconditions:
- derivation-based algorithms require a free labelset (e.g., word labels are not supported)
- "expansion,deterministic" might not terminate on some expressions
- expressions with complement operators might not terminate either
Also known as:
- Antimirov automaton
- equation automaton
- partial-derivatives automaton
See also:
- expression.automaton
- expression.derivation
- expression.expansion
References:
- antimirov.1996.tcs introduces the concept of derived-term automaton
- lombardy.2005.tcs defines the derived-term construction for weighted automata (and coins the name "derived-term").
- angrand.2010.jalc defines its breaking variant
Examples
End of explanation
"""


b = vcsn.context('lal_char(ab), b')
r = b.expression('[ab]*a[ab]{3}')
a = r.derived_term()
a

"""
Explanation: Classical Expressions
In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.
End of explanation
"""


a.strip()

"""
Explanation: The resulting automaton has its states decorated by their expressions, which can be stripped:
End of explanation
"""


r.derived_term('derivation')

"""
Explanation: The result does not depend on the core computation: expansions and derivations compute the same terms:
End of explanation
"""


r = vcsn.Q.expression('aba+a(a+<-1>ba)')
nfa = r.derived_term('expansion')
nfa

dfa = r.derived_term('expansion,deterministic')
dfa

nfa.determinize()

"""
Explanation: Deterministic Automata
Alternatively, one can request a deterministic result:
End of explanation
"""


r = b.expression('a*b*&(ab){c}')
r

a = r.derived_term()
a

a.shortest(10)

"""
Explanation: Extended Rational Expressions
Extended expressions are supported.  For instance, words starting with as and then bs, but not exactly ab:
End of explanation
"""


q = vcsn.context('lal_char(abc), q')
r = q.expression('(<1/6>a*+<1/3>b*)*')
r.derived_term()

"""
Explanation: Weighted Expressions
The following example is taken from lombardy.2005.tcs:
End of explanation
"""


r = q.expression('[ab]{2}')
r.derived_term()

r.derived_term('expansion,breaking')

"""
Explanation: Broken derived-term automaton
"Breaking" variants of derivation and expansion "split" the polynomials at each step.  In short, it means that no state will be labeled by an addition: rather the addition is split into several states.  As a consequence, the automaton might have several initial states.
End of explanation
"""


