Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News AboutSign UpSign In
| Download
Views: 45859
Kernel: Python 3

Derived-Term Automata of Multitape Expressions with Composition

This page is a complement to the paper Derived-Term Automata of Multitape Expressions with Composition. This page exists in several forms:

More information is available here:

You may change the cells, and run then. To run a cell in a notebook, hit "Control-Enter" (in which case the focus stays on the same cell) or "Shift-Enter" (focus goes to the next cell). Beware that depending on the requested operations, Vcsn may generate and compile code, which may be a really slow process on small machines (about a minute): be patient! However, the code is compiled only once: successive uses will be way faster.

To run all the cells anew, select "Restart & Run All" in the "Kernel" menu above. ParseError: KaTeX parse error: \newcommand{\coloneqq} attempting to redefine \coloneqq; use \renewcommand

import vcsn vcsn.setenv(SEED=1) vcsn.table = vcsn.ipython.table # There will be examples with benchmarks, tell the test suite to ignore the durations. # global ignore: \d+ms

Introduction: Motivating Examples

First we introduce the context we are interested in: labels are letter-or-empty-word (lan), two tapes (lat), weights are in the tropical semiring Zmin:=Z,min,+,,0\mathbb{Z}_{\min} := \langle \mathbb{Z}, \min, +, \infty, 0 \rangle.

zmin2 = vcsn.context('lat<lan, lan>, zmin') zmin2

({})?×({})?Zmin(\{\ldots\})^? \times (\{\ldots\})^?\to\mathbb{Z}_{\text{min}}

The following examples show how the multiplication and addition of Zmin\mathbb{Z}_{\min} behave:

zmin2.weight('1') * zmin2.weight('3')

44

zmin2.weight('1') + zmin2.weight('3')

11

The first automaton, A\mathcal{A}, is obtained from the following rational expression (the empty word is noted \e in Vcsn, and rendered ε\varepsilon even as an expression, whereas in the paper it is written 1\mathsf{1}).

zmin2.expression(r'(a|a+b|b+⟨1⟩(\e|(a+b)+(a+b)|\e))∗')

(aa+bb+1(ε|(a+b)+(a+b)|ε))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left( \left. \varepsilon \middle| \left(a + b\right) \right. + \left. \left(a + b\right) \middle| \varepsilon \right. \right)\right)^{*}

Or, using syntactic sugar (aaaa \coloneqq a|a, [ab]a+b[ab] \coloneqq a+b):

e1 = zmin2.expression(r'([ab] + ⟨1⟩(\e|[ab] + [ab]|\e))∗') e1

(aa+bb+1(ε|(a+b)+(a+b)|ε))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left( \left. \varepsilon \middle| \left(a + b\right) \right. + \left. \left(a + b\right) \middle| \varepsilon \right. \right)\right)^{*}

a1 = e1.derived_term() a1
Image in a Jupyter notebook

Admittedly, the display of multitape labels on transition could be improved. The rather cryptic [ε|a-a|εb|ε] denotes ε|a+ε|b+a|ε+b|ε. This will be addressed in future versions of Vcsn.

Ng's automaton is:

e2 = zmin2.expression('[ab]∗ (⟨1⟩(\e|[ab] + [ab]|\e) + ⟨2⟩(a|b + b|a))∗') e2

(aa+bb)(2(ab+ba)+1(ε|(a+b)+(a+b)|ε))\left(a|a + b|b\right)^{*} \, \left( \left\langle 2 \right\rangle \,\left(a|b + b|a\right) + \left\langle 1 \right\rangle \,\left( \left. \varepsilon \middle| \left(a + b\right) \right. + \left. \left(a + b\right) \middle| \varepsilon \right. \right)\right)^{*}

e2.derived_term()
Image in a Jupyter notebook

Or, cleaned from state decorations:

a2 = e2.automaton('expansion') a2
Image in a Jupyter notebook

Mohri factors his automaton A\mathcal{A} in the composition of A1\mathcal{A}_1 and A2\mathcal{A}_2:

f1 = zmin2.expression('([ab] + ⟨1⟩(\e|i + [ab]|s))∗') f2 = zmin2.expression('([ab] + i|[ab] + s|\e)∗') f = f1.compose(f2) vcsn.table([["Name", "Expression", "Automaton"], ["$\mathcal{A}_1$", f1, f1.derived_term()], ["$\mathcal{A}_2$", f2, f2.derived_term()], ["$\mathcal{A}$", f, f.derived_term()]])
Name Expression Automaton
A1\mathcal{A}_1 (aa+bb+1(εi+(a+b)|s))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left(\varepsilon|i + \left. \left(a + b\right) \middle| s \right. \right)\right)^{*}
A2\mathcal{A}_2 (aa+bb+sε+i|(a+b))\left(a|a + b|b + s|\varepsilon + \left. i \middle| \left(a + b\right) \right. \right)^{*}
A\mathcal{A} (aa+bb+1(εi+(a+b)|s))@(aa+bb+sε+i|(a+b))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left(\varepsilon|i + \left. \left(a + b\right) \middle| s \right. \right)\right)^{*}@\left(a|a + b|b + s|\varepsilon + \left. i \middle| \left(a + b\right) \right. \right)^{*}

The resulting automaton is exactly the automaton A\mathcal{A}.

Section 2.2: Weighted Rational Expressions

The set of operators supported by Vcsn is quite large, see the documentation for details. We will show a few simple examples.

We start with a simple example of a single tape expression whose labels are letters-or-empty-word (lan), and weights are rational numbers. We first introduce what in Vcsn is called a context which is simply an object to type automata, expressions, expansions, etc.

q = vcsn.context('lan, q') q

({})?Q(\{\ldots\})^?\to\mathbb{Q}

From this context, we can build (typed) expressions:

e = q.expression('(<1/6>a*+<1/3>b*)*') e

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

Let's introduce qexp as a shorthand to build an expression from a string.

qexp = q.expression qexp('(<1/6>a*+<1/3>b*)*')

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

The usual +{}^+ quantifier (E+EE\Ed^+ \coloneqq \Ed\Ed^*) is written {+}, to disambiguate from the binary operator (E+F\Ed + \Fd):

qexp('a{+}+b{+}')

aa+bba \, {a}^{*} + b \, {b}^{*}

The following examples show the trivial identities in action.

def example(*es): import pandas as pd pd.options.display.max_colwidth = 0 ids = ['none', 'trivial'] res = [[e] + ['${:x}$'.format(qexp(e, id)) for id in ids] for e in es] return pd.DataFrame(res, columns=['.' + ' ' * 20 + id.title() for id in ['input'] + ids]) example('\z+a', 'a+a', '\za', '\ea', '(\e\za+\z)*')
.                    Input .                    None .                    Trivial
0 \z+a +a\emptyset + a aa
1 a+a a+aa + a a+aa + a
2 \za a\emptyset \, a \emptyset
3 \ea εa\varepsilon \, a aa
4 (\e\za+\z)* (ε(a)+)\left(\varepsilon \, \left(\emptyset \, a\right) + \emptyset\right)^{*} ε\varepsilon

Vcsn also provides Python operators to assemble expressions.

('1/6' * qexp('a').star() + '1/3' * qexp('b').star()).star()

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

The Python operator | builds a multitape expression from simple tape ones, and the Python operator @ denotes composition. As a matter of fact, the reason why composition is denoted @@ in Vcsn is because that is the only remaining operator available in Python. Besides, more beautiful symbols, such as \circ for instance, are technical to type.

qexp('a*') | qexp('b*')

a|b \left. {a}^{*} \middle| {b}^{*} \right.

(qexp('a*') | qexp('b')) @ (qexp('b') | qexp('c*'))

a|b@b|c \left. {a}^{*} \middle| b \right. @ \left. b \middle| {c}^{*} \right.

Section 3: Rational Expansions

We start with a simple example of a single tape expression whose labels are letters-or-empty-word (lan), and weights are rational numbers.

e = qexp('a+<2>bc*') e

a+2(bc)a + \left\langle 2 \right\rangle \,\left(b \, {c}^{*}\right)

Its expansion is:

e.expansion()

a[ε]b[2c]a \odot \left[\varepsilon\right] \oplus b \odot \left[\left\langle 2\right\rangle {c}^{*}\right]

And its derived-term automaton (contrary to the paper, in Vcsn the empty expression is denoted ε\varepsilon instead of 1\mathsf{1}):

e.derived_term()
Image in a Jupyter notebook

which is smaller than its standard automaton:

e.standard()
Image in a Jupyter notebook

The following example demonstrates how successors of a state are computed. It uses the shuffle operator, denoted :, for illustration.

qexp('ab:xy').derived_term()
Image in a Jupyter notebook

Examples 1 to 4: A Simple Multitape Expression (also Figure 1)

Labels are pairs of letter-or-empty-word (lat<lan, lan>), and weights are rational numbers (q).

q2 = vcsn.context('lat<lan(abcde), lan(xy)>, q') q2

({a,b,c,d,e})?×({x,y})?Q(\{a, b, c, d, e\})^? \times (\{x, y\})^?\to\mathbb{Q}

The expression E1\mathsf{E}_1 is:

e1 = q2.expression('⟨4⟩ade*|x + ⟨3⟩bde*|x + ⟨2⟩ace*|xy + ⟨6⟩bce*|xy') e1

4(ade)|x+3(bde)|x+2(ace)|xy+6(bce)|xy \left. \left\langle 4 \right\rangle \,\left(a \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 3 \right\rangle \,\left(b \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 2 \right\rangle \,\left(a \, c \, {e}^{*}\right) \middle| x \, y \right. + \left. \left\langle 6 \right\rangle \,\left(b \, c \, {e}^{*}\right) \middle| x \, y \right.

Its expansion is:

e1.expansion()

ax[2ce|y4de|ε]bx[6ce|y3de|ε]a|x \odot \left[\left\langle 2\right\rangle \left. c \, {e}^{*} \middle| y \right. \oplus \left\langle 4\right\rangle \left. d \, {e}^{*} \middle| \varepsilon \right. \right] \oplus b|x \odot \left[\left\langle 6\right\rangle \left. c \, {e}^{*} \middle| y \right. \oplus \left\langle 3\right\rangle \left. d \, {e}^{*} \middle| \varepsilon \right. \right]

The derived-term automaton of E1\mathsf{E}_1, AE1\mathcal{A}_{\mathsf{E}_1}, is:

a1 = e1.derived_term() a1
Image in a Jupyter notebook

The ten shortest accepted multitape words are:

a1.shortest(10)

2acxy4adx6bcxy3bdx2acexy4adex6bcexy3bdex2aceexy4adeex\left\langle 2\right\rangle \mathit{ac}|\mathit{xy} \oplus \left\langle 4\right\rangle \mathit{ad}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{bc}|\mathit{xy} \oplus \left\langle 3\right\rangle \mathit{bd}|\mathit{x} \oplus \left\langle 2\right\rangle \mathit{ace}|\mathit{xy} \oplus \left\langle 4\right\rangle \mathit{ade}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{bce}|\mathit{xy} \oplus \left\langle 3\right\rangle \mathit{bde}|\mathit{x} \oplus \left\langle 2\right\rangle \mathit{acee}|\mathit{xy} \oplus \left\langle 4\right\rangle \mathit{adee}|\mathit{x}

Example 5: An Exponential Number of States

We introduce a three-tape context. Unfortunately the automatic graphical rendering is poor.

q3 = vcsn.context('lat<lan, lan, lan>, q') a3 = q3.expression('a*|b*|c*').derived_term() a3
Image in a Jupyter notebook

From multitape automata currently Vcsn extracts only simple-tape expressions over multitape generators (e.g. (εa)(\varepsilon | a)^*) instead of general mutitape expressions (e.g. εa\varepsilon | a^*):

a3.expression()

(abc)(ε+(εεc)(εεc)+(εbε)(εbε)+(aεε)(aεε)+(εbc)(εbc)(ε+(εεc)(εεc)+(εbε)(εbε))+(aεc)(aεc)(ε+(εεc)(εεc)+(aεε)(aεε))+(abε)(abε)(ε+(εbε)(εbε)+(aεε)(aεε)))\left(a|b|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*} + \left(\varepsilon|b|c\right) \, \left(\varepsilon|b|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*}\right) + \left(a|\varepsilon|c\right) \, \left(a|\varepsilon|c\right)^{*} \, \left(\varepsilon + \left(\varepsilon|\varepsilon|c\right) \, \left(\varepsilon|\varepsilon|c\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*}\right) + \left(a|b|\varepsilon\right) \, \left(a|b|\varepsilon\right)^{*} \, \left(\varepsilon + \left(\varepsilon|b|\varepsilon\right) \, \left(\varepsilon|b|\varepsilon\right)^{*} + \left(a|\varepsilon|\varepsilon\right) \, \left(a|\varepsilon|\varepsilon\right)^{*}\right)\right)

In the case of the corresponding five-tape expression, the generated graphical rendering is so messy that it is totally useless (try it if you want!). So instead of displaying the automaton, we list its states.

q5 = vcsn.context('lat<lan(a), lan(b), lan(c), lan(d), lan(e)>, q') e5 = q5.expression('a*|b*|c*|d*|e*') e5

a|b|c|d|e \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right.

e5.expansion()

1εεεεe[ε|ε|ε|ε|e]εεεdε[ε|ε|ε|d|ε]εεεde[ε|ε|ε|d|e]εεcεε[ε|ε|c|ε|ε]εεcεe[ε|ε|c|ε|e]εεcdε[ε|ε|c|d|ε]εεcde[ε|ε|c|d|e]εbεεε[ε|b|ε|ε|ε]εbεεe[ε|b|ε|ε|e]εbεdε[ε|b|ε|d|ε]εbεde[ε|b|ε|d|e]εbcεε[ε|b|c|ε|ε]εbcεe[ε|b|c|ε|e]εbcdε[ε|b|c|d|ε]εbcde[ε|b|c|d|e]aεεεε[a|ε|ε|ε|ε]aεεεe[a|ε|ε|ε|e]aεεdε[a|ε|ε|d|ε]aεεde[a|ε|ε|d|e]aεcεε[a|ε|c|ε|ε]aεcεe[a|ε|c|ε|e]aεcdε[a|ε|c|d|ε]aεcde[a|ε|c|d|e]abεεε[a|b|ε|ε|ε]abεεe[a|b|ε|ε|e]abεdε[a|b|ε|d|ε]abεde[a|b|ε|d|e]abcεε[a|b|c|ε|ε]abcεe[a|b|c|ε|e]abcdε[a|b|c|d|ε]abcde[a|b|c|d|e]\left\langle 1\right\rangle \oplus \varepsilon|\varepsilon|\varepsilon|\varepsilon|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|\varepsilon|d|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|\varepsilon|d|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|c|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|c|\varepsilon|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|\varepsilon|c|d|\varepsilon \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|\varepsilon|c|d|e \odot \left[ \left. \varepsilon \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|b|\varepsilon|\varepsilon|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|\varepsilon|d|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|b|\varepsilon|d|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|c|\varepsilon|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus \varepsilon|b|c|\varepsilon|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus \varepsilon|b|c|d|\varepsilon \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus \varepsilon|b|c|d|e \odot \left[ \left. \varepsilon \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|\varepsilon|\varepsilon|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|\varepsilon|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|\varepsilon|\varepsilon|d|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|c|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|\varepsilon|c|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|\varepsilon|c|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|\varepsilon|c|d|e \odot \left[ \left. {a}^{*} \middle| \varepsilon \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|b|\varepsilon|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|b|\varepsilon|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|b|\varepsilon|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|b|\varepsilon|d|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| \varepsilon \middle| {d}^{*} \middle| {e}^{*} \right. \right] \oplus a|b|c|\varepsilon|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| \varepsilon \right. \right] \oplus a|b|c|\varepsilon|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| \varepsilon \middle| {e}^{*} \right. \right] \oplus a|b|c|d|\varepsilon \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| \varepsilon \right. \right] \oplus a|b|c|d|e \odot \left[ \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. \right]

a5 = e5.derived_term() a5.states()
['a*|b*|c*|d*|e*', 'a*|b*|c*|d*|ε', 'a*|b*|c*|ε|e*', 'a*|b*|c*|ε|ε', 'a*|b*|ε|d*|e*', 'a*|b*|ε|d*|ε', 'a*|b*|ε|ε|e*', 'a*|b*|ε|ε|ε', 'a*|ε|c*|d*|e*', 'a*|ε|c*|d*|ε', 'a*|ε|c*|ε|e*', 'a*|ε|c*|ε|ε', 'a*|ε|ε|d*|e*', 'a*|ε|ε|d*|ε', 'a*|ε|ε|ε|e*', 'a*|ε|ε|ε|ε', 'ε|b*|c*|d*|e*', 'ε|b*|c*|d*|ε', 'ε|b*|c*|ε|e*', 'ε|b*|c*|ε|ε', 'ε|b*|ε|d*|e*', 'ε|b*|ε|d*|ε', 'ε|b*|ε|ε|e*', 'ε|b*|ε|ε|ε', 'ε|ε|c*|d*|e*', 'ε|ε|c*|d*|ε', 'ε|ε|c*|ε|e*', 'ε|ε|c*|ε|ε', 'ε|ε|ε|d*|e*', 'ε|ε|ε|d*|ε', 'ε|ε|ε|ε|e*']

Example 6: A Sed-like Substitution

e2 = q2.expression('(a{+}|x + b{+}|y)*') e2

(aa|x+bb|y)\left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}

e2.expansion()

1ax[(a|ε)(aa|x+bb|y)]by[(b|ε)(aa|x+bb|y)]\left\langle 1\right\rangle \oplus a|x \odot \left[\left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\right] \oplus b|y \odot \left[\left( \left. {b}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\right]

a2 = e2.derived_term() a2
Image in a Jupyter notebook

Again, the extracted expression is less readable than the one we started from.

a2.expression()

ε+(ax)(aε+ax)+(by+(ax)(aε+ax)(by))(bε+by+(ax)(aε+ax)(by))(ε+(ax)(aε+ax))\varepsilon + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} + \left(b|y + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} \, \left(b|y\right)\right) \, \left(b|\varepsilon + b|y + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*} \, \left(b|y\right)\right)^{*} \, \left(\varepsilon + \left(a|x\right) \, \left(a|\varepsilon + a|x\right)^{*}\right)

A More Complex Expression

The previous examples often looked like sed-like substitutions, in the sense that the first tape was often a composite expression, but the second tape a simple label. There is no such limitation.

e = q2.expression('(<2>[ab])* | (<3>[xy])*') e

(2(a+b))|(3(x+y)) \left. \left( \left\langle 2 \right\rangle \,\left(a + b\right)\right)^{*} \middle| \left( \left\langle 3 \right\rangle \,\left(x + y\right)\right)^{*} \right.

a = e.derived_term() a
Image in a Jupyter notebook
a.shortest(20)

εε3εx3εy2aε6ax6ay2bε6bx6by9εxx9εxy9εyx9εyy18axx18axy18ayx18ayy18bxx18bxy18byx\varepsilon|\varepsilon \oplus \left\langle 3\right\rangle \varepsilon|\mathit{x} \oplus \left\langle 3\right\rangle \varepsilon|\mathit{y} \oplus \left\langle 2\right\rangle \mathit{a}|\varepsilon \oplus \left\langle 6\right\rangle \mathit{a}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{a}|\mathit{y} \oplus \left\langle 2\right\rangle \mathit{b}|\varepsilon \oplus \left\langle 6\right\rangle \mathit{b}|\mathit{x} \oplus \left\langle 6\right\rangle \mathit{b}|\mathit{y} \oplus \left\langle 9\right\rangle \varepsilon|\mathit{xx} \oplus \left\langle 9\right\rangle \varepsilon|\mathit{xy} \oplus \left\langle 9\right\rangle \varepsilon|\mathit{yx} \oplus \left\langle 9\right\rangle \varepsilon|\mathit{yy} \oplus \left\langle 18\right\rangle \mathit{a}|\mathit{xx} \oplus \left\langle 18\right\rangle \mathit{a}|\mathit{xy} \oplus \left\langle 18\right\rangle \mathit{a}|\mathit{yx} \oplus \left\langle 18\right\rangle \mathit{a}|\mathit{yy} \oplus \left\langle 18\right\rangle \mathit{b}|\mathit{xx} \oplus \left\langle 18\right\rangle \mathit{b}|\mathit{xy} \oplus \left\langle 18\right\rangle \mathit{b}|\mathit{yx}

Section 5.3: Derived-Term Automaton with Composition

f1 = zmin2.expression('([ab] + ⟨1⟩(\e|I + [ab]|S))∗') f2 = zmin2.expression('([ab] + I|[ab] + S|\e)∗') f = f1 @ f2 f.derived_term()
Image in a Jupyter notebook

Here we show, as will be discussed in Section 6.2, the role played by identities. Here, they are fully disabled (via the 'none' argument).

f1 = zmin2.expression('([ab] + ⟨1⟩(\e|I + [ab]|S))∗', 'none') f2 = zmin2.expression('([ab] + I|[ab] + S|\e)∗', 'none') f = f1 @ f2 f.derived_term()
Image in a Jupyter notebook

Then we show an example with the endmarker (as discussed in Section 6.4).

f1 = zmin2.expression('([ab] + ⟨1⟩(\e|I + [ab]|S))∗ ($|$)') f2 = zmin2.expression('([ab] + S|[ab] + S|\e)∗ ($|$)') f = f1 @ f2 f.derived_term()
Image in a Jupyter notebook

Example 8

In this example we used symbolic weights, k,hk, h. To simulate this we introduce expressions whose weights are expressions (whose weights are in Q\mathbb{Q}):

eset2 = vcsn.context('lat<lan(ab), lan(ab)>, expressionset<lan(kh), q>') eset2

({a,b})?×({a,b})?RatE[({h,k})?Q](\{a, b\})^? \times (\{a, b\})^?\to\mathsf{RatE}[(\{h, k\})^?\to\mathbb{Q}]

Then we build and display the expression, its expansion, and its derived-term automaton.

e = eset2.expression('(⟨k⟩\e|a)∗ @ (⟨h⟩aa|\e)∗', 'trivial') vcsn.display(e, e.expansion(), e.derived_term())

(kε|a)@(haa|ε)\left( \left. \left\langle k \right\rangle \,\varepsilon \middle| a \right. \right)^{*}@\left( \left. \left\langle h \right\rangle \,a \, a \middle| \varepsilon \right. \right)^{*}

εεε[kh(kε|a)@(aε)(haa|ε)]\left\langle \varepsilon\right\rangle \oplus \varepsilon|\varepsilon \odot \left[\left\langle k \, h\right\rangle \left( \left. \left\langle k \right\rangle \,\varepsilon \middle| a \right. \right)^{*}@\left(a|\varepsilon\right) \, \left( \left. \left\langle h \right\rangle \,a \, a \middle| \varepsilon \right. \right)^{*}\right]

Image in a Jupyter notebook
vcsn.setenv(OLDWAY=0, DENORM=1) e = eset2.expression('(⟨k⟩\e|a)∗ @ (⟨h⟩aa|\e)∗', 'trivial') vcsn.display(e, e.expansion(), e.derived_term())

(kε|a)@(haa|ε)\left( \left. \left\langle k \right\rangle \,\varepsilon \middle| a \right. \right)^{*}@\left( \left. \left\langle h \right\rangle \,a \, a \middle| \varepsilon \right. \right)^{*}

ParseError: KaTeX parse error: Undefined control sequence: \varepsilon@ at position 277: …h\right\rangle \̲v̲a̲r̲e̲p̲s̲i̲l̲o̲n̲@̲\left(a|\vareps…

Image in a Jupyter notebook

Section 6.1: Discussion on the Validity of Automata

The following function takes a rational expression, and generates derived-term automata from denormalized expansions (simpler equation, but generates many spontaneous transitions), and from "normal" expansions. The former are often simpler, but may generate invalid automata.

vcsn.setenv(DENORM=0, OLDWAY=0) import vcsn def compare(e, name=None, ctx='lan, q'): if not isinstance(e, vcsn.expression): e = vcsn.context(ctx).expression(e, identities='trivial') if name: e_named = e.name(name) else: e_named = e a_norm = e_named.derived_term() vcsn.setenv(NAIVE_MUL=1, NAIVE_STAR=1) a_denorm = e_named.derived_term() vcsn.setenv(NAIVE_MUL=0, NAIVE_STAR=0) return vcsn.table([['Expression', 'Denormalized', 'Normal'], [e, a_denorm, a_norm]]) compare('a*b*c*')
Expression Denormalized Normal
a(bc){a}^{*} \, \left({b}^{*} \, {c}^{*}\right)
compare('(<1/2>\e)*')
Expression Denormalized Normal
(12ε)\left( \left\langle \frac{1}{2} \right\rangle \,\varepsilon\right)^{*}
compare('(a*b* + <-1>\e)*', name='E')
Expression Denormalized Normal
(ab+1ε)\left({a}^{*} \, {b}^{*} + \left\langle -1 \right\rangle \,\varepsilon\right)^{*}
compare('((<1/2>\e)* + <-2>\e)*', name='E')
Expression Denormalized Normal
((12ε)+2ε)\left(\left( \left\langle \frac{1}{2} \right\rangle \,\varepsilon\right)^{*} + \left\langle -2 \right\rangle \,\varepsilon\right)^{*}
compare('((\e|ab @ ab|\e) + <-1>\e)*', ctx='lat<lan, lan>, q', name='E')
Expression Denormalized Normal
(ε|ab@ab|ε+1ε)\left( \left. \varepsilon \middle| a \, b \right. @ \left. a \, b \middle| \varepsilon \right. + \left\langle -1 \right\rangle \,\varepsilon\right)^{*}

Section 6.2: Discussion on Identities

vcsn.setenv(DENORM=0, OLDWAY=0) def dterm(e): '''The derived-term of `e`, or the first line of the error if it fails.''' try: return e.derived_term() except RuntimeError as e: return 'Error: ' + str(e).split('\n')[0] def compare(e, ctx='lan, q'): exp = vcsn.context(ctx).expression return vcsn.table([['No identities: Expression', 'No identities: Automaton'], [exp(e, 'none'), dterm(exp(e, 'none'))], ['Trivial identities: Expression', 'Trivial identities: Automaton'], [exp(e, 'trivial'), dterm(exp(e, 'trivial'))]]) compare('a*')
No identities: Expression No identities: Automaton
a{a}^{*}
Trivial identities: Expression Trivial identities: Automaton
a{a}^{*}
compare('a + ⟨0⟩\e* + \z\e*')
No identities: Expression No identities: Automaton
(a+0ε)+ε\left(a + \left\langle 0 \right\rangle \,{\varepsilon}^{*}\right) + \emptyset \, {\varepsilon}^{*} Error: Q: value is not starrable: 1
Trivial identities: Expression Trivial identities: Automaton
aa
compare('abc\z')
No identities: Expression No identities: Automaton
a(b(c))a \, \left(b \, \left(c \, \emptyset\right)\right)
Trivial identities: Expression Trivial identities: Automaton
\emptyset

Runtime Performances

We compare the quality of the generated automata (smaller is better) and the duration of the generation procedure (again, smaller is better). Vcsn feature two generation procedures for multitape expressions: derived-term, and "inductive".

"Inductive" is a simple recursive translation of the rational expression that applies the corresponding operation on the automata. For single-tape expressions, it uses the "standard" operations on automata, which are the ones used to implement the expression.standard algorithm. The comparison will be performed on twenty randomly generated expressions.

zmin2 = vcsn.context('lat<lan, lan>, zmin') from vcsn.tools import _timeit def timeit(fun): 'Run `fun` a number of times, and return its fastest run in milliseconds.' return '{}ms'.format(round(_timeit(lambda: fun())[1])) title = ['Rational Expression', 'DT: transitions', 'Ind: transitions', 'DT: states', 'Ind: states', 'DT: duration', 'Ind: duration'] def compare(e): # Make sure this is an object expression, not just a string. if not isinstance(e, vcsn.expression): e = zmin2.expression(e) # Compute its derived-term automaton. a1 = e.automaton('expansion') t1 = timeit(lambda: e.automaton('expansion')) # Compute another automaton by mapping operators to one of their natural implementation. # In the case of single-tape automata, this yield the standard (aka Glushkov) automaton. a2 = e.automaton('inductive') t2 = timeit(lambda: e.automaton('inductive')) # Return their numbers of states. return [e, a1.info('number of transitions'), a2.info('number of transitions'), a1.state_number(), a2.state_number(), t1, t2]
# ignore cell zmin2 = vcsn.context('lat<lan(ab), lan(ab)>, zmin') res = [title] for i in range(20): e = zmin2.random_expression('+, ., *=.2, w., .w, w="min=0, max=3", |=.5, @', length=20) c = compare(e) res.append(c) vcsn.table(res)
Rational Expression DT: transitions Ind: transitions DT: states Ind: states DT: duration Ind: duration
(εb)(εa)+3a|a\left(\varepsilon|b\right) \, \left(\varepsilon|a\right) + \left. \left\langle 3 \right\rangle \,a \middle| a \right. 3 3 3 4 33ms 30ms
(ε+εb+aa)(bε)@1(2(ab)|2(ε+a))\left(\varepsilon + \varepsilon|b + a|a\right) \, \left(b|\varepsilon\right)@ \left\langle 1 \right\rangle \,\left( \left. \left\langle 2 \right\rangle \,\left(a \, b\right) \middle| \left\langle 2 \right\rangle \,\left(\varepsilon + a\right) \right. \right) 0 5 0 6 48ms 90ms
(bb)((εb)((ε+εb)@εa)@(εa+ba))\left(b|b\right) \, \left(\left(\varepsilon|b\right) \, \left(\left(\varepsilon + \varepsilon|b\right)@\varepsilon|a\right)@\left(\varepsilon|a + b|a\right)\right) 0 3 0 4 31ms 75ms
6((5(ba))|(ε+a)) \left\langle 6 \right\rangle \,\left( \left. \left( \left\langle 5 \right\rangle \,\left(b \, a\right)\right)^{*} \middle| \left(\varepsilon + {a}^{*}\right) \right. \right) 11 11 6 6 148ms 46ms
4((εb)(2ε+1(a2)|(1ε+a))) \left\langle 4 \right\rangle \,\left(\left(\varepsilon|b\right) \, \left( \left\langle 2 \right\rangle \,\varepsilon + \left. \left\langle 1 \right\rangle \,\left({a}^{2}\right) \middle| \left( \left\langle 1 \right\rangle \,\varepsilon + a\right) \right. \right)^{*}\right) 4 7 3 5 48ms 65ms
ParseError: KaTeX parse error: Undefined control sequence: \varepsilon@ at position 45: … \,\left(\left(\̲v̲a̲r̲e̲p̲s̲i̲l̲o̲n̲@̲\left(a|\vareps… 0 0 0 3 13ms 76ms
3(1(2ε+ab)@2ε|(ε+b)) \left\langle 3 \right\rangle \,\left( \left\langle 1 \right\rangle \,\left( \left\langle 2 \right\rangle \,\varepsilon + a|b\right)@ \left. \left\langle 2 \right\rangle \,\varepsilon \middle| \left(\varepsilon + b\right) \right. \right) 1 1 2 2 36ms 50ms
(6(ε+a+b))|2(a+(3b)) \left. \left( \left\langle 6 \right\rangle \,\left(\varepsilon + a + b\right)\right)^{*} \middle| \left\langle 2 \right\rangle \,\left(a + \left( \left\langle 3 \right\rangle \,b\right)^{*}\right) \right. 16 27 5 9 153ms 61ms
2(b|3b@(ε+bb)(bε)) \left\langle 2 \right\rangle \,\left( \left. b \middle| \left\langle 3 \right\rangle \,b \right. @\left(\varepsilon + b|b\right) \, \left(b|\varepsilon\right)\right) 1 2 2 3 33ms 52ms
5((ε+8b)|4(ε+a)) \left\langle 5 \right\rangle \,\left( \left. \left(\varepsilon + \left\langle 8 \right\rangle \,b\right) \middle| \left\langle 4 \right\rangle \,\left(\varepsilon + a\right) \right. \right) 3 3 2 4 40ms 34ms
ε|5(aba) \left. \varepsilon \middle| \left\langle 5 \right\rangle \,\left(a \, b \, a\right) \right. 3 3 4 4 45ms 29ms
3(1a+ε)|(ε+b) \left. \left\langle 3 \right\rangle \,\left( \left\langle 1 \right\rangle \,a + {\varepsilon}^{*}\right) \middle| \left(\varepsilon + b\right) \right. 3 3 2 4 38ms 30ms
6(3(ba)+5((εa)2(ba))) \left\langle 6 \right\rangle \,\left( \left\langle 3 \right\rangle \,\left(b|a\right) + \left\langle 5 \right\rangle \,\left(\left(\varepsilon|a\right)^{2} \, \left(b|a\right)\right)\right) 4 4 4 5 29ms 42ms
3((3b)|ε@2ε|8a) \left\langle 3 \right\rangle \,\left( \left. \left( \left\langle 3 \right\rangle \,b\right)^{*} \middle| \varepsilon \right. @ \left. \left\langle 2 \right\rangle \,\varepsilon \middle| \left\langle 8 \right\rangle \,a \right. \right) 3 4 3 4 70ms 50ms
4(bε)+8((ab)(εb+aε)) \left\langle 4 \right\rangle \,\left(b|\varepsilon\right) + \left\langle 8 \right\rangle \,\left(\left(a|b\right) \, \left(\varepsilon|b + a|\varepsilon\right)\right) 4 4 3 5 25ms 37ms
\emptyset 0 0 0 1 11ms 2ms
5ε|b \left. \left\langle 5 \right\rangle \,\varepsilon \middle| {b}^{*} \right. 2 2 2 2 47ms 15ms
ε\varepsilon 0 0 1 1 13ms 3ms
ε+ab+7(ε+(bε)(ε+εa))\varepsilon + a|b + \left\langle 7 \right\rangle \,\left(\varepsilon + \left(b|\varepsilon\right) \, \left(\varepsilon + \varepsilon|a\right)^{*}\right) 3 4 3 4 26ms 55ms
3(εa+aa+1ε|1a) \left\langle 3 \right\rangle \,\left(\varepsilon|a + a|a + \left. \left\langle 1 \right\rangle \,\varepsilon \middle| \left\langle 1 \right\rangle \,a \right. \right) 2 3 2 4 30ms 35ms

Unfortunately, random expressions are rarely interesting (as can be seen by the number of transitions).

Now we compare the behavior of both algorithms on a familly of rational expressions: n[ab](ab)n[ab]n \mapsto [ab]^* (a|b)^n [ab]^*.

res = [title] for i in range(20): e = zmin2.expression('[ab]* (a|b){{{}}} [ab]*'.format(i)) res.append(compare(e)) vcsn.table(res)
Rational Expression DT: transitions Ind: transitions DT: states Ind: states DT: duration Ind: duration
(aa+bb)2{\left(a|a + b|b\right)^{*}}^{2} 6 16 2 5 36ms 45ms
(aa+bb)(ab)(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right) \, \left(a|a + b|b\right)^{*} 5 15 2 6 31ms 56ms
(aa+bb)(ab)2(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{2} \, \left(a|a + b|b\right)^{*} 6 16 3 7 35ms 68ms
(aa+bb)(ab)3(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{3} \, \left(a|a + b|b\right)^{*} 7 17 4 8 42ms 82ms
(aa+bb)(ab)4(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{4} \, \left(a|a + b|b\right)^{*} 8 18 5 9 45ms 95ms
(aa+bb)(ab)5(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{5} \, \left(a|a + b|b\right)^{*} 9 19 6 10 49ms 109ms
(aa+bb)(ab)6(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{6} \, \left(a|a + b|b\right)^{*} 10 20 7 11 54ms 123ms
(aa+bb)(ab)7(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{7} \, \left(a|a + b|b\right)^{*} 11 21 8 12 60ms 141ms
(aa+bb)(ab)8(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{8} \, \left(a|a + b|b\right)^{*} 12 22 9 13 63ms 155ms
(aa+bb)(ab)9(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{9} \, \left(a|a + b|b\right)^{*} 13 23 10 14 69ms 174ms
(aa+bb)(ab)10(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{10} \, \left(a|a + b|b\right)^{*} 14 24 11 15 73ms 189ms
(aa+bb)(ab)11(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{11} \, \left(a|a + b|b\right)^{*} 15 25 12 16 76ms 202ms
(aa+bb)(ab)12(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{12} \, \left(a|a + b|b\right)^{*} 16 26 13 17 83ms 220ms
(aa+bb)(ab)13(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{13} \, \left(a|a + b|b\right)^{*} 17 27 14 18 84ms 238ms
(aa+bb)(ab)14(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{14} \, \left(a|a + b|b\right)^{*} 18 28 15 19 103ms 304ms
(aa+bb)(ab)15(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{15} \, \left(a|a + b|b\right)^{*} 19 29 16 20 101ms 299ms
(aa+bb)(ab)16(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{16} \, \left(a|a + b|b\right)^{*} 20 30 17 21 103ms 314ms
(aa+bb)(ab)17(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{17} \, \left(a|a + b|b\right)^{*} 21 31 18 22 107ms 344ms
(aa+bb)(ab)18(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{18} \, \left(a|a + b|b\right)^{*} 22 32 19 23 109ms 356ms
(aa+bb)(ab)19(aa+bb)\left(a|a + b|b\right)^{*} \, \left(a|b\right)^{19} \, \left(a|a + b|b\right)^{*} 23 33 20 24 130ms 370ms

Section 6.6: Discussion on the Performances

In this section, we compare the size of automata generated either using the "standard automaton" construction (aka, Glushkov automata), or the expansion-based derived-term automaton as exposed in the paper.

def exp(e, ctx=None): '''Make an expression from `e`, using the context `ctx` if `e` is not already an expression.''' if isinstance(e, vcsn.expression): return e else: if not isinstance(ctx, vcsn.context): ctx = vcsn.context(ctx) return ctx.expression(e) def compare_one(e): '''Compare the sizes of the derived-term, denormalized derived-term, and inductive automata from exprssion `e`.''' e = exp(e, ctx=zmin2) ind = e.inductive() dte = e.derived_term() vcsn.setenv(OLDWAY=1, DENORM=1) den = e.derived_term() vcsn.setenv(OLDWAY=0, DENORM=0) return [e, dte.info('number of states'), dte.info('number of transitions'), den.info('number of states'), den.info('number of transitions'), ind.info('number of states'), ind.info('number of transitions')] def compare(*es): '''Compare the sizes of the derived-term, denormalized derived-term, and inductive automata for each expression in `es`.''' res = [['Expression', 'DTerm states', 'Dterm transitions', 'Denorm DTerm states', 'Denorm Dterm transitions', 'Inductive states', 'Inductive transitions']] for e in es: res.append(compare_one(e)) return res zmin = vcsn.context('lan, zmin') zmin2 = zmin|zmin eset2 = vcsn.context('lat<lan, lan>, expressionset<lan, q>') q = vcsn.context('lan, q') q3 = vcsn.context('lat<lan, lan, lan>, q') res = compare(# Introduction exp('([ab] + ⟨1⟩(\e|[ab] + [ab]|\e))∗', zmin2), exp('[ab]∗ (⟨1⟩(\e|[ab] + [ab]|\e) + ⟨2⟩(a|b + b|a))∗', zmin2), exp('([ab] + ⟨1⟩(\e|I + [ab]|S))∗', zmin2), exp('([ab] + I|[ab] + S|\e)∗', zmin2), exp('(([ab] + ⟨1⟩(\e|I + [ab]|S))∗) @ (([ab] + I|[ab] + S|\e)∗)', zmin2), exp('⟨4⟩ade*|x + ⟨3⟩bde*|x + ⟨2⟩ace*|xy + ⟨6⟩bce*|xy', zmin2), exp('a + ⟨2⟩bc∗', ctx=zmin), # Section 3. exp('a*|b*|c*', ctx=q3), # Example 4. exp('a*|b*|c*|d*|e*', ctx='lat<lan(a), lan(b), lan(c), lan(d), lan(e)>, q'), # Example 4 exp('(a{+}|x + b{+}|y)*', zmin2), # Example 5 exp('(⟨k⟩\e|a)∗ @ (⟨h⟩aa|\e)∗', ctx=eset2), # Example 8, Section 5.3, exp('a*b*c*', ctx=q), # Section 6.1 exp('(<1/2>\\e)*', ctx=q), # Section 6.1 exp('(a*b* + <-1>\\e)*', ctx=q), # Section 6.1 exp('((<1/2>\\e)* + <-2>\\e)*', ctx=q), # Section 6.1 # exp('((\\e|ab @ ab|\\e) + <-1>\\e)*', ctx='lat<lan, lan>, q'), # Section 6.1, invalid automaton. ) t = vcsn.table(res) t
Expression DTerm states Dterm transitions Denorm DTerm states Denorm Dterm transitions Inductive states Inductive transitions
(aa+bb+1(ε|(a+b)+(a+b)|ε))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left( \left. \varepsilon \middle| \left(a + b\right) \right. + \left. \left(a + b\right) \middle| \varepsilon \right. \right)\right)^{*} 1 6 1 6 7 42
(aa+bb)(2(ab+ba)+1(ε|(a+b)+(a+b)|ε))\left(a|a + b|b\right)^{*} \, \left( \left\langle 2 \right\rangle \,\left(a|b + b|a\right) + \left\langle 1 \right\rangle \,\left( \left. \varepsilon \middle| \left(a + b\right) \right. + \left. \left(a + b\right) \middle| \varepsilon \right. \right)\right)^{*} 2 14 2 14 9 60
(aa+bb+1(εI+(a+b)|S))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left(\varepsilon|I + \left. \left(a + b\right) \middle| S \right. \right)\right)^{*} 1 5 1 5 6 30
(Sε+aa+bb+I|(a+b))\left(S|\varepsilon + a|a + b|b + \left. I \middle| \left(a + b\right) \right. \right)^{*} 1 5 1 5 6 30
(aa+bb+1(εI+(a+b)|S))@(Sε+aa+bb+I|(a+b))\left(a|a + b|b + \left\langle 1 \right\rangle \,\left(\varepsilon|I + \left. \left(a + b\right) \middle| S \right. \right)\right)^{*}@\left(S|\varepsilon + a|a + b|b + \left. I \middle| \left(a + b\right) \right. \right)^{*} 1 6 11 26 7 42
4(ade)|x+3(bde)|x+2(ace)|xy+6(bce)|xy \left. \left\langle 4 \right\rangle \,\left(a \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 3 \right\rangle \,\left(b \, d \, {e}^{*}\right) \middle| x \right. + \left. \left\langle 2 \right\rangle \,\left(a \, c \, {e}^{*}\right) \middle| x \, y \right. + \left. \left\langle 6 \right\rangle \,\left(b \, c \, {e}^{*}\right) \middle| x \, y \right. 4 7 4 7 13 16
a+2(bc)a + \left\langle 2 \right\rangle \,\left(b \, {c}^{*}\right) 3 3 3 3 4 4
a|b|c \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \right. 7 19 7 19 8 26
a|b|c|d|e \left. {a}^{*} \middle| {b}^{*} \middle| {c}^{*} \middle| {d}^{*} \middle| {e}^{*} \right. 31 211 31 211 32 242
(aa|x+bb|y)\left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*} 3 8 3 8 5 14
(kε|a)@(haa|ε)\left( \left. \left\langle k \right\rangle \,\varepsilon \middle| a \right. \right)^{*}@\left( \left. \left\langle h \right\rangle \,a \, a \middle| \varepsilon \right. \right)^{*} 2 2 5 8 3 3
abc{a}^{*} \, {b}^{*} \, {c}^{*} 3 6 3 6 4 9
(12ε)\left( \left\langle \frac{1}{2} \right\rangle \,\varepsilon\right)^{*} 1 0 1 0 1 0
(1ε+ab)\left( \left\langle -1 \right\rangle \,\varepsilon + {a}^{*} \, {b}^{*}\right)^{*} 3 6 3 6 3 6
(2ε+(12ε))\left( \left\langle -2 \right\rangle \,\varepsilon + \left( \left\langle \frac{1}{2} \right\rangle \,\varepsilon\right)^{*}\right)^{*} 1 0 1 0 1 0