`expression`.`star_normal_form()`

Compute the star normal form of a (Boolean) expression: an equivalent expression where the star operator is applied only on proper expressions (i.e., expressions whose constant term is null).

Preconditions:

The expression is Boolean

Postconditions:

The Result is equivalent to the input expression
The standard automata of the Result and of the input are isomorphic.

Examples

The following function allows to display nicely expressions and their star-normal form.



In [1]:

    
import vcsn
from IPython.display import Latex

def snf(*rs):
    eqs = []
    for r in rs:
        r = vcsn.b.expression(r)
        eqs.append(r'{r} &\Rightarrow {snf}'
                   .format(r = r.format('latex'),
                           snf = r.star_normal_form().format('latex')))
    return Latex(r'''\begin{{aligned}}
        {eqs}
    \end{{aligned}}'''.format(eqs = r'\\'.join(eqs)))









    



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



In [2]:

    
snf('a**', 'a?{+}', '(a+b*)*', '(a*+b*)*', '(ab)*', '(ab?)*', '(a?b?)*', '(a*b*c*)**')









    Out[2]:





\begin{aligned}
        {{a}^{*}}^{*} &\Rightarrow {a}^{*}\\\left(\varepsilon + a\right) \, \left(\varepsilon + a\right)^{*} &\Rightarrow \left(\varepsilon + a\right) \, {a}^{*}\\\left(a + {b}^{*}\right)^{*} &\Rightarrow \left(a + b\right)^{*}\\\left({a}^{*} + {b}^{*}\right)^{*} &\Rightarrow \left(a + b\right)^{*}\\\left(a \, b\right)^{*} &\Rightarrow \left(a \, b\right)^{*}\\\left(a \, \left(\varepsilon + b\right)\right)^{*} &\Rightarrow \left(a \, \left(\varepsilon + b\right)\right)^{*}\\\left(\left(\varepsilon + a\right) \, \left(\varepsilon + b\right)\right)^{*} &\Rightarrow \left(a + b\right)^{*}\\{\left({a}^{*} \, {b}^{*} \, {c}^{*}\right)^{*}}^{*} &\Rightarrow \left(a + b + c\right)^{*}
    \end{aligned}

Of course, expressions already in star-normal form are returned unmodified.



In [3]:

    
snf('a*', '(a+b+c)*')









    Out[3]:





\begin{aligned}
        {a}^{*} &\Rightarrow {a}^{*}\\\left(a + b + c\right)^{*} &\Rightarrow \left(a + b + c\right)^{*}
    \end{aligned}

An expression and its star-normal form have the same standard automaton.



In [4]:

    
r = vcsn.b.expression('(a*b*)*')
r.standard()









    Out[4]:



In [5]:

    
r.star_normal_form().standard()









    Out[5]:

expression.star_normal_form()

Examples

`expression`.`star_normal_form()`