expression.star_normal_form.ipynb

Kernel: Python 3

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:

• expression.standard

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.

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

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

$$\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.

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

$$\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.

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

r.star_normal_form().standard()