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:

Examples

In [1]:
import vcsn
import pandas as pd
pd.options.display.max_colwidth = 0
In [2]:
a = vcsn.B.expression('ab*c').standard()
a
Out[2]:
%3 I0 0 0 I0->0 F4 1 1 0->1 a 3 3 1->3 b 4 4 1->4 c 3->3 b 3->4 c 4->F4
In [3]:
a.expression(algo = "naive")
Out[3]:
$a \, c + a \, b \, {b}^{*} \, c$
In [4]:
a.expression(algo = "best")
Out[4]:
$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.

In [5]:
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}')
Out[5]:
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.

In [6]:
a
Out[6]:
%3 I0 0 0 I0->0 F4 1 1 0->1 a 3 3 1->3 b 4 4 1->4 c 3->3 b 3->4 c 4->F4
In [7]:
a.expression('trivial')
Out[7]:
$a \, \left(c + \left(b \, {b}^{*}\right) \, c\right)$
In [8]:
a.expression('linear')
Out[8]:
$a \, \left(c + b \, {b}^{*} \, c\right)$