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

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


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

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

In :
g.exp_to_aut("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 construction.

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.exp_to_aut(method="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("<3>((<1/4>(a*)+<1/4>(b*))*)<2>","Q")
j

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

Out:
'12'

In :
j.get_weightset()

Out:
Q

## Decomposing RatExp's¶

### Kind of RatExp's¶

The method exp.get_kind() gives the top level kind of a RatExp exp. (For instance, below, the top level operator of expression j is the Kleene star.)

In :
j.get_kind()

Out:
STAR~5

The method get_kind() returns an object of RatExpKind, which is a sort of enum. The different instances are accessible as follows.

In :
awalipy.RatExp.ZERO

Out:
ZERO~0
In :
awalipy.RatExp.ONE

Out:
ONE~1
In :
awalipy.RatExp.ATOM

Out:
ATOM~2
In :
awalipy.RatExp.SUM

Out:
SUM~3
In :
awalipy.RatExp.PROD

Out:
PROD~4
In :
awalipy.RatExp.STAR

Out:
STAR~5

The list of all possible instances of RatExpKind can be accessed via RatExpKind.instance.

In :
awalipy.RatExpKind.instances

Out:
[ZERO~0, ONE~1, ATOM~2, SUM~3, PROD~4, STAR~5]

Object of type RatExpKind can be converted to or built from their integer value or their string value as follows.

In :
awalipy.RatExpKind.of["STAR"]

Out:
STAR~5
In :
str(awalipy.RatExp.PROD)

Out:
'PROD'
In :
awalipy.RatExpKind.of

Out:
ATOM~2
In :
int(awalipy.RatExp.ATOM)

Out:
2

### Sub-expression¶

The method ratexp.children() gives the sub-expressions of a RatExp ratexp.

In :
j.children()

Out:
[<1/4>(a*)+<1/4>(b*)]

In the case where the expression is a RatExp.ATOM, then children() gives the held label as string.

In :
k = awalipy.RatExp('a')
k.get_kind()

Out:
ATOM~2
In :
k.children()

Out:
['a']
In :
l = awalipy.RatExp('<2>a','Z')
l.get_kind()

Out:
ATOM~2
In :
l.children()

Out:
['a']

### Weights¶

The method ratexp.weight() gives the left and right weights of a RatExp ratexp.

In :
j.display()

In :
j.weight()

Out:
['3', '2']
In :
k.display()

In :
k.weight()

Out:
['1', '1']
In :
l.display()

In :
l.weight()

Out:
['2', '1']

### Unpack a RatExp¶

The method ratexp.content() gives the full top-level content of a RatExp exp.

In :
j.display()
j

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

Out:
[STAR~5, '3', <1/4>(a*)+<1/4>(b*), '2']
In [ ]:


In [ ]:


In [ ]:


In [ ]:


In [ ]: