More remarks on Glushkov automata.

1 files changed, 20 insertions, 3 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 6312c88..78191a4 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2618,7 +2618,7 @@ si l'automate accepte le mot.
 
 \thingy Les constructions que nous avons décrites dans cette section
 associent naturellement un NFA standard à chaque expression
-rationnelle : il s'obtient en partant des automates décrits
+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,
@@ -2628,12 +2628,29 @@ suivantes :
 \item c'est un NFA reconnaissant le langage $L_r$ dénoté par
   l'expression rationnelle $r$ dont on est parti,
 \item il est standard au sens de \ref{standard-automaton-lemma},
-  c'est-à-dire qu'il possède un unique état initial qui n'est la cible
-  d'aucune transition,
+  c'est-à-dire qu'il possède un unique état initial auquel n'aboutit
+  aucune transition,
+\item les transitions aboutissant à n'importe quel état donné sont
+  toutes étiquetées par la même lettre,
 \item son nombre d'états est égal à $1$ plus le nombre de lettres (à
   l'exclusion des métacaractères) contenues dans l'expression $r$.
 \end{itemize}
 
+Les deux dernières propriétés se vérifient inductivement, c'est-à-dire
+qu'on observe qu'elles sont satisfaites sur les automates de base
+décrits en \ref{trivial-standard-automata} qu'elles sont préservées
+par les constructions de \ref{nfa-union}, \ref{nfa-concatenation}
+et \ref{nfa-star}.  En fait, on peut être un peu plus précis : chaque
+état, autre que l'état initial, de l'automate de Glushkov associé à
+l'expression rationnelle $r$ correspond à une lettre $x$ (à
+l'exclusion des métacaractères) de $r$, l'état en question provient de
+l'état $q_1$ de l'automate décrit en \ref{trivial-standard-automata}
+pour le langage $\{x\}$, et toutes les transitions menant à cet état
+sont étiquetées par $x$.
+
+Ces observations sont utiles pour détecter des erreurs lors de la
+construction de l'automate.
+
 \textcolor{red}{TODO: Développer, et donner des exemples.}