expression.automaton(algo="auto")¶

Generate an automaton from an expression.

The algo can be:

• "auto": currently equivalent to "expansion", eventually should mix "standard" for basic expressions (faster) and "expansion" otherwise (more general).
• "derivation": use derivation-based expression.derived_term, trim and stripped.
• "derived_term": same as "expansion".
• "inductive": use expression.inductive.
• "expansion": use expansion-based expression.derived_term, trim and stripped.
• "standard": use expression.standard.
• "thompson": use expression.thompson.
• "zpc": use expression.zpc, trim.
• "zpc,compact": use expression.zpc, "compact" version, trim.

Precondition:

• "standard", "thompson", "zpc", "zpc,compact": the expression is not extended

Examples¶

In [1]:
import vcsn
from IPython.display import display
e = vcsn.Q.expression('\e+<2>a+<3>b')
e

Out[1]:
$\varepsilon + \left\langle 2 \right\rangle \,a + \left\langle 3 \right\rangle \,b$
In [2]:
e.automaton('derived_term')

Out[2]:
In [3]:
e.automaton('inductive')

Out[3]:
In [4]:
e.automaton('standard')

Out[4]:
In [5]:
e.automaton('thompson')

Out[5]:
In [6]:
e.automaton('zpc')

Out[6]:
In [7]:
e.automaton('zpc,compact')

Out[7]:

Trimming¶

The automata are guaranteed to be trim, even if the algorithm used by automaton generated useless states.

In [8]:
e = vcsn.Q.expression('abc&abd')
e.derived_term()

Out[8]:
In [9]:
e.automaton('derived_term')

Out[9]:
In [10]:
e = vcsn.Q.expression('a?')
e.zpc()

Out[10]:
In [11]:
e.automaton('zpc')

Out[11]:

Extended Rational Expressions¶

The derived-term based algorithms and "inductive" support extended expressions.

In [12]:
def aut(e):
e = vcsn.context('lal, q').expression(e)
for a in ['expansion', 'inductive']:
print(a)
display(e.automaton(a))

aut('(ab*c){T}')

expansion

inductive

In [13]:
aut('[ab]*a[ab]{1} & [ab]*a[ab]{2} & [ab]*a[ab]{3}')

expansion

inductive

In [14]:
aut('(a*b*){c}')

expansion

inductive