expression.automaton.ipynb

Kernel: Python 3

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

See also:

• expression.derived_term

• expression.inductive

• expression.standard

• expression.thompson

• expression.zpc

Examples

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

$\varepsilon + \left\langle 2 \right\rangle \,a + \left\langle 3 \right\rangle \,b$

e.automaton('derived_term')

e.automaton('inductive')

e.automaton('standard')

e.automaton('thompson')

e.automaton('zpc')

e.automaton('zpc,compact')

Trimming

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

e = vcsn.Q.expression('abc&abd')
e.derived_term()

e.automaton('derived_term')

e = vcsn.Q.expression('a?')
e.zpc()

e.automaton('zpc')

Extended Rational Expressions

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

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

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

expansion

inductive

aut('(a*b*){c}')

expansion

inductive