Automata
  
  
                                ( Version 1.12 )
  
  
                                 Manuel Delgado
  
                                  Steve Linton
  
                                José João Morais
  
  
  
  Manuel Delgado
      Email:    mailto:mdelgado@fc.up.pt
      Homepage: http://www.fc.up.pt/cmup/mdelgado
  Steve Linton
      Email:    mailto:sal@dcs.st-and.ac.uk
      Homepage: http://www.dcs.st-and.ac.uk/~sal/
  José João Morais
      Email:    mailto:josejoao@fc.up.pt
  
  -------------------------------------------------------
  Copyright
  © 2004 by Manuel Delgado, Steve Linton and José Morais
  
  We  adopt  the  copyright  regulations  of  GAP as detailed in the copyright
  notice in the GAP manual.
  
  
  -------------------------------------------------------
  Acknowledgements
  The  first  author wishes to acknowledge Cyril Nicaud and Paulo Varandas for
  their  help  in programming some functions of the very first version of this
  package.  He  wishes  also to acknowledge useful discussions and comments by
  Cyril Nicaud, Vítor H. Fernandes, Jean-Eric Pin and Jorge Almeida.
  
  The  first  author also acknowledges support of FCT through CMUP and the FCT
  and  POCTI  Project POCTI/32817/MAT/2000 which is funded in cooperation with
  the European Community Fund FEDER.
  
  The third author acknowledges financial support of FCT and the POCTI program
  through  a  scholarship  given  by  Centro  de Matemática da Universidade do
  Porto.
  
  The      authors      would      like     to     thank     Mark     Kambites
  (http://www.theory.informatik.uni-kassel.de/~kambites/) for his contribution
  in finding bugs and making suggestions for the improvement of this package.
  
  
  -------------------------------------------------------
  Colophon
  This  work  started  in  1998, when the first author was in the LIAFA at the
  University  of Paris 7, in a post-doc. Encouraged by J. E. Pin, he began the
  implementation in GAP3 of an algorithm obtained some time before to answer a
  question  from  the realm of Finite Semigroups proposed by J. Almeida. It is
  now part of a separate package: finsemi.
  
  The  first  version  of  this  package on automata was prepared by the first
  author  who  gave  it  the form of a GAP share package. In a second version,
  prepared  by the first and third authors, many functions have been added and
  the  performance  of  many  of  the existing ones has been improved. Further
  important improvements, specially concerning performance, have been achieved
  when  the  second  author  joined  the  group.  Bug reports, suggestions and
  comments  are, of course, welcome. Please contact any of the authors to this
  effect.    Our    e-mail    addresses    are   mailto:mdelgado@fc.up.pt   or
  mailto:sal@dcs.st-and.ac.uk or mailto:josejoao@fc.up.pt.
  
  
  -------------------------------------------------------
  
  
  Contents (Automata)
  
  1 Introduction
  2 Finite Automata
    2.1 Automata generation
      2.1-1 Automaton
      2.1-2 IsAutomaton
      2.1-3 IsDeterministicAutomaton
      2.1-4 IsNonDeterministicAutomaton
      2.1-5 IsEpsilonAutomaton
      2.1-6 String
      2.1-7 RandomAutomaton
    2.2 Automata internals
      2.2-1 AlphabetOfAutomaton
      2.2-2 AlphabetOfAutomatonAsList
      2.2-3 TransitionMatrixOfAutomaton
      2.2-4 InitialStatesOfAutomaton
      2.2-5 SetInitialStatesOfAutomaton
      2.2-6 FinalStatesOfAutomaton
      2.2-7 SetFinalStatesOfAutomaton
      2.2-8 NumberStatesOfAutomaton
    2.3 Comparison of automata
    2.4 Tests involving automata
      2.4-1 IsDenseAutomaton
      2.4-2 IsRecognizedByAutomaton
      2.4-3 IsPermutationAutomaton
      2.4-4 IsInverseAutomaton
      2.4-5 AddInverseEdgesToInverseAutomaton
      2.4-6 IsReversibleAutomaton
    2.5 Basic operations
      2.5-1 CopyAutomaton
      2.5-2 NullCompletionAutomaton
      2.5-3 ListSinkStatesAut
      2.5-4 RemovedSinkStates
      2.5-5 ReversedAutomaton
      2.5-6 PermutedAutomaton
      2.5-7 ListPermutedAutomata
      2.5-8 NormalizedAutomaton
      2.5-9 UnionAutomata
      2.5-10 ProductAutomaton
      2.5-11 ProductOfLanguages
    2.6 Links with Semigroups
      2.6-1 TransitionSemigroup
      2.6-2 SyntacticSemigroupAut
      2.6-3 SyntacticSemigroupLang
  3 Rational languages
    3.1 Rational Expressions
      3.1-1 RationalExpression
      3.1-2 RatExpOnnLetters
      3.1-3 RandomRatExp
      3.1-4 SizeRatExp
      3.1-5 IsRationalExpression
      3.1-6 AlphabetOfRatExp
      3.1-7 AlphabetOfRatExpAsList
      3.1-8 CopyRatExp
    3.2 Comparison of rational expressions
    3.3 Operations with rational languages
      3.3-1 UnionRatExp
      3.3-2 ProductRatExp
      3.3-3  StarRatExp
  4 Automata versus rational expressions
    4.1 From automata to rational expressions
      4.1-1 AutomatonToRatExp 
    4.2 From rational expression to automata
      4.2-1 RatExpToNDAut
      4.2-2 RatExpToAutomaton
    4.3 Some tests on automata
      4.3-1 IsEmptyLang
      4.3-2 IsFullLang
      4.3-3 AreEqualLang
      4.3-4 IsContainedLang
      4.3-5 AreDisjointLang
  5 Some functions involving automata
    5.1 From one type to another
      5.1-1 EpsilonToNFA
      5.1-2 EpsilonToNFASet
      5.1-3 EpsilonCompactedAut
      5.1-4 ReducedNFA
      5.1-5 NFAtoDFA
      5.1-6 FuseSymbolsAut
    5.2 Minimalization of an automaton
      5.2-1 UsefulAutomaton
      5.2-2 MinimalizedAut
      5.2-3  MinimalAutomaton
      5.2-4 AccessibleStates
      5.2-5 AccessibleAutomaton
      5.2-6 IntersectionLanguage
      5.2-7 AutomatonAllPairsPaths
  6 Finite regular languages
    6.1 Dealing with finite regular languages
      6.1-1 IsFiniteRegularLanguage
      6.1-2 FiniteRegularLanguageToListOfWords
      6.1-3 ListOfWordsToAutomaton
  A Directed graphs
    A.1 Directed graphs
      A.1-1 RandomDiGraph
      A.1-2 VertexInDegree
      A.1-3 VertexOutDegree
      A.1-4 AutoVertexDegree
      A.1-5 ReversedGraph
      A.1-6 AutoConnectedComponents
      A.1-7 GraphStronglyConnectedComponents
      A.1-8 UnderlyingMultiGraphOfAutomaton
      A.1-9 UnderlyingGraphOfAutomaton
      A.1-10 DiGraphToRelation
      A.1-11 MSccAutomaton
      A.1-12 AutoIsAcyclicGraph
  B Drawing automata
    B.1 Installing some external programs
    B.2 Functions to draw automata
      B.2-1 DrawAutomaton
      B.2-2 DrawAutomata
      B.2-3 DrawGraph
      B.2-4 DrawSCCAutomaton
    B.3 Drawings output formats
    B.4 Drawings extra graph attributes
  C Inverse automata and subgroups of the free group
    C.1 From subgroups to inverse automata
      C.1-1 GeneratorsToListRepresentation
      C.1-2 ListToGeneratorsRepresentation
      C.1-3 FlowerAutomaton
      C.1-4 FoldFlowerAutomaton
      C.1-5 SubgroupGenToInvAut
    C.2 From inverse automata to subgroups
      C.2-1 GeodesicTreeOfInverseAutomaton
      C.2-2 InverseAutomatonToGenerators
  
  
  -------------------------------------------------------