\contentsline {chapter}{\numberline {1}\leavevmode {\color {Chapter } Introduction }}{7}{chapter.1}
\contentsline {chapter}{\numberline {2}\leavevmode {\color {Chapter }Finite Automata}}{9}{chapter.2}
\contentsline {section}{\numberline {2.1}\leavevmode {\color {Chapter }Automata generation}}{9}{section.2.1}
\contentsline {subsection}{\numberline {2.1.1}\leavevmode {\color {Chapter }Automaton}}{9}{subsection.2.1.1}
\contentsline {subsection}{\numberline {2.1.2}\leavevmode {\color {Chapter }IsAutomaton}}{11}{subsection.2.1.2}
\contentsline {subsection}{\numberline {2.1.3}\leavevmode {\color {Chapter }IsDeterministicAutomaton}}{11}{subsection.2.1.3}
\contentsline {subsection}{\numberline {2.1.4}\leavevmode {\color {Chapter }IsNonDeterministicAutomaton}}{11}{subsection.2.1.4}
\contentsline {subsection}{\numberline {2.1.5}\leavevmode {\color {Chapter }IsEpsilonAutomaton}}{11}{subsection.2.1.5}
\contentsline {subsection}{\numberline {2.1.6}\leavevmode {\color {Chapter }String}}{12}{subsection.2.1.6}
\contentsline {subsection}{\numberline {2.1.7}\leavevmode {\color {Chapter }RandomAutomaton}}{12}{subsection.2.1.7}
\contentsline {section}{\numberline {2.2}\leavevmode {\color {Chapter }Automata internals}}{13}{section.2.2}
\contentsline {subsection}{\numberline {2.2.1}\leavevmode {\color {Chapter }AlphabetOfAutomaton}}{13}{subsection.2.2.1}
\contentsline {subsection}{\numberline {2.2.2}\leavevmode {\color {Chapter }AlphabetOfAutomatonAsList}}{13}{subsection.2.2.2}
\contentsline {subsection}{\numberline {2.2.3}\leavevmode {\color {Chapter }TransitionMatrixOfAutomaton}}{14}{subsection.2.2.3}
\contentsline {subsection}{\numberline {2.2.4}\leavevmode {\color {Chapter }InitialStatesOfAutomaton}}{14}{subsection.2.2.4}
\contentsline {subsection}{\numberline {2.2.5}\leavevmode {\color {Chapter }SetInitialStatesOfAutomaton}}{14}{subsection.2.2.5}
\contentsline {subsection}{\numberline {2.2.6}\leavevmode {\color {Chapter }FinalStatesOfAutomaton}}{14}{subsection.2.2.6}
\contentsline {subsection}{\numberline {2.2.7}\leavevmode {\color {Chapter }SetFinalStatesOfAutomaton}}{15}{subsection.2.2.7}
\contentsline {subsection}{\numberline {2.2.8}\leavevmode {\color {Chapter }NumberStatesOfAutomaton}}{15}{subsection.2.2.8}
\contentsline {section}{\numberline {2.3}\leavevmode {\color {Chapter }Comparison of automata}}{15}{section.2.3}
\contentsline {section}{\numberline {2.4}\leavevmode {\color {Chapter }Tests involving automata}}{15}{section.2.4}
\contentsline {subsection}{\numberline {2.4.1}\leavevmode {\color {Chapter }IsDenseAutomaton}}{15}{subsection.2.4.1}
\contentsline {subsection}{\numberline {2.4.2}\leavevmode {\color {Chapter }IsRecognizedByAutomaton}}{16}{subsection.2.4.2}
\contentsline {subsection}{\numberline {2.4.3}\leavevmode {\color {Chapter }IsPermutationAutomaton}}{16}{subsection.2.4.3}
\contentsline {subsection}{\numberline {2.4.4}\leavevmode {\color {Chapter }IsInverseAutomaton}}{16}{subsection.2.4.4}
\contentsline {subsection}{\numberline {2.4.5}\leavevmode {\color {Chapter }AddInverseEdgesToInverseAutomaton}}{16}{subsection.2.4.5}
\contentsline {subsection}{\numberline {2.4.6}\leavevmode {\color {Chapter }IsReversibleAutomaton}}{17}{subsection.2.4.6}
\contentsline {section}{\numberline {2.5}\leavevmode {\color {Chapter }Basic operations}}{17}{section.2.5}
\contentsline {subsection}{\numberline {2.5.1}\leavevmode {\color {Chapter }CopyAutomaton}}{17}{subsection.2.5.1}
\contentsline {subsection}{\numberline {2.5.2}\leavevmode {\color {Chapter }NullCompletionAutomaton}}{17}{subsection.2.5.2}
\contentsline {subsection}{\numberline {2.5.3}\leavevmode {\color {Chapter }ListSinkStatesAut}}{18}{subsection.2.5.3}
\contentsline {subsection}{\numberline {2.5.4}\leavevmode {\color {Chapter }RemovedSinkStates}}{18}{subsection.2.5.4}
\contentsline {subsection}{\numberline {2.5.5}\leavevmode {\color {Chapter }ReversedAutomaton}}{18}{subsection.2.5.5}
\contentsline {subsection}{\numberline {2.5.6}\leavevmode {\color {Chapter }PermutedAutomaton}}{19}{subsection.2.5.6}
\contentsline {subsection}{\numberline {2.5.7}\leavevmode {\color {Chapter }ListPermutedAutomata}}{19}{subsection.2.5.7}
\contentsline {subsection}{\numberline {2.5.8}\leavevmode {\color {Chapter }NormalizedAutomaton}}{19}{subsection.2.5.8}
\contentsline {subsection}{\numberline {2.5.9}\leavevmode {\color {Chapter }UnionAutomata}}{20}{subsection.2.5.9}
\contentsline {subsection}{\numberline {2.5.10}\leavevmode {\color {Chapter }ProductAutomaton}}{20}{subsection.2.5.10}
\contentsline {subsection}{\numberline {2.5.11}\leavevmode {\color {Chapter }ProductOfLanguages}}{21}{subsection.2.5.11}
\contentsline {section}{\numberline {2.6}\leavevmode {\color {Chapter }Links with Semigroups}}{21}{section.2.6}
\contentsline {subsection}{\numberline {2.6.1}\leavevmode {\color {Chapter }TransitionSemigroup}}{21}{subsection.2.6.1}
\contentsline {subsection}{\numberline {2.6.2}\leavevmode {\color {Chapter }SyntacticSemigroupAut}}{22}{subsection.2.6.2}
\contentsline {subsection}{\numberline {2.6.3}\leavevmode {\color {Chapter }SyntacticSemigroupLang}}{22}{subsection.2.6.3}
\contentsline {chapter}{\numberline {3}\leavevmode {\color {Chapter }Rational languages}}{23}{chapter.3}
\contentsline {section}{\numberline {3.1}\leavevmode {\color {Chapter }Rational Expressions}}{23}{section.3.1}
\contentsline {subsection}{\numberline {3.1.1}\leavevmode {\color {Chapter }RationalExpression}}{23}{subsection.3.1.1}
\contentsline {subsection}{\numberline {3.1.2}\leavevmode {\color {Chapter }RatExpOnnLetters}}{23}{subsection.3.1.2}
\contentsline {subsection}{\numberline {3.1.3}\leavevmode {\color {Chapter }RandomRatExp}}{24}{subsection.3.1.3}
\contentsline {subsection}{\numberline {3.1.4}\leavevmode {\color {Chapter }SizeRatExp}}{24}{subsection.3.1.4}
\contentsline {subsection}{\numberline {3.1.5}\leavevmode {\color {Chapter }IsRationalExpression}}{24}{subsection.3.1.5}
\contentsline {subsection}{\numberline {3.1.6}\leavevmode {\color {Chapter }AlphabetOfRatExp}}{25}{subsection.3.1.6}
\contentsline {subsection}{\numberline {3.1.7}\leavevmode {\color {Chapter }AlphabetOfRatExpAsList}}{25}{subsection.3.1.7}
\contentsline {subsection}{\numberline {3.1.8}\leavevmode {\color {Chapter }CopyRatExp}}{26}{subsection.3.1.8}
\contentsline {section}{\numberline {3.2}\leavevmode {\color {Chapter }Comparison of rational expressions}}{26}{section.3.2}
\contentsline {section}{\numberline {3.3}\leavevmode {\color {Chapter }Operations with rational languages}}{26}{section.3.3}
\contentsline {subsection}{\numberline {3.3.1}\leavevmode {\color {Chapter }UnionRatExp}}{26}{subsection.3.3.1}
\contentsline {subsection}{\numberline {3.3.2}\leavevmode {\color {Chapter }ProductRatExp}}{26}{subsection.3.3.2}
\contentsline {subsection}{\numberline {3.3.3}\leavevmode {\color {Chapter } StarRatExp}}{26}{subsection.3.3.3}
\contentsline {chapter}{\numberline {4}\leavevmode {\color {Chapter }Automata \emph {versus} rational expressions}}{28}{chapter.4}
\contentsline {section}{\numberline {4.1}\leavevmode {\color {Chapter }From automata to rational expressions}}{28}{section.4.1}
\contentsline {subsection}{\numberline {4.1.1}\leavevmode {\color {Chapter }AutomatonToRatExp }}{28}{subsection.4.1.1}
\contentsline {section}{\numberline {4.2}\leavevmode {\color {Chapter }From rational expression to automata}}{28}{section.4.2}
\contentsline {subsection}{\numberline {4.2.1}\leavevmode {\color {Chapter }RatExpToNDAut}}{28}{subsection.4.2.1}
\contentsline {subsection}{\numberline {4.2.2}\leavevmode {\color {Chapter }RatExpToAutomaton}}{29}{subsection.4.2.2}
\contentsline {section}{\numberline {4.3}\leavevmode {\color {Chapter } Some tests on automata }}{29}{section.4.3}
\contentsline {subsection}{\numberline {4.3.1}\leavevmode {\color {Chapter }IsEmptyLang}}{30}{subsection.4.3.1}
\contentsline {subsection}{\numberline {4.3.2}\leavevmode {\color {Chapter }IsFullLang}}{30}{subsection.4.3.2}
\contentsline {subsection}{\numberline {4.3.3}\leavevmode {\color {Chapter }AreEqualLang}}{30}{subsection.4.3.3}
\contentsline {subsection}{\numberline {4.3.4}\leavevmode {\color {Chapter }IsContainedLang}}{31}{subsection.4.3.4}
\contentsline {subsection}{\numberline {4.3.5}\leavevmode {\color {Chapter }AreDisjointLang}}{31}{subsection.4.3.5}
\contentsline {chapter}{\numberline {5}\leavevmode {\color {Chapter }Some functions involving automata}}{32}{chapter.5}
\contentsline {section}{\numberline {5.1}\leavevmode {\color {Chapter }From one type to another}}{32}{section.5.1}
\contentsline {subsection}{\numberline {5.1.1}\leavevmode {\color {Chapter }EpsilonToNFA}}{32}{subsection.5.1.1}
\contentsline {subsection}{\numberline {5.1.2}\leavevmode {\color {Chapter }EpsilonToNFASet}}{32}{subsection.5.1.2}
\contentsline {subsection}{\numberline {5.1.3}\leavevmode {\color {Chapter }EpsilonCompactedAut}}{33}{subsection.5.1.3}
\contentsline {subsection}{\numberline {5.1.4}\leavevmode {\color {Chapter }ReducedNFA}}{33}{subsection.5.1.4}
\contentsline {subsection}{\numberline {5.1.5}\leavevmode {\color {Chapter }NFAtoDFA}}{34}{subsection.5.1.5}
\contentsline {subsection}{\numberline {5.1.6}\leavevmode {\color {Chapter }FuseSymbolsAut}}{34}{subsection.5.1.6}
\contentsline {section}{\numberline {5.2}\leavevmode {\color {Chapter }Minimalization of an automaton}}{34}{section.5.2}
\contentsline {subsection}{\numberline {5.2.1}\leavevmode {\color {Chapter }UsefulAutomaton}}{35}{subsection.5.2.1}
\contentsline {subsection}{\numberline {5.2.2}\leavevmode {\color {Chapter }MinimalizedAut}}{35}{subsection.5.2.2}
\contentsline {subsection}{\numberline {5.2.3}\leavevmode {\color {Chapter } MinimalAutomaton}}{35}{subsection.5.2.3}
\contentsline {subsection}{\numberline {5.2.4}\leavevmode {\color {Chapter }AccessibleStates}}{36}{subsection.5.2.4}
\contentsline {subsection}{\numberline {5.2.5}\leavevmode {\color {Chapter }AccessibleAutomaton}}{36}{subsection.5.2.5}
\contentsline {subsection}{\numberline {5.2.6}\leavevmode {\color {Chapter }IntersectionLanguage}}{37}{subsection.5.2.6}
\contentsline {subsection}{\numberline {5.2.7}\leavevmode {\color {Chapter }AutomatonAllPairsPaths}}{37}{subsection.5.2.7}
\contentsline {chapter}{\numberline {6}\leavevmode {\color {Chapter }Finite regular languages}}{39}{chapter.6}
\contentsline {section}{\numberline {6.1}\leavevmode {\color {Chapter }Dealing with finite regular languages}}{39}{section.6.1}
\contentsline {subsection}{\numberline {6.1.1}\leavevmode {\color {Chapter }IsFiniteRegularLanguage}}{39}{subsection.6.1.1}
\contentsline {subsection}{\numberline {6.1.2}\leavevmode {\color {Chapter }FiniteRegularLanguageToListOfWords}}{39}{subsection.6.1.2}
\contentsline {subsection}{\numberline {6.1.3}\leavevmode {\color {Chapter }ListOfWordsToAutomaton}}{39}{subsection.6.1.3}
\contentsline {chapter}{\numberline {A}\leavevmode {\color {Chapter }Directed graphs}}{41}{appendix.A}
\contentsline {section}{\numberline {A.1}\leavevmode {\color {Chapter }Directed graphs}}{41}{section.A.1}
\contentsline {subsection}{\numberline {A.1.1}\leavevmode {\color {Chapter }RandomDiGraph}}{42}{subsection.A.1.1}
\contentsline {subsection}{\numberline {A.1.2}\leavevmode {\color {Chapter }VertexInDegree}}{42}{subsection.A.1.2}
\contentsline {subsection}{\numberline {A.1.3}\leavevmode {\color {Chapter }VertexOutDegree}}{42}{subsection.A.1.3}
\contentsline {subsection}{\numberline {A.1.4}\leavevmode {\color {Chapter }AutoVertexDegree}}{42}{subsection.A.1.4}
\contentsline {subsection}{\numberline {A.1.5}\leavevmode {\color {Chapter }ReversedGraph}}{42}{subsection.A.1.5}
\contentsline {subsection}{\numberline {A.1.6}\leavevmode {\color {Chapter }AutoConnectedComponents}}{43}{subsection.A.1.6}
\contentsline {subsection}{\numberline {A.1.7}\leavevmode {\color {Chapter }GraphStronglyConnectedComponents}}{43}{subsection.A.1.7}
\contentsline {subsection}{\numberline {A.1.8}\leavevmode {\color {Chapter }UnderlyingMultiGraphOfAutomaton}}{43}{subsection.A.1.8}
\contentsline {subsection}{\numberline {A.1.9}\leavevmode {\color {Chapter }UnderlyingGraphOfAutomaton}}{44}{subsection.A.1.9}
\contentsline {subsection}{\numberline {A.1.10}\leavevmode {\color {Chapter }DiGraphToRelation}}{44}{subsection.A.1.10}
\contentsline {subsection}{\numberline {A.1.11}\leavevmode {\color {Chapter }MSccAutomaton}}{44}{subsection.A.1.11}
\contentsline {subsection}{\numberline {A.1.12}\leavevmode {\color {Chapter }AutoIsAcyclicGraph}}{45}{subsection.A.1.12}
\contentsline {chapter}{\numberline {B}\leavevmode {\color {Chapter } Drawing automata }}{46}{appendix.B}
\contentsline {section}{\numberline {B.1}\leavevmode {\color {Chapter } Installing some external programs }}{46}{section.B.1}
\contentsline {section}{\numberline {B.2}\leavevmode {\color {Chapter } Functions to draw automata }}{46}{section.B.2}
\contentsline {subsection}{\numberline {B.2.1}\leavevmode {\color {Chapter }DrawAutomaton}}{46}{subsection.B.2.1}
\contentsline {subsection}{\numberline {B.2.2}\leavevmode {\color {Chapter }DrawAutomata}}{48}{subsection.B.2.2}
\contentsline {subsection}{\numberline {B.2.3}\leavevmode {\color {Chapter }DrawGraph}}{48}{subsection.B.2.3}
\contentsline {subsection}{\numberline {B.2.4}\leavevmode {\color {Chapter }DrawSCCAutomaton}}{48}{subsection.B.2.4}
\contentsline {section}{\numberline {B.3}\leavevmode {\color {Chapter }Drawings output formats}}{49}{section.B.3}
\contentsline {section}{\numberline {B.4}\leavevmode {\color {Chapter }Drawings extra graph attributes}}{49}{section.B.4}
\contentsline {chapter}{\numberline {C}\leavevmode {\color {Chapter }Inverse automata and subgroups of the free group}}{50}{appendix.C}
\contentsline {section}{\numberline {C.1}\leavevmode {\color {Chapter }From subgroups to inverse automata}}{50}{section.C.1}
\contentsline {subsection}{\numberline {C.1.1}\leavevmode {\color {Chapter }GeneratorsToListRepresentation}}{50}{subsection.C.1.1}
\contentsline {subsection}{\numberline {C.1.2}\leavevmode {\color {Chapter }ListToGeneratorsRepresentation}}{50}{subsection.C.1.2}
\contentsline {subsection}{\numberline {C.1.3}\leavevmode {\color {Chapter }FlowerAutomaton}}{51}{subsection.C.1.3}
\contentsline {subsection}{\numberline {C.1.4}\leavevmode {\color {Chapter }FoldFlowerAutomaton}}{51}{subsection.C.1.4}
\contentsline {subsection}{\numberline {C.1.5}\leavevmode {\color {Chapter }SubgroupGenToInvAut}}{51}{subsection.C.1.5}
\contentsline {section}{\numberline {C.2}\leavevmode {\color {Chapter }From inverse automata to subgroups}}{52}{section.C.2}
\contentsline {subsection}{\numberline {C.2.1}\leavevmode {\color {Chapter }GeodesicTreeOfInverseAutomaton}}{52}{subsection.C.2.1}
\contentsline {subsection}{\numberline {C.2.2}\leavevmode {\color {Chapter }InverseAutomatonToGenerators}}{52}{subsection.C.2.2}