expression.thompson.ipynb

Kernel: Python 3

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:

• expression.automaton

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.

import vcsn
vcsn.context('lan_char, b').expression('a[bc]d').thompson()

vcsn.context('law_char, b').expression("'aa'[bc]'dd'").thompson()

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.

vcsn.context('lal_char, b').expression("a").thompson().context()

$(\{a, \ldots\})^?\to\mathbb{B}$

Weights

Weights are supported.

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

$\left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}$

t = r.thompson()
t

t.proper()

r.standard()

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

t = vcsn.context('lan_char(abc), q').expression('\e*').thompson()
t

t.is_valid()

False