Processing math: 100%

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(*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 [2]:
snf('a**', 'a?{+}', '(a+b*)*', '(a*+b*)*', '(ab)*', '(ab?)*', '(a?b?)*', '(a*b*c*)**')
Out[2]:
aa(ε+a)(ε+a)(ε+a)a(a+b)(a+b)(a+b)(a+b)(ab)(ab)(a(ε+b))(a(ε+b))((ε+a)(ε+b))(a+b)(abc)(a+b+c)

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

In [3]:
snf('a*', '(a+b+c)*')
Out[3]:
aa(a+b+c)(a+b+c)

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