ratexp.derived_term(algo="expansion")

Generate the derived-term automaton from an expression.

The algorithm can be:

  • derivation: rely on the ratexp.derivation.
  • breaking_derivation: likewise, but split the polynomials at each step
  • expansion: rely on the ratexp.expansion.
  • breaking_expansion: likewise, but split the polynomials at each step

Also known as:

  • Antimirov automaton
  • Partial-derivatives automaton

See also:

References:

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.ratexp('[ab]*a[ab]{3}')
a = r.derived_term()
a
Out[2]:
%3 I0 0 (a+b)*a(a+b)(a+b)(a+b) I0->0 F4 0->0 a, b 1 (a+b)(a+b)(a+b) 0->1 a 2 (a+b)(a+b) 1->2 a, b 3 a+b 2->3 a, b 4 ε 3->4 a, b 4->F4

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

In [3]: 
a.strip()
Out[3]:
%3 I0 0 0 I0->0 F4 0->0 a, b 1 1 0->1 a 2 2 1->2 a, b 3 3 2->3 a, b 4 4 3->4 a, b 4->F4

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

In [4]: 
r.derived_term('derivation')
Out[4]:
%3 I0 0 (a+b)*a(a+b)(a+b)(a+b) I0->0 F4 0->0 a, b 1 (a+b)(a+b)(a+b) 0->1 a 2 (a+b)(a+b) 1->2 a, b 3 a+b 2->3 a, b 4 ε 3->4 a, b 4->F4

Extended Rational Expressions

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

In [5]: 
r = b.ratexp('a*b*&(ab){c}')
r
Out[5]:
${a}^{*} \, {b}^{*} \& \left(a \, b\right)^{c}$
In [6]: 
a = r.derived_term()
a
Out[6]:
%3 I0 0 a*b*&(ab){c} I0->0 F0 F1 F2 F3 0->F0 1 a*b*&b{c} 0->1 a 2 b*&∅{c} 0->2 b 1->F1 3 a*b*&∅{c} 1->3 a 4 b*&ε{c} 1->4 b 2->F2 2->2 b 3->F3 3->2 b 3->3 a 4->2 b
In [7]: 
a.shortest(10)
Out[7]:
$\varepsilon \oplus a \oplus b \oplus aa \oplus bb \oplus aaa \oplus aab \oplus abb \oplus bbb \oplus aaaa$

Weighted expressions

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

In [8]: 
q = vcsn.context('lal_char(abc), q')
r = q.ratexp('(<1/6>a*+<1/3>b*)*')
r.derived_term()
Out[8]:
%3 I0 0 (⟨1/6⟩a*+⟨1/3⟩b*)* I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 a*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->1 ⟨1/3⟩a 2 b*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->2 ⟨2/3⟩b 1->F1 ⟨2⟩ 1->1 ⟨4/3⟩a 1->2 ⟨2/3⟩b 2->F2 ⟨2⟩ 2->1 ⟨1/3⟩a 2->2 ⟨5/3⟩b

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 [9]: 
r = q.ratexp('[ab]{2}')
r.derived_term()
Out[9]:
%3 I0 0 (a+b)(a+b) I0->0 F2 1 a+b 0->1 a, b 2 ε 1->2 a, b 2->F2
In [10]: 
r.derived_term('breaking_expansion')
Out[10]:
%3 I0 0 a(a+b) I0->0 I1 1 b(a+b) I1->1 F4 2 a 0->2 a 3 b 0->3 a 1->2 b 1->3 b 4 ε 2->4 a 3->4 b 4->F4