# 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

## 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]:
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]:
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)$