Sophie

Sophie

distrib > Mandriva > 2010.0 > i586 > media > contrib-release > by-pkgid > 5e1854624d3bc613bdd0dd13d1ef9ac7 > files > 835

gap-system-4.4.12-5mdv2010.0.i586.rpm

  
  6 Finite regular languages
  
  This chapter describes some functions to deal with finite regular languages.
  
  
  6.1 Dealing with finite regular languages
  
  6.1-1 IsFiniteRegularLanguage
  
  > IsFiniteRegularLanguage( L ) _____________________________________function
  
  L  is an automaton or a rational expression. This function tests whether its
  argument represents a finite language or not.
  
  ---------------------------  Example  ----------------------------
    gap> RandomRatExp(2);
    b*(aU@)
    gap> IsFiniteRegularLanguage(last);
    false
    gap> RandomRatExp(2);
    aUbU@
    gap> IsFiniteRegularLanguage(last);
    true
  ------------------------------------------------------------------
  
  6.1-2 FiniteRegularLanguageToListOfWords
  
  > FiniteRegularLanguageToListOfWords( L ) __________________________function
  
  L  is  an  automaton  or  a  rational  expression. This function outputs the
  recognized language as a list of words.
  
  ---------------------------  Example  ----------------------------
    gap> r:=RationalExpression("aaUx(aUb)");   
    aaUx(aUb)
    gap>  FiniteRegularLanguageToListOfWords(r);
    [ "aa", "xa", "xb" ]
  ------------------------------------------------------------------
  
  6.1-3 ListOfWordsToAutomaton
  
  > ListOfWordsToAutomaton( alph, L ) ________________________________function
  
  Given  an  alphabet  alph  (a list) and a list of words L (a list of lists),
  outputs an automaton that recognizes the given list of words.
  
  ---------------------------  Example  ----------------------------
    gap> ListOfWordsToAutomaton("ab",["aaa","bba",""]);
    < deterministic automaton on 2 letters with 6 states >
    gap> FAtoRatExp(last);
    (bbUaa)aU@
  ------------------------------------------------------------------