diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 11 |
1 files changed, 6 insertions, 5 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 5047c10..fcca541 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2165,7 +2165,7 @@ sous-ensemble de $Q'' = Q_1\times Q_2$ formé des couples dont \end{proof} \thingy La construction $A'$ ci-dessus est parfois appelée -\emph{produit} des DFA $A_1$ et $A_2$. +\index{produit (d'automates)}\emph{produit} des DFA $A_1$ et $A_2$. La construction de l'automate produit pour fabriquer le langage intersection utilise la caractérisation des langages reconnaissables @@ -2188,7 +2188,8 @@ et finaux). L'automate ainsi construit en inversant toutes les flèches d'un automate $A$ (la définition précise est donnée dans la démonstration qui suit) et qui reconnaît le langage miroir de celui reconnu par $A$ -peut s'appeller automate \textbf{transposé} $A^{\mathsf{R}}$ de $A$. +peut s'appeller automate \defin[transposé (automate)]{transposé} +$A^{\mathsf{R}}$ de $A$. \begin{proof} Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel @@ -2214,7 +2215,7 @@ chaque état $q$ et chaque lettre $x$, il existe une unique arête aboutissant à $q$ et étiquetée par $x$ — sont parfois dits « co-déterministes ».) -\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards} +\subsection{Stabilité des langages reconnaissables par opérations rationnelles, automates standards, construction de Glushkov} \thingy Nous allons maintenant montrer que la classe des langages reconnaissables est stable par les opérations rationnelles (union, @@ -2623,8 +2624,8 @@ rationnelle : il s'obtient en partant des automates de base décrits en \ref{trivial-standard-automata} et en appliquant les constructions décrites dans les démonstrations de \ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}. Cette automate standard, -parfois appelé automate « de Glushkov », possède les propriétés -suivantes : +appelé \defin[Glushkov (construction d'automate de)]{automate de + Glushkov}, possède les propriétés suivantes : \begin{itemize} \item c'est un NFA reconnaissant le langage $L_r$ dénoté par l'expression rationnelle $r$ dont on est parti, |