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.

See also:

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 [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)))
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]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 1 1 0->1 a 3 3 0->3 b 1->F1 1->1 a 1->3 b 3->F3 3->1 a 3->3 b
In [5]:
r.star_normal_form().standard()
Out[5]:
%3 I0 0 0 I0->0 F0 F1 F3 0->F0 1 1 0->1 a 3 3 0->3 b 1->F1 1->1 a 1->3 b 3->F3 3->1 a 3->3 b