# 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.

Caveat:

• Although the notion of "star normal form" is perfectly valid for weighted expressions, this implementation is unable to compute the star normal form in this case. One could work-around this limitation by running exp.standard().expression().

## Examples¶

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

In :
import vcsn
from IPython.display import Latex

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

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

Out:
\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 :
snf('a*', '(a+b+c)*')

Out:
\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 :
r = vcsn.b.expression('(a*b*)*')
r.standard()

Out:
In :
r.star_normal_form().standard()

Out: