chap0.txt

  
  
                                    Automata
  
  
                                ( Version 1.13 )
  
  
                                 Manuel Delgado
  
                                  Steve Linton
  
                                José João Morais
  
  
  
  Manuel Delgado
      Email:    mailto:[email protected]
      Homepage: http://www.fc.up.pt/cmup/mdelgado
  Steve Linton
      Email:    mailto:[email protected]
      Homepage: http://www-circa.mcs.st-and.ac.uk/~sal/
  
  -------------------------------------------------------
  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 for his contribution in
  finding bugs and making suggestions for the improvement of this package.
  
  Concerning the mantainment:
  
  The   first   author   was/is  (partially)  supported  by  the  FCT  project
  PTDC/MAT/65481/2006  and also by the Centro de Matemática da Universidade do
  Porto  (CMUP),  funded by the European Regional Development Fund through the
  program  COMPETE and by the Portuguese Government through the FCT - Fundação
  para a Ciência e a Tecnologia under the project PEst-C/MAT/UI0144/2011.
  
  
  -------------------------------------------------------
  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.
  
  Since  Version 1.12, the package is maintained by the first two authors. Bug
  reports,  suggestions  and  comments are, of course, welcome. Please use our
  email addresses to this effect.
  
  
  -------------------------------------------------------
  
  
  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