Glushkov automata: define properly.

1 files changed, 52 insertions, 11 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index efb4a57..6312c88 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2084,7 +2084,7 @@ choix.
 
 \section{Langages reconnaissables et langages rationnels}\label{section-recognizable-languages}
 
-\subsection{Stabilité des langages reconnaissables}
+\subsection{Stabilité des langages reconnaissables par opérations booléennes et miroir}
 
 \thingy On rappelle qu'on a défini un langage \index{reconnaissable
   (langage)}reconnaissable comme un langage $L$ pour lequel il existe
@@ -2213,12 +2213,15 @@ 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}
+
 \thingy Nous allons maintenant montrer que la classe des langages
 reconnaissables est stable par les opérations rationnelles (union,
 concaténation et étoile de Kleene,
-cf. \ref{stable-under-rational-operations} ; on l'a déjà vu pour la
-réunion, mais on va en donner une nouvelle démonstration, qui a un
-contenu algorithmique utile dans des circonstances différentes).
+cf. \ref{stable-under-rational-operations} ; on l'a déjà vu sur les
+DFA en \ref{dfa-union-and-intersection} pour la réunion, mais on va en
+donner une nouvelle démonstration, cette fois basée sur les NFA, qui a
+un contenu algorithmique utile dans des circonstances différentes).
 
 Pour établir ces stabilités, on va travailler sur les NFA et utiliser
 la construction parfois appelée « de Glushkov » ou « automate
@@ -2567,6 +2570,29 @@ final dans cet automate $A'$ consiste en un nombre quelconque
 dans $A$.  On a donc bien $L_{A'} = L^*$.
 \end{proof}
 
+\thingy\label{trivial-standard-automata} Il sera utile de fixer
+également des NFA (« standards » au sens de
+\ref{standard-automaton-lemma}) reconnaissant les langages de base
+triviaux $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
+chaque $x\in\Sigma$).  On prendra les suivants :
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
+\end{tikzpicture}
+pour le langage $\varnothing$\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final] {$q_0$};
+\end{tikzpicture}
+pour le langage $\{\varepsilon\}$\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final] {$q_1$};
+\draw [->] (q0) to node[auto,swap] {$x$} (q1);
+\end{tikzpicture}
+pour le langage $\{x\}$.
+\end{center}
+
 \begin{cor}\label{rational-languages-are-recognizable}
 Tout langage rationnel est reconnaissable ; de plus, un NFA le
 reconnaissant se déduit algorithmiquement d'une expression rationnelle
@@ -2577,9 +2603,9 @@ algorithmiquement si un mot vérifie une expression rationnelle.)
 Cela résulte de façon évidente de la définition des langages
 rationnels (cf. §\ref{subsection-rational-languages}), du fait que les
 langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
-chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des
-propositions \ref{nfa-union}, \ref{nfa-concatenation}
-et \ref{nfa-star}.
+chaque $x\in\Sigma$) sont reconnaissables par automates finis
+(cf. \ref{trivial-standard-automata}), et grâce aux propositions
+\ref{nfa-union}, \ref{nfa-concatenation} et \ref{nfa-star}.
 
 Pour décider si un mot vérifie une expression rationnelle, on peut
 commencer par transformer cette expression rationnelle en NFA standard
@@ -2590,10 +2616,25 @@ automate en DFA quitte déterminiser
 si l'automate accepte le mot.
 \end{proof}
 
-\textcolor{red}{TODO: Standardiser la construction des automates.  Par
-  exemple, utiliser le NFA « standard » ou « de Glushkov » (ayant un
-  seul état initial, éventuellement final, sans aucune transition qui
-  y mène).}
+\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
+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 :
+\begin{itemize}
+\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,
+\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}
+
+\textcolor{red}{TODO: Développer, et donner des exemples.}
 
 
 \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}