automaton.expression.ipynb

Kernel: Python 3

automaton.expression(identities="default", algo="auto")

Apply the Brzozowski-McCluskey procedure, to compute a (basic) expression from an automaton.

Arguments:

• identities: the identities of the resulting expression

• algo: a heuristics to choose the order in which states are eliminated

  • "auto": same as "best"

  • "best": run all the heuristics, and return the shortest result

  • "naive": a simple heuristics which eliminates states with few incoming/outgoing transitions

  • "delgado": choose a state whose removal would add a small expression (number of nodes) to the result

  • "delgado_label": choose a state whose removal would add a small expression (number of labels in the expression) to the result

See also:

• automaton.eliminate_state

• automaton.lift

Examples

import vcsn
import pandas as pd

a = vcsn.B.expression('ab*c').standard()
a

a.expression(algo = "naive")

$a \, c + a \, b \, {b}^{*} \, c$

a.expression(algo = "best")

$a \, \left(c + b \, {b}^{*} \, c\right)$

Unfortunately there is no guarantee that the resulting expression is as simple as one could hope for. Note also that expression.derived_term tends to build automata which give nicer results than expression.standard.

def latex(e):
    return '$' + e.format('latex') + '$'
def example(*es):
    res = [[latex(e),
            latex(e.standard().expression(algo="naive")),
            latex(e.derived_term().expression(algo="naive"))]
           for e in [vcsn.Q.expression(e) for e in es]]
    return pd.DataFrame(res, columns=['Input', 'Via Standard', 'Via Derived Term'])
example('a', 'a+b+a', 'a+b+a', 'ab*c', '[ab]{2}')

	Input	Via Standard	Via Derived Term
0	$a$	$a$	$a$
1	$\left\langle 2 \right\rangle \,a + b$	$\left\langle 2 \right\rangle \,a + b$	$\left\langle 2 \right\rangle \,a + b$
2	$\left\langle 2 \right\rangle \,a + b$	$\left\langle 2 \right\rangle \,a + b$	$\left\langle 2 \right\rangle \,a + b$
3	$a \, {b}^{*} \, c$	$a \, c + a \, b \, {b}^{*} \, c$	$a \, {b}^{*} \, c$
4	$\left(a + b\right)^{2}$	$a \, a + a \, b + b \, a + b \, b$	$\left(a + b\right)^{2}$

Identities

You may pass the desired identities as an argument.

a

a.expression('trivial')

$a \, \left(c + \left(b \, {b}^{*}\right) \, c\right)$

a.expression('linear')

$a \, \left(c + b \, {b}^{*} \, c\right)$