Derived-term Automata for Extended Weighted Rational Expressions

This page is a complement to Derived-term Automata for Extended Weighted Rational Expressions presented at ICTAC 2016. This page exists in several forms:

More information is available here:

You may change the cells, and run then. To run a cell in a notebook, hit "Control-Enter" (in which case the focus stays on the same cell) or "Shift-Enter" (focus goes to the next cell). Beware that depending on the requested operations, Vcsn may generate and compile code, which may be a really slow process on small machines (about a minute): be patient! However, the code is compiled only once: successive uses will be way faster.

To run all the cells anew, select "Restart & Run All" in the "Kernel" menu above.

In [1]:
import vcsn

Valid Expressions

Beware that the so-called ''context'' (which, in Vcsn parlance denotes the type of labels (letters or words, etc.) and the semiring of weights) has an extreme importance. In particular, an expression might be valid in a given context, and invalid in another.

As an example, ${a^*}^*$ is valid in $\mathbb{B}$, so we can build its derived-term automaton.

In [2]:
e = vcsn.B.expression('a**'); e.is_valid()
Out[2]:
True
In [3]:
e.derived_term()
Out[3]:
%3 I0 0 a** I0->0 F0 F1 0->F0 1 a*a** 0->1 a 1->F1 1->1 a

However, the construction will fail in $\mathbb{Q}$, since the constant term for $a^*$ is 1, which is not starrable in $\mathbb{Q}$ (indeed, $1^* = \sum_{k \in \mathbb{N}} 1^k$ is not a value in $\mathbb{Q}$).

In [4]:
e = vcsn.Q.expression('a**'); e.is_valid()
Out[4]:
False
In [5]:
try:
    e.derived_term()
except RuntimeError as err:
    print("error:", err)

error: Q: value is not starrable: 1
  while computing expansion of: a**
  while computing derived-term of: a**

Example $\mathsf{E}_3$: A Lex-like Scanner

Desugaring

We introduce the "context" (i.e., the automaton type) that corresponds to labels that are letters (lal_char) and weights that are rational numbers (q).

In [6]:
Q = vcsn.context('lal_char(ab), q')
Q
Out[6]:
$\{a, b\}\to\mathbb{Q}$

Vcsn supports the <+ operator. It is desugared in a combination of conjuction and complement.

In [7]:
e3 = Q.expression('<2>(ab) <+ <3>[ab]{+}')
e3
Out[7]:
$ \left\langle 2 \right\rangle \,\left(a \, b\right) + \left(a \, b\right)^{c} \& \left\langle 3 \right\rangle \,\left(\left(a + b\right) \, \left(a + b\right)^{*}\right)$

The Derived-Term Automaton

The expansion and the derived-term automaton of $\mathsf{E}_3$ follow.

In [8]:
e3.expansion()
Out[8]:
$a \odot \left[\left\langle 2\right\rangle b \oplus \left\langle 3\right\rangle {b}^{c} \& \left(a + b\right)^{*}\right] \oplus b \odot \left[\left\langle 3\right\rangle \left(a + b\right)^{*}\right]$
In [9]:
e3.derived_term()
Out[9]:
%3 I0 0 ⟨2⟩(ab)+(ab)ᶜ&⟨3⟩((a+b)(a+b)*) I0->0 F2 F3 F5 1 b 0->1 ⟨2⟩a 2 bᶜ&(a+b)* 0->2 ⟨3⟩a 3 (a+b)* 0->3 ⟨3⟩b 5 ε 1->5 b 2->F2 2->3 a 4 εᶜ&(a+b)* 2->4 b 3->F3 3->3 a, b 4->3 a, b 5->F5

Example $\mathsf{E}_1$: A Simple Expression

Polynomials and Derivatives

In [10]:
Z = vcsn.context('lal_char, z')
e1 = Z.expression('<5>\e + <2>ace + <6>bce + <4>ade + <3>bde')
e1
Out[10]:
$ \left\langle 5 \right\rangle \,\varepsilon + \left\langle 2 \right\rangle \,\left(a \, c \, e\right) + \left\langle 4 \right\rangle \,\left(a \, d \, e\right) + \left\langle 6 \right\rangle \,\left(b \, c \, e\right) + \left\langle 3 \right\rangle \,\left(b \, d \, e\right)$

The derivatives of $\mathsf{E}_1$ with respect to $a$ and $b$ are the following polynomials.

In [11]:
e1.derivation('a')
Out[11]:
$\left\langle 2\right\rangle c \, e \oplus \left\langle 4\right\rangle d \, e$
In [12]:
e1.derivation('b')
Out[12]:
$\left\langle 6\right\rangle c \, e \oplus \left\langle 3\right\rangle d \, e$

The expansion of $\mathsf{E}_1$ is as follows. The notation is slightly different from the paper, where for higher clarity the weights in the polynomials are separated from the expressions by a $\otimes$. In the implementation, since the weight is always displayed, this separation is useless, and not put, for conciseness.

In [13]:
e1.expansion()
Out[13]:
$\left\langle 5\right\rangle \oplus a \odot \left[\left\langle 2\right\rangle c \, e \oplus \left\langle 4\right\rangle d \, e\right] \oplus b \odot \left[\left\langle 6\right\rangle c \, e \oplus \left\langle 3\right\rangle d \, e\right]$

The Derived-Term Automaton

The derived-term automaton can be computed using derivations or expansions.

In [14]:
e1.derived_term('expansion')
Out[14]:
%3 I0 0 ⟨5⟩ε+⟨2⟩(ace)+⟨4⟩(ade)+⟨6⟩(bce)+⟨3⟩(bde) I0->0 F0 F4 0->F0 ⟨5⟩ 1 ce 0->1 ⟨2⟩a, ⟨6⟩b 2 de 0->2 ⟨4⟩a, ⟨3⟩b 3 e 1->3 c 2->3 d 4 ε 3->4 e 4->F4
In [15]:
e1.derived_term('derivation')
Out[15]:
%3 I0 0 ⟨5⟩ε+⟨2⟩(ace)+⟨4⟩(ade)+⟨6⟩(bce)+⟨3⟩(bde) I0->0 F0 F4 0->F0 ⟨5⟩ 1 ce 0->1 ⟨2⟩a, ⟨6⟩b 2 de 0->2 ⟨4⟩a, ⟨3⟩b 3 e 1->3 c 2->3 d 4 ε 3->4 e 4->F4

The Deterministic Derived-Term Automaton

In [16]:
e1.derived_term(deterministic=True)
Out[16]:
%3 I0 0 ⟨5⟩ε+⟨2⟩(ace)+⟨4⟩(ade)+⟨6⟩(bce)+⟨3⟩(bde) I0->0 F0 F4 0->F0 ⟨5⟩ 1 ce+⟨2⟩(de) 0->1 ⟨2⟩a 2 ⟨2⟩(ce)+de 0->2 ⟨3⟩b 3 e 1->3 c, ⟨2⟩d 2->3 ⟨2⟩c, d 4 ε 3->4 e 4->F4

Section 4.2: An Infinite Automaton

There exists no finite weighted deterministic automaton for the following expression.

In [17]:
e = Q.expression('a* + (<2>a)*')
e
Out[17]:
${a}^{*} + \left( \left\langle 2 \right\rangle \,a\right)^{*}$
In [18]:
e.derived_term()
Out[18]:
%3 I0 0 a*+(⟨2⟩a)* I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 a* 0->1 a 2 (⟨2⟩a)* 0->2 ⟨2⟩a 1->F1 1->1 a 2->F2 2->2 ⟨2⟩a
In [19]:
a = e.derived_term(deterministic=True, lazy=True)
a
Out[19]:
%3 I0 0 a*+(⟨2⟩a)* I0->0

Repeated evaluations uncover parts of this automaton.

In [20]:
print(a('')); a

2
Out[20]:
%3 I0 0 a*+(⟨2⟩a)* I0->0 F0 0->F0 ⟨2⟩ 1 a*+⟨2⟩(⟨2⟩a)* 0->1 a
In [21]:
print(a('aa')); a

5
Out[21]:
%3 I0 0 a*+(⟨2⟩a)* I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 a*+⟨2⟩(⟨2⟩a)* 0->1 a 1->F1 ⟨3⟩ 2 a*+⟨4⟩(⟨2⟩a)* 1->2 a 2->F2 ⟨5⟩ 3 a*+⟨8⟩(⟨2⟩a)* 2->3 a
In [22]:
print(a('aaaa')); a

17
Out[22]:
%3 I0 0 a*+(⟨2⟩a)* I0->0 F0 F1 F2 F3 F4 0->F0 ⟨2⟩ 1 a*+⟨2⟩(⟨2⟩a)* 0->1 a 1->F1 ⟨3⟩ 2 a*+⟨4⟩(⟨2⟩a)* 1->2 a 2->F2 ⟨5⟩ 3 a*+⟨8⟩(⟨2⟩a)* 2->3 a 3->F3 ⟨9⟩ 4 a*+⟨16⟩(⟨2⟩a)* 3->4 a 4->F4 ⟨17⟩ 5 a*+⟨32⟩(⟨2⟩a)* 4->5 a

Additional Operators

The following automata demonstrate the support of the shuffle operator (denoted ':' in ASCII, and '$\between$' in $\LaTeX$), and the infiltrate operator ('&:' and '$\uparrow$'). See also the documentation of the corresponding operations on automata: automaton.shuffle and automaton.infiltrate.

In [23]:
exp = vcsn.context('lal, q').expression
e1 = exp('<2>a<3>a : <5>a<6>a', 'trivial')
e1
Out[23]:
$ \left\langle 2 \right\rangle \,a \, \left\langle 3 \right\rangle \,a \between \left\langle 5 \right\rangle \,a \, \left\langle 6 \right\rangle \,a$

The 'trivial' argument above restricts the identities to the trivial ones, otherwise additional identities would defeat our attempt to "taint" the as below:

In [24]:
exp('<2>a<3>a : <5>a<6>a')
Out[24]:
$ \left\langle 6 \right\rangle \,\left(a \, a\right) \between \left\langle 30 \right\rangle \,\left(a \, a\right)$
In [25]:
e1.derived_term()
Out[25]:
%3 I0 0 ⟨2⟩a⟨3⟩a:⟨5⟩a⟨6⟩a I0->0 F7 1 ⟨3⟩a:⟨5⟩a⟨6⟩a 0->1 ⟨2⟩a 2 ⟨2⟩a⟨3⟩a:⟨6⟩a 0->2 ⟨5⟩a 4 ⟨3⟩a:⟨6⟩a 1->4 ⟨5⟩a 8 ⟨5⟩a⟨6⟩a 1->8 ⟨3⟩a 3 ⟨2⟩a⟨3⟩a 2->3 ⟨6⟩a 2->4 ⟨2⟩a 5 ⟨3⟩a 3->5 ⟨2⟩a 4->5 ⟨6⟩a 6 ⟨6⟩a 4->6 ⟨3⟩a 7 ε 5->7 ⟨3⟩a 6->7 ⟨6⟩a 7->F7 8->6 ⟨5⟩a
In [26]:
e2 = exp('<2>a<3>a &: <5>a<6>a', 'trivial')
e2
Out[26]:
$ \left\langle 2 \right\rangle \,a \, \left\langle 3 \right\rangle \,a \uparrow \left\langle 5 \right\rangle \,a \, \left\langle 6 \right\rangle \,a$
In [27]:
e2.derived_term()
Out[27]:
%3 I0 0 ⟨2⟩a⟨3⟩a&:⟨5⟩a⟨6⟩a I0->0 F6 1 ⟨3⟩a&:⟨6⟩a 0->1 ⟨10⟩a 2 ⟨3⟩a&:⟨5⟩a⟨6⟩a 0->2 ⟨2⟩a 3 ⟨2⟩a⟨3⟩a&:⟨6⟩a 0->3 ⟨5⟩a 4 ⟨3⟩a 1->4 ⟨6⟩a 6 ε 1->6 ⟨18⟩a 7 ⟨6⟩a 1->7 ⟨3⟩a 2->1 ⟨5⟩a 2->7 ⟨15⟩a 8 ⟨5⟩a⟨6⟩a 2->8 ⟨3⟩a 3->1 ⟨2⟩a 3->4 ⟨12⟩a 5 ⟨2⟩a⟨3⟩a 3->5 ⟨6⟩a 4->6 ⟨3⟩a 5->4 ⟨2⟩a 6->F6 7->6 ⟨6⟩a 8->7 ⟨5⟩a

Broken Derived Terms

"Breaking" variants "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 [28]:
e3 = exp('[ab]{2}')
e3.derived_term()
Out[28]:
%3 I0 0 (a+b)² I0->0 F2 1 a+b 0->1 a, b 2 ε 1->2 a, b 2->F2
In [29]:
e3.derived_term(breaking=True)
Out[29]:
%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