`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

Examples



In [1]:

    
import vcsn

Classical Expressions

In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.



In [2]:

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









    Out[2]:

The resulting automaton has its states decorated by their expressions, which can be stripped:



In [3]:

    
a.strip()









    Out[3]:

The result does not depend on the core computation: expansions and derivations compute the same terms:



In [4]:

    
r.derived_term('derivation')









    Out[4]:

Deterministic Automata

Alternatively, one can request a deterministic result:



In [5]:

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









    Out[5]:



In [6]:

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









    Out[6]:



In [7]:

    
nfa.determinize()









    Out[7]:

Extended Rational Expressions

Extended expressions are supported. For instance, words starting with as and then bs, but not exactly ab:



In [8]:

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









    Out[8]:





${a}^{*} \, {b}^{*} \& \left(a \, b\right)^{c}$



In [9]:

    
a = r.derived_term()
a









    Out[9]:



In [10]:

    
a.shortest(10)









    Out[10]:





$\varepsilon \oplus \mathit{a} \oplus \mathit{b} \oplus \mathit{aa} \oplus \mathit{bb} \oplus \mathit{aaa} \oplus \mathit{aab} \oplus \mathit{abb} \oplus \mathit{bbb} \oplus \mathit{aaaa}$

Weighted Expressions

The following example is taken from lombardy.2005.tcs:



In [11]:

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









    Out[11]:

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.



In [12]:

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









    Out[12]:



In [13]:

    
r.derived_term('expansion,breaking')









    Out[13]: