# Rational expressions¶

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

Autosave disabled

In [2]:
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 one minute.


## 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 [3]:
e = awalipy.RatExp("(a+bc)c*(ab)*")
e

Out[3]:
(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 [4]:
f = awalipy.RatExp("(a+b)(c*+a)*", alphabet="abcd")
f

Out[4]:
(a+b)(c*+a)*

Displaying a rational expression as a tree.

In [5]:
e.display()


## Union¶

In [6]:
e+f

Out[6]:
(a+bc)c*(ab)*+(a+b)(c*+a)*
In [7]:
e+=e
e

Out[7]:
(a+bc)c*(ab)*+(a+bc)c*(ab)*

## Concatenation¶

In [8]:
e^f

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

Out[9]:
((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*)

## Star¶

In [10]:
e.star()

Out[10]:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*
In [11]:
e.star_here()
e

Out[11]:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*

## Star normal form and star height¶

In [12]:
e.star_height()

Out[12]:
2
In [13]:
e.star_normal_form()

Out[13]:
(((a+bc)c*(ab)*+(a+bc)c*(ab)*)(abc*))*

## Expand¶

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

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

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

## Expressions to automata¶

By default, awali uses the derived term algorithm.

In [15]:
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 [16]:
A.display(horizontal=False)


For convenience, one may give an expression to the constructor of an automaton.

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


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

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

In [19]:
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 [20]:
h = awalipy.RatExp("(<1>a*+<-1>(b*))","Z")
h

Out[20]:
a*+<-1>(b*)
In [21]:
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 [22]:
awalipy.RatExp("<-2>","Z")

Out[22]:
<-2>\e

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

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

Out[23]:
(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 [24]:
i.is_valid()

Out[24]:
True
In [25]:
i.exp_to_aut().display()


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

Indeed, let us consider the following valid expression g:

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

Out[26]:
True
In [27]:
G = g.exp_to_aut(method="thompson")
G.display(horizontal=False)


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

In [28]:
G.is_valid()

Out[28]:
False

## Other functions¶

The method constant_term gives the weight of epsilon

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

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

Out[30]:
'12'

In [31]:
j.get_weightset()

Out[31]:
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 [32]:
j.get_kind()

Out[32]:
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 [33]:
awalipy.RatExp.ZERO

Out[33]:
ZERO~0
In [34]:
awalipy.RatExp.ONE

Out[34]:
ONE~1
In [35]:
awalipy.RatExp.ATOM

Out[35]:
ATOM~2
In [36]:
awalipy.RatExp.SUM

Out[36]:
SUM~3
In [37]:
awalipy.RatExp.PROD

Out[37]:
PROD~4
In [38]:
awalipy.RatExp.STAR

Out[38]:
STAR~5

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

In [39]:
awalipy.RatExpKind.instances

Out[39]:
[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 [40]:
awalipy.RatExpKind.of["STAR"]

Out[40]:
STAR~5
In [41]:
str(awalipy.RatExp.PROD)

Out[41]:
'PROD'
In [42]:
awalipy.RatExpKind.of[2]

Out[42]:
ATOM~2
In [43]:
int(awalipy.RatExp.ATOM)

Out[43]:
2

### Sub-expression¶

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

In [44]:
j.children()

Out[44]:
[<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 [45]:
k = awalipy.RatExp('a')
k.get_kind()

Out[45]:
ATOM~2
In [46]:
k.children()

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

Out[47]:
ATOM~2
In [48]:
l.children()

Out[48]:
['a']

### Weights¶

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

In [49]:
j.display()

In [50]:
j.weight()

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

In [52]:
k.weight()

Out[52]:
['true', 'true']
In [53]:
l.display()

In [54]:
l.weight()

Out[54]:
['2', '1']

### Unpack a RatExp¶

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

In [55]:
j.display()
j

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

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


In [ ]:


In [ ]:


In [ ]:


In [ ]: