expression.thompson

Generate the Thompson automaton from an expression.

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())

Examples

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



In [1]:

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









    



:0: FutureWarning: IPython widgets are experimental and may change in the future.






    














    Out[1]:



In [2]:

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









    Out[2]:

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\})^?\rightarrow\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]:



In [6]:

    
t.proper()









    Out[6]:



In [7]:

    
r.standard()









    Out[7]:

Note however that you may generate invalid automata:



In [8]:

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









    Out[8]:



In [9]:

    
t.is_valid()









    Out[9]:





False