expression
.derived_term(
algo
="expansion")
¶Generate the derived-term automaton from an expression.
The algorithm can be:
"derivation"
: rely on the expression.derivation
."derivation,breaking"
: likewise, but split
the polynomials at each step"expansion"
: rely on the expression.expansion
."expansion,breaking"
: likewise, but split
the polynomials at each step"expansion,deterministic"
: rely on the expression.expansion
and force determinismPreconditions:
"expansion,deterministic"
might not terminate on some expressionsAlso known as:
See also:
References:
import vcsn
In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.
b = vcsn.context('lal_char(ab), b')
r = b.expression('[ab]*a[ab]{3}')
a = r.derived_term()
a
The resulting automaton has its states decorated by their expressions, which can be stripped:
a.strip()
The result does not depend on the core computation: expansions and derivations compute the same terms:
r.derived_term('derivation')
Alternatively, one can request a deterministic result:
r = vcsn.Q.expression('aba+a(a+<-1>ba)')
nfa = r.derived_term('expansion')
nfa
dfa = r.derived_term('expansion,deterministic')
dfa
nfa.determinize()
Extended expressions are supported. For instance, words starting with a
s and then b
s, but not exactly ab
:
r = b.expression('a*b*&(ab){c}')
r
a = r.derived_term()
a
a.shortest(10)
The following example is taken from lombardy.2005.tcs:
q = vcsn.context('lal_char(abc), q')
r = q.expression('(<1/6>a*+<1/3>b*)*')
r.derived_term()
"Breaking" variants of derivation and expansion "split" the polynomials at each step. In short, it means that no state will be labeled by an addition: rather the addition is split into several states. As a consequence, the automaton might have several initial states.
r = q.expression('[ab]{2}')
r.derived_term()
r.derived_term('expansion,breaking')