# Rational expressions¶

In :
# We disable autosave for technical reasons.
# Replace 0 by 120 in next line to restore default.
%autosave 0

Autosave disabled

In :
import awalipy # If import fails, check that
# Python version used as Jupyter
# kernel matches the one
# Awalipy was compiled with.

[Warning] The python module awalipy relies on compilation executed "on-the-fly" depending on the context (type of weights, of labels, etc.). As a result, the very first call to a given function in a given context may take up to 10 seconds.


## Creating a RatExp¶

When parsing a rational expression operator precedence is : star > concatenation > union . In other words,

• a+(b*) = a+b* != (a+b)*
• a(b*) = ab* != (ab)*
• a+(bc) = a+bc != (a+b)c
In :
e = awalipy.RatExp("(a+bc)c*(ab)*")
e

Out:
(a+bc)c*(ab)*

By default, the alphabet of a rational expression is the set of all letters appearing in it. However the alphabet may be increased artifically as follows.

In :
f = awalipy.RatExp("(a+b)(c*+a)*", alphabet="abcd")
f

Out:
(a+b)(c*+a)*

Displaying a rational expression as a tree.

In :
e.display()


## Union¶

In :
e+f

Out:
(a+bc)c*(ab)*+(a+b)(c*+a)*
In :
e+=e
e

Out:
(a+bc)c*(ab)*+(a+bc)c*(ab)*

## Concatenation¶

In :
e^f

Out:
((a+bc)c*(ab)*+(a+bc)c*(ab)*)((a+b)(c*+a)*)
In :
e^="abc*"
e

Out:
((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*)

## Star¶

In :
e.star()

Out:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*
In :
e.star_here()
e

Out:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*

## Star normal form and star height¶

In :
e.star_height()

Out:
2
In :
e.star_normal_form()

Out:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*

## Expand¶

The method expand distribute union and concatenation as much as possible.

In :
awalipy.RatExp("(a+bc)(d+e)(f+g)*").expand()

Out:
ad(f+g)*+ae(f+g)*+bcd(f+g)*+bce(f+g)*

## Expressions to automata¶

By default, awali uses the derived term algorithm.

In :
A = e.exp_to_aut()
A.display()


The states of A are indeed all the derived expressions of e. It may be displayed by setting to True the optional argument history.

In :
A.display(horizontal=False,history=True)


For convenience, one may give an expression to the constructor of an automaton. Derived term is called.

In :
A = awalipy.Automaton(awalipy.RatExp("01*0*"))
A.display()


Awali implements other algorithms for transforming expressions to automata, such as thompson or standard

In :
g = awalipy.RatExp("1*0")
g.thompson().display()

In :
g.standard().display()

In [ ]:



## Weighted rational expression¶

Weights must be put between "<>" and weights takes precedence over other operators:

• <-1>a* = (<-1>a)* != <-1>(a*)
• <-1>ab = (<-1>a)b != <-1>(ab)
• <-1>a+b = (<-1>a)+b != <-1>(a+b)

The weighset must be given as a second argument at creation.

In :
h = awalipy.RatExp("(<1>a*+<-1>(b*))","Z")
h

Out:
a*+<-1>(b*)
In :
h.display()


For the sake of convenience, a weight alone (ie. "<-1>") is considered as a valid representation of the word epsilon with the given weight (ie. "<-1>\e").

In :
awalipy.RatExp("<-2>","Z")

Out:
<-2>\e

Union, concatenation and star works in the same way for weighted rational expressions.

In :
i = h ^ h + ("<-1>" ^ h).star()
i

Out:
(a*+<-1>(b*))(a*+<-1>(b*)+<-1>(a*+<-1>(b*))*)

### Weighted expression to weighted automaton¶

For aut_to_exp or standard to work, the rational expression needs to be valid. An expression is valid if, in every sub-expression, the weight of $\epsilon$ is well defined. For instance the expression *(< 2 >\e)** is not valid (with weightset $(\mathbb{Z},+,\times$))

In :
i.is_valid()

Out:
True
In :
i.exp_to_aut().display()


The method thompson() is not suitable for weighted expressions.

Indeed, let us consider the following valid expression g:

In :
g = awalipy.RatExp("(<1>(a*)+<-1>(b*))*","Z")
g.is_valid()

Out:
True
In :
G = g.thompson()
G.display(horizontal=False)


In this case, thompson produces an automaton that is not valid.

In :
G.is_valid()

Out:
False

## Other functions¶

The method constant_term gives the weight of epsilon

In :
j = awalipy.RatExp("(<1/4>(a*)+<1/4>(b*))*","Q")
j

Out:
(<1/4>(a*)+<1/4>(b*))*
In :
j.constant_term()

Out:
'2'

In :
j.get_weightset()

Out:
Q