[1X4 Automata [13Xversus[1X rational expressions[0X 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 [13Xequivalent[0m when both represent the same language. In this chapter we describe functions to go from automata to equivalent rational expressions and [13Xvice-versa[0m. [1X4.1 From automata to rational expressions[0X [1X4.1-1 AutomatonToRatExp [0m [2X> AutomatonToRatExp ( [0X[3XA[0X[2X ) __________________________________________[0Xfunction [2X> AutToRatExp( [0X[3XA[0X[2X ) _________________________________________________[0Xfunction [2X> FAtoRatExp( [0X[3XA[0X[2X ) __________________________________________________[0Xfunction From a finite automaton, [10XFAtoRatExp[0m, [10XAutToRatExp[0m and [10XAutomatonToRatExp[0m, which are synonyms, compute one equivalent rational expression, using the state elimination algorithm. [4X--------------------------- Example ----------------------------[0X [4Xgap> x:=Automaton("det",4,2,[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;[0X [4Xgap> FAtoRatExp(x);[0X [4X(aUb)(aUb)U@[0X [4Xgap> aut:=Automaton("det",4,"xy",[[ 0, 1, 2, 3 ],[ 0, 1, 2, 3 ]],[ 3 ],[ 1, 3, 4 ]);;[0X [4Xgap> FAtoRatExp(aut); [0X [4X(xUy)(xUy)U@[0X [4X------------------------------------------------------------------[0X [1X4.2 From rational expression to automata[0X [1X4.2-1 RatExpToNDAut[0m [2X> RatExpToNDAut( [0X[3XR[0X[2X ) _______________________________________________[0Xfunction Given a rational expression [3XR[0m, computes the equivalent NFA [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RationalExpression("aUab");[0X [4XaUab[0X [4Xgap> Display(RatExpToNDAut(r));[0X [4X | 1 2 3 4[0X [4X--------------------------------[0X [4X a | [ 1, 2 ][0X [4X b | [ 3 ][0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 3 ][0X [4Xgap> r:=RationalExpression("xUxy"); [0X [4XxUxy[0X [4Xgap> Display(RatExpToNDAut(r)); [0X [4X | 1 2 3 4[0X [4X--------------------------------[0X [4X x | [ 1, 2 ] [0X [4X y | [ 3 ] [0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 3 ][0X [4X------------------------------------------------------------------[0X [1X4.2-2 RatExpToAutomaton[0m [2X> RatExpToAutomaton( [0X[3XR[0X[2X ) ___________________________________________[0Xfunction [2X> RatExpToAut( [0X[3XR[0X[2X ) _________________________________________________[0Xfunction Given a rational expression [3XR[0m, these functions, which are synonyms, use [2XRatExpToNDAut[0m ([14X4.2-1[0m)) to compute the equivalent NFA and then returns the equivalent minimal DFA [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RationalExpression("@U(aUb)(aUb)");[0X [4X@U(aUb)(aUb)[0X [4Xgap> Display(RatExpToAut(r));[0X [4X | 1 2 3 4[0X [4X-----------------[0X [4X a | 3 1 3 2[0X [4X b | 3 1 3 2[0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 4 ][0X [4Xgap> r:=RationalExpression("@U(0U1)(0U1)");[0X [4X@U(0U1)(0U1)[0X [4Xgap> Display(RatExpToAut(r)); [0X [4X | 1 2 3 4 [0X [4X-----------------[0X [4X 0 | 3 1 3 2 [0X [4X 1 | 3 1 3 2 [0X [4XInitial state: [ 4 ][0X [4XAccepting states: [ 1, 4 ][0X [4X------------------------------------------------------------------[0X [1X4.3 Some tests on automata[0X This section describes functions that perform tests on automata, rational expressions and their accepted languages. [1X4.3-1 IsEmptyLang[0m [2X> IsEmptyLang( [0X[3XR[0X[2X ) _________________________________________________[0Xfunction This function tests if the language given through a rational expression or an automaton [3X R [0m is the empty language. [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RandomRatExp(2);[0X [4Xempty_set[0X [4Xgap> IsEmptyLang(r);[0X [4Xtrue[0X [4Xgap> r:=RandomRatExp(2);[0X [4XaUb[0X [4Xgap> IsEmptyLang(r);[0X [4Xfalse[0X [4X------------------------------------------------------------------[0X [1X4.3-2 IsFullLang[0m [2X> IsFullLang( [0X[3XR[0X[2X ) __________________________________________________[0Xfunction This function tests if the language given through a rational expression or an automaton [3X R [0m represents the Kleene closure of the alphabet of [3X R [0m . [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RationalExpression("aUb");[0X [4XaUb[0X [4Xgap> IsFullLang(r);[0X [4Xfalse[0X [4Xgap> r:=RationalExpression("(aUb)*");[0X [4X(aUb)*[0X [4Xgap> IsFullLang(r);[0X [4Xtrue[0X [4X------------------------------------------------------------------[0X [1X4.3-3 AreEqualLang[0m [2X> AreEqualLang( [0X[3XA1, A2[0X[2X ) ___________________________________________[0Xfunction [2X> AreEquivAut( [0X[3XA1, A2[0X[2X ) ____________________________________________[0Xfunction These functions, which are synonyms, test if the automata or rational expressions [3XA1[0m and [3XA2[0m 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. [4X--------------------------- Example ----------------------------[0X [4Xgap> y:=RandomAutomaton("det",4,2);;[0X [4Xgap> x:=RandomAutomaton("det",4,2);;[0X [4Xgap> AreEquivAut(x, y);[0X [4Xfalse[0X [4Xgap> a:=RationalExpression("(aUb)*ab*");[0X [4X(aUb)*ab*[0X [4Xgap> b:=RationalExpression("(aUb)*");[0X [4X(aUb)*[0X [4Xgap> AreEqualLang(a, b);[0X [4Xfalse[0X [4Xgap> a:=RationalExpression("(bUa)*");[0X [4X(bUa)*[0X [4Xgap> AreEqualLang(a, b);[0X [4Xtrue[0X [4Xgap> x:=RationalExpression("(1U0)*");[0X [4X(1U0)*[0X [4Xgap> AreEqualLang(a, x); [0X [4XThe given languages are not over the same alphabet[0X [4Xfalse[0X [4Xg[0X [4X------------------------------------------------------------------[0X [1X4.3-4 IsContainedLang[0m [2X> IsContainedLang( [0X[3XR1, R2[0X[2X ) ________________________________________[0Xfunction Tests if the language represented (through an automaton or a rational expression) by [3X R1 [0m is contained in the language represented (through an automaton or a rational expression) by [3X R2 [0m . [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RationalExpression("aUab");[0X [4XaUab[0X [4Xgap> s:=RationalExpression("a","ab");[0X [4Xa[0X [4Xgap> IsContainedLang(s,r);[0X [4Xtrue[0X [4Xgap> IsContainedLang(r,s);[0X [4Xfalse[0X [4X------------------------------------------------------------------[0X [1X4.3-5 AreDisjointLang[0m [2X> AreDisjointLang( [0X[3XR1, R2[0X[2X ) ________________________________________[0Xfunction Tests if the languages represented (through automata or a rational expressions) by [3X R1 [0m and [3X R2 [0m are disjoint. [4X--------------------------- Example ----------------------------[0X [4Xgap> r:=RationalExpression("aUab");;[0X [4Xgap> s:=RationalExpression("a","ab");;[0X [4Xgap> AreDisjointLang(r,s);[0X [4Xfalse[0X [4X------------------------------------------------------------------[0X