expression.thompson

Generate the Thompson automaton from an expression.

Preconditions:

  • the expression is basic.

Caveats:

  • it is not guaranteed that Result.is_valid()
  • the context of the result might be different from the original context: spontaneous-transition support is required.

Properties:

  • Result.proper().is_isomorphic(r.standard())

See also:

Examples

The Thompson procedure generates an automaton with spontaneous-transitions, which requires a labelset that features a "one" label. The nullableset and wordset labelsets (and their compositions) do support a "one" label.

In [1]:
import vcsn
vcsn.context('lan_char, b').expression('a[bc]d').thompson()
Out[1]:
%3 I0 0 0 I0->0 F9 1 1 0->1 a 2 2 1->2 ε 4 4 2->4 ε 6 6 2->6 ε 3 3 8 8 3->8 ε 5 5 4->5 b 5->3 ε 7 7 6->7 c 7->3 ε 9 9 8->9 d 9->F9
In [2]:
vcsn.context('law_char, b').expression("'aa'[bc]'dd'").thompson()
Out[2]:
%3 I0 0 0 I0->0 F9 1 1 0->1 aa 2 2 1->2 ε 4 4 2->4 ε 6 6 2->6 ε 3 3 8 8 3->8 ε 5 5 4->5 b 5->3 ε 7 7 6->7 c 7->3 ε 9 9 8->9 dd 9->F9

You may, however, use a labelset which does not feature a "one", in which case the context of the automaton will be different from the one of the expression.

In [3]:
vcsn.context('lal_char, b').expression("a").thompson().context()
Out[3]:
$(\{a, \ldots\})^?\to\mathbb{B}$

Weights

Weights are supported.

In [4]:
r = vcsn.context('lan_char(abc), q').expression('(<1/6>a*+<1/3>b*)*')
r
Out[4]:
$\left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}$
In [5]:
t = r.thompson()
t
Out[5]:
%3 I10 10 10 I10->10 F11 0 0 4 4 0->4 ε 8 8 0->8 ε 1 1 1->0 ε 11 11 1->11 ε 2 2 3 3 2->3 a 3->2 ε 5 5 3->5 ε 4->2 ⟨1/6⟩ε 4->5 ⟨1/6⟩ε 5->1 ε 6 6 7 7 6->7 b 7->6 ε 9 9 7->9 ε 8->6 ⟨1/3⟩ε 8->9 ⟨1/3⟩ε 9->1 ε 10->0 ε 10->11 ε 11->F11
In [6]:
t.proper()
Out[6]:
%3 I2 2 2 I2->2 F0 F1 F2 0 0 0->F0 ⟨2⟩ 0->0 ⟨4/3⟩a 1 1 0->1 ⟨2/3⟩b 1->F1 ⟨2⟩ 1->0 ⟨1/3⟩a 1->1 ⟨5/3⟩b 2->F2 ⟨2⟩ 2->0 ⟨1/3⟩a 2->1 ⟨2/3⟩b
In [7]:
r.standard()
Out[7]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 ⟨2⟩ 1 1 0->1 ⟨1/3⟩a 3 3 0->3 ⟨2/3⟩b 1->F1 ⟨2⟩ 1->1 ⟨4/3⟩a 1->3 ⟨2/3⟩b 3->F3 ⟨2⟩ 3->1 ⟨1/3⟩a 3->3 ⟨5/3⟩b

Note however that you may generate invalid automata (from invalid expressions):

In [8]:
t = vcsn.context('lan_char(abc), q').expression('\e*').thompson()
t
Out[8]:
%3 I2 2 2 I2->2 F3 0 0 1 1 0->1 ε 1->0 ε 3 3 1->3 ε 2->0 ε 2->3 ε 3->F3
In [9]:
t.is_valid()
Out[9]:
False