\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}