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