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:

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.expression('[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

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]:
%3 I0 0 aba+a(a+⟨-1⟩(ba)) I0->0 F3 1 ba 0->1 a 2 a+⟨-1⟩(ba) 0->2 a 4 a 1->4 b 3 ε 2->3 a 2->4 ⟨-1⟩b 3->F3 4->3 a
In [6]:
dfa = r.derived_term('expansion,deterministic')
dfa
Out[6]:
%3 I0 0 aba+a(a+⟨-1⟩(ba)) I0->0 F2 1 a 0->1 a 2 ε 1->2 a 2->F2
In [7]:
nfa.determinize()
Out[7]:
%3 I0 0 aba+a(a+⟨-1⟩(ba)) I0->0 F2 1 ba, a+⟨-1⟩(ba) 0->1 a 2 ε 1->2 a 2->F2

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]:
%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 [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]:
%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 [12]:
r = q.expression('[ab]{2}')
r.derived_term()
Out[12]:
%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 [13]:
r.derived_term('expansion,breaking')
Out[13]:
%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