GAP (Automata) - Chapter 4: Automata versus rational expressions

A remarkable theorem due to Kleene shows that a language is recognized by a finite automaton precisely when it may be given by means of a rational expression, i.e. is a rational language.

An automaton and a rational expression are said to be equivalent when both represent the same language. In this chapter we describe functions to go from automata to equivalent rational expressions and vice-versa.

4.1 From automata to rational expressions

4.1-1 AutomatonToRatExp

From a finite automaton, FAtoRatExp, AutToRatExp and AutomatonToRatExp, which are synonyms, compute one equivalent rational expression, using the state elimination algorithm.

gap> x:=Automaton("det",4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;
gap> FAtoRatExp(x);
(aUb)(aUb)U@
gap> aut:=Automaton("det",4,"xy",[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;
gap> FAtoRatExp(aut);
(xUy)(xUy)U@

4.2 From rational expression to automata

4.2-1 RatExpToNDAut

gap> r:=RationalExpression("aUab");
aUab
gap> Display(RatExpToNDAut(r));
   |  1    2       3    4
--------------------------------
 a |                   [ 1, 2 ]
 b |      [ 3 ]
Initial state:    [ 4 ]
Accepting states: [ 1, 3 ]
gap> r:=RationalExpression("xUxy"); 
xUxy
gap> Display(RatExpToNDAut(r));    
   |  1    2       3    4
--------------------------------
 x |                   [ 1, 2 ]   
 y |      [ 3 ]                   
Initial state:    [ 4 ]
Accepting states: [ 1, 3 ]

4.2-2 RatExpToAutomaton

Given a rational expression R, these functions, which are synonyms, use RatExpToNDAut (4.2-1)) to compute the equivalent NFA and then returns the equivalent minimal DFA

gap> r:=RationalExpression("@U(aUb)(aUb)");
@U(aUb)(aUb)
gap> Display(RatExpToAut(r));
   |  1  2  3  4
-----------------
 a |  3  1  3  2
 b |  3  1  3  2
Initial state:    [ 4 ]
Accepting states: [ 1, 4 ]
gap> r:=RationalExpression("@U(0U1)(0U1)");
@U(0U1)(0U1)
gap> Display(RatExpToAut(r));              
   |  1  2  3  4  
-----------------
 0 |  3  1  3  2  
 1 |  3  1  3  2  
Initial state:    [ 4 ]
Accepting states: [ 1, 4 ]

4.3 Some tests on automata

This section describes functions that perform tests on automata, rational expressions and their accepted languages.

4.3-1 IsEmptyLang

This function tests if the language given through a rational expression or an automaton R is the empty language.

gap> r := RationalExpression("empty_set");
empty_set
gap> IsEmptyLang(r);
true
gap> r := RationalExpression("aUb");
aUb
gap> IsEmptyLang(r);
false

4.3-2 IsFullLang

This function tests if the language given through a rational expression or an automaton R represents the Kleene closure of the alphabet of R .

gap> r:=RationalExpression("aUb");
aUb
gap> IsFullLang(r);
false
gap> r:=RationalExpression("(aUb)*");
(aUb)*
gap> IsFullLang(r);
true

4.3-3 AreEqualLang

These functions, which are synonyms, test if the automata or rational expressions A1 and A2 are equivalent, i.e. represent the same language. This is performed by checking that the corresponding minimal automata are isomorphic. Note hat this cannot happen if the alphabets are different.

gap> x := Automaton("det",4,"ab",[ [ 0, 1, 3, 4 ], [ 0, 1, 2, 0 ] ],[ 2 ],[ 1, 2, 3, 4 ] );;
gap> y := Automaton("det",4,"ab",[ [ 1, 3, 4, 0 ], [ 0, 3, 4, 0 ] ],[ 3 ],[ 1, 3, 4 ]);;
gap> z := Automaton("det",4,"ab",[ [ 0, 4, 0, 0 ], [ 1, 3, 4, 0 ] ],[ 2 ],[ 1, 3, 4 ]);;
gap> AreEquivAut(x, y);
true
gap> AreEquivAut(x, z);
false
gap> a:=RationalExpression("(aUb)*ab*");
(aUb)*ab*
gap> b:=RationalExpression("(aUb)*");
(aUb)*
gap> AreEqualLang(a, b);
false
gap> a:=RationalExpression("(bUa)*");
(bUa)*
gap> AreEqualLang(a, b);
true
gap> x:=RationalExpression("(1U0)*");
(1U0)*
gap> AreEqualLang(a, x);  
The given languages are not over the same alphabet
false

4.3-4 IsContainedLang

Tests if the language represented (through an automaton or a rational expression) by R1 is contained in the language represented (through an automaton or a rational expression) by R2 .

gap> r:=RationalExpression("aUab");
aUab
gap> s:=RationalExpression("a","ab");
a
gap> IsContainedLang(s,r);
true
gap> IsContainedLang(r,s);
false

4.3-5 AreDisjointLang

Tests if the languages represented (through automata or a rational expressions) by R1 and R2 are disjoint.

gap> r:=RationalExpression("aUab");;
gap> s:=RationalExpression("a","ab");;
gap> AreDisjointLang(r,s);
false

4 Automata versus rational expressions