<!-- $Id: aut-vs-rat.xml,v 1.12 Exp $ --> <Chapter><Heading>Automata <Emph>versus</Emph> rational expressions</Heading> 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. <P/> An automaton and a rational expression are said to be <E>equivalent</E> when both represent the same language. In this chapter we describe functions to go from automata to equivalent rational expressions and <E>vice-versa</E>. <Section><Heading>From automata to rational expressions</Heading> <ManSection> <Func Name="AutomatonToRatExp " Arg="A"/> <Func Name="AutToRatExp" Arg="A"/> <Func Name="FAtoRatExp" Arg="A"/> <Description> From a finite automaton, <C>FAtoRatExp</C>, <C>AutToRatExp</C> and <C>AutomatonToRatExp</C>, which are synonyms, compute one equivalent rational expression, using the state elimination algorithm. <Example> 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@ </Example> </Description> </ManSection> </Section> <Section><Heading>From rational expression to automata</Heading> <ManSection> <Func Name="RatExpToNDAut" Arg="R"/> <Description> Given a rational expression <A>R</A>, computes the equivalent NFA <Example> 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 ] </Example> </Description> </ManSection> <ManSection> <Func Name="RatExpToAutomaton" Arg="R"/> <Func Name="RatExpToAut" Arg="R"/> <Description> Given a rational expression <A>R</A>, these functions, which are synonyms, use <Ref Func="RatExpToNDAut"/>) to compute the equivalent NFA and then returns the equivalent minimal DFA <Example> 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 ] </Example> </Description> </ManSection> </Section> <Section> <Heading> Some tests on automata </Heading> This section describes functions that perform tests on automata, rational expressions and their accepted languages. <ManSection> <Func Arg="R" Name="IsEmptyLang" /> <Description> This function tests if the language given through a rational expression or an automaton <Arg> R </Arg> is the empty language. <Example> gap> r:=RandomRatExp(2); empty_set gap> IsEmptyLang(r); true gap> r:=RandomRatExp(2); aUb gap> IsEmptyLang(r); false </Example> </Description> </ManSection> <ManSection> <Func Arg="R" Name="IsFullLang" /> <Description> This function tests if the language given through a rational expression or an automaton <Arg> R </Arg> represents the Kleene closure of the alphabet of <A> R </A> . <Example> gap> r:=RationalExpression("aUb"); aUb gap> IsFullLang(r); false gap> r:=RationalExpression("(aUb)*"); (aUb)* gap> IsFullLang(r); true </Example> </Description> </ManSection> <ManSection> <Func Arg="A1, A2" Name="AreEqualLang" /> <Func Name="AreEquivAut" Arg="A1,A2 "/> <Description> These functions, which are synonyms, test if the automata or rational expressions <A>A1</A> and <A>A2</A> 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. <Example> gap> y:=RandomAutomaton("det",4,2);; gap> x:=RandomAutomaton("det",4,2);; gap> AreEquivAut(x, y); 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 g</Example> </Description> </ManSection> <ManSection> <Func Arg="R1, R2" Name="IsContainedLang" /> <Description> Tests if the language represented (through an automaton or a rational expression) by <A> R1 </A> is contained in the language represented (through an automaton or a rational expression) by <A> R2 </A> . <Example> gap> r:=RationalExpression("aUab"); aUab gap> s:=RationalExpression("a","ab"); a gap> IsContainedLang(s,r); true gap> IsContainedLang(r,s); false </Example> </Description> </ManSection> <ManSection> <Func Arg="R1, R2" Name="AreDisjointLang" /> <Description> Tests if the languages represented (through automata or a rational expressions) by <A> R1 </A> and <A> R2 </A> are disjoint. <Example> gap> r:=RationalExpression("aUab");; gap> s:=RationalExpression("a","ab");; gap> AreDisjointLang(r,s); false </Example> </Description> </ManSection> </Section> </Chapter>