`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









    



:0: FutureWarning: IPython widgets are experimental and may change in the future.



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) \, \left(a + b\right)$
      $a \, a + a \, b + b \, a + b \, b$
      $\left(a + b\right) \, \left(a + b\right)$

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)$

	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) \, \left(a + b\right)$	$a \, a + a \, b + b \, a + b \, b$	$\left(a + b\right) \, \left(a + b\right)$

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

Examples

Identities

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