Rewrite stability of recognizable languages using Glushkov's construction.

1 files changed, 322 insertions, 81 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index ead466a..efb4a57 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -22,7 +22,7 @@
 \usepackage{graphics}
 \usepackage[usenames,dvipsnames]{xcolor}
 \usepackage{tikz}
-\usetikzlibrary{arrows,automata,positioning}
+\usetikzlibrary{arrows,automata,positioning,calc}
 \usepackage[hyperindex=false]{hyperref}
 %
 \theoremstyle{definition}
@@ -761,7 +761,8 @@ cccc,\ldots\}$, est rationnel, et comme $\{d\}$ l'est aussi, la
 concaténation $\{d\}(\{c\}^*) = \{d, dc, dcc, dccc, \ldots\}$ est
 encore un langage rationnel.
 
-\thingy Formellement, la définition des langages rationnelles est la
+\thingy\label{stable-under-rational-operations}
+Formellement, la définition des langages rationnelles est la
 suivante : un ensemble $\mathscr{C} \subseteq \mathscr{P}(\Sigma^*)$
 de langages (où $\mathscr{P}(\Sigma^*)$ est l'ensemble des parties de
 $\Sigma^*$, i.e., l'ensemble de tous les langages sur $\Sigma$,
@@ -2085,12 +2086,12 @@ choix.
 
 \subsection{Stabilité des langages reconnaissables}
 
-\thingy On rappelle qu'on a défini un langage reconnaissable comme un
-langage $L$ pour lequel il existe un DFA $A$ tel que $L = L_A$.
-D'après \ref{completion-of-dfai}, \ref{determinization-of-nfa} et
-\ref{removal-of-epsilon-transitions}, on peut remplacer « DFA » dans
-cette définition par « DFAI », « NFA » ou « εNFA » sans changer la
-définition.
+\thingy On rappelle qu'on a défini un langage \index{reconnaissable
+  (langage)}reconnaissable comme un langage $L$ pour lequel il existe
+un DFA $A$ tel que $L = L_A$.  D'après \ref{completion-of-dfai},
+\ref{determinization-of-nfa} et \ref{removal-of-epsilon-transitions},
+on peut remplacer « DFA » dans cette définition par « DFAI », « NFA »
+ou « εNFA » sans changer la définition.
 
 Nous allons maintenant montrer que les langages reconnaissables sont
 stables par différentes opérations : complémentaire, union,
@@ -2212,6 +2213,77 @@ 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 ».)
 
+\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).
+
+Pour établir ces stabilités, on va travailler sur les NFA et utiliser
+la construction parfois appelée « de Glushkov » ou « automate
+standard ».  Celle-ci travaille, en fait, sur des NFA vérifiant une
+propriété supplémentaire facile à assurer, et on va commencer par un
+lemme dans ce sens :
+
+\begin{lem}\label{standard-automaton-lemma}
+Soit $A$ un NFA.  Alors il existe un NFA $A'$ (sur le même
+alphabet $\Sigma$) qui soit équivalent à $A$ et qui possède la
+propriété supplémentaire d'avoir un \emph{unique} état initial $q_0$
+et qu'aucune transition n'aboutit à $q_0$.  De plus, $A'$ se déduit
+algorithmiquement de $A$ et a au plus un état de plus que $A$.
+
+(On pourra appeler \defin[standard (automate)]{standard} un NFA
+vérifiant cette propriété d'avoir un unique état initial qui n'est la
+cible d'aucune transition.  L'affirmation est donc que tout NFA est
+équivalent à un NFA \emph{standard} qui s'en déduit algorithmiquement
+par l'ajout d'au plus un état.)
+\end{lem}
+\begin{proof}
+On fabrique $A'$ en reprenant le même ensemble d'états $Q$ que
+dans $A$ auquel on ajoute un unique nouvel état $q_0$ qui sera le seul
+état initial de $A'$ ; pour chaque transition partant d'un état
+initial de $A$, on ajoute dans $A'$ une transition identiquement
+étiquetée partant de $q_0$.
+
+Formellement : soit $A = (Q,I,F,\delta)$.  On définit alors $A' =
+(Q',\{q_0\},F,\delta')$ de la manière suivante : $Q' = Q \uplus
+\{q_0\}$ (où $\uplus$ désigne une réunion
+disjointe\footnote{C'est-à-dire qu'on s'arrange pour que $q_0$
+  n'appartienne pas à $Q$.}), et $\delta'$ est la réunion des
+transitions $(q,x,q')$ qui étaient déjà dans $\delta$ et des
+$(q_0,x,q')$ telles qu'il existe une transition $(q,x,q') \in \delta$
+avec $q\in I$.
+
+La figure suivante illustre la transformation en question :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=75bp] {$A$};
+\node (q) at (-15bp,15bp) [draw,circle,state,initial] {\footnotesize $q$};
+\node (qp) at (15bp,15bp) [draw,circle,state] {\footnotesize\vbox to0pt{\vss\hbox to0pt{$q'$\hss}}\phantom{$q$}};
+\draw [->] (A.east) -- ($(A.east)+(3ex,0)$);
+\draw [->] (q) -- node[auto] {\footnotesize $x$} (qp);
+\end{tikzpicture}
+\quad devient\quad
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=75bp] {\phantom{$A$}};
+\node (q) at (-15bp,15bp) [draw,circle,state] {\footnotesize $q$};
+\node (qp) at (15bp,15bp) [draw,circle,state] {\footnotesize\vbox to0pt{\vss\hbox to0pt{$q'$\hss}}\phantom{$q$}};
+\node (q0) at (-40bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$};
+\draw [->] (A.east) -- ($(A.east)+(3ex,0)$);
+\draw [->] (q) -- node[auto] {\footnotesize $x$} (qp);
+\draw [->] (q0) to[out=0,in=270] node[auto,swap] {\footnotesize $x$} (qp.south);
+\end{tikzpicture}
+\end{center}
+
+(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
+ajoutant d'abord un unique état initial $q_0$ et des ε-transitions de
+$q_0$ vers chacun des états initiaux de $A$, puis en éliminant les
+ε-transitions qu'on vient d'ajouter
+(cf. \ref{removal-of-epsilon-transitions}).  Cela donne le même
+résultat que ce qui vient d'être dit.)
+\end{proof}
+
 \thingy On a vu en \ref{dfa-union-and-intersection} une preuve, à base
 de NFA, que $L_1 \cup L_2$ est reconnaissable lorsque $L_1$ et $L_2$
 le sont.  Donnons maintenant une autre preuve de ce fait, à base de
@@ -2220,40 +2292,99 @@ le sont.  Donnons maintenant une autre preuve de ce fait, à base de
 \begin{prop}\label{nfa-union}
 Si $L_1,L_2$ sont des langages reconnaissables (sur un même
 alphabet $\Sigma$), alors la réunion $L_1 \cup L_2$ est
-reconnaissable ; de plus, un εNFA (resp. NFA) la reconnaissant se
-déduit algorithmiquement de εNFA (resp. NFA) reconnaissant $L_1$
-et $L_2$ (c'est simplement, en un sens évident, la réunion disjointe
-des automates donnés).
+reconnaissable ; de plus, un NFA la reconnaissant se déduit
+algorithmiquement de NFA reconnaissant $L_1$ et $L_2$.
 \end{prop}
 \begin{proof}
-Par hypothèse, il existe des εNFA (resp. NFA) $A_1 =
-(Q_1,I_1,F_1,\delta_1)$ et $A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que
-$L_1 = L_{A_1}$ et $L_2 = L_{A_2}$.  Considérons l'automate $A'$ dont
-l'ensemble d'états est $Q' = Q_1 \uplus Q_2$ où $\uplus$ désigne la
-réunion disjointe\footnote{C'est-à-dire que, quitte à renommer les
-  états, on remplace $Q_2$ par un ensemble en bijection avec lui de
-  façon à être disjoint de $Q_1$.}, l'ensemble d'états initiaux est la
-réunion $I' = I_1 \cup I_2$, les états finaux $F' = F_1 \cup F_2$, et
-la relation de transition $\delta'$ est $\delta_1 \cup \delta_2$
-(l'ensemble des transitions existant déjà dans $A_1$ ou $A_2$).
-Symboliquement :
+Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ :
+d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont
+\emph{standards} en ce sens qu'ils ont un unique état initial qui
+n'est la cible d'aucune transition.  Disons que $A_1 =
+(Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont
+des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$.
+
+L'automate $A'$ s'obtient réunissant $A_1$ et $A_2$ mais en
+« fusionnant » les états initiaux $q_1$ et $q_2$ de $A_1$ et $A_2$ en
+un unique état initial $q'_0$, d'où partent les mêmes transitions que
+de l'un ou de l'autre :
 
 \begin{center}
-\begin{tikzpicture}[>=latex,line join=bevel,automaton]
-\node (A1) at (0bp,25bp) [draw,dotted,circle,initial,final] {$A_1$};
-\node (A2) at (0bp,-25bp) [draw,dotted,circle,initial,final] {$A_2$};
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_1$};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\end{tikzpicture}
+et
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_2$};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_2$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\end{tikzpicture}
+\\deviennent\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A1) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_1$}};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q'_0$};
+\node (A1) at (90bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_2$}};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (l1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (l2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (l3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (r1) at (80bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (r2) at (80bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (105bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (115bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (105bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (l1) -- ($(l1.east)+(3ex,0)$);
+\draw [->] (l2) -- ($(l2.east)+(3ex,0)$);
+\draw [->] (l3) -- ($(l3.east)+(3ex,0)$);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\draw [->] (q0) to[out=10,in=180] (r1);
+\draw [->] (q0) to[out=350,in=180] (r2);
 \end{tikzpicture}
 \end{center}
 
-%% \begin{center}
-%% \begin{tikzpicture}[>=latex,line join=bevel,automaton]
-%% \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$q_0$};
-%% \node (A1) at (50bp,30bp) [draw,dotted,circle] {$A_1$};
-%% \node (A2) at (50bp,-30bp) [draw,dotted,circle] {$A_2$};
-%%   \draw [->] (q0) to node[auto] {$\varepsilon$} (A1);
-%%   \draw [->] (q0) to node[auto] {$\varepsilon$} (A2);
-%% \end{tikzpicture}
-%% \end{center}
+De façon plus formelle, considérons un nouvel ensemble d'états $Q' =
+(Q_1 \uplus Q_2) \setminus \{q_1,q_2\} \uplus \{q'_0\}$ où $\uplus$
+désigne la réunion disjointe (autrement dit, on prend la réunion
+disjointe des états non-initiaux de $A_1$ et $A_2$ et on ajoute un
+nouvel état $q'_0$), et la fonction $\varphi_1\colon Q_1 \to Q'$ qui
+envoie $q_1$ sur $q'_0$ et tout autre état de $Q_1$ sur lui-même, et
+$\varphi_2\colon Q_2 \to Q'$ de même.  On définit alors l'automate
+$A'$ dont l'ensemble d'états est $Q'$, l'état initial est $q'_0$, les
+états finaux $F' = \varphi_1(F_1) \cup \varphi_2(F_2)$, et la relation
+de transition $\delta'$ est formée des triplets $(\varphi_1(q),x,q')$
+où $q\in Q_1$ et $(\varphi_2(q),x,q')$ où $q\in Q_2$.
+
+(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
+ajoutant d'abord un unique état initial $q'_0$ à la réunion disjointe
+de $A_1$ et $A_2$ et des ε-transitions de $q'_0$ vers $q_1$ et $q_2$,
+puis en éliminant les ε-transitions qu'on vient d'ajouter
+(cf. \ref{removal-of-epsilon-transitions}) ainsi que les états $q_1$
+et $q_2$ devenus inutiles.  Cela donne le même résultat que ce qui
+vient d'être dit.)
 
 Il est alors clair qu'un chemin de l'état initial à un état final dans
 cet automate $A'$ consiste soit en un chemin d'un état initial à un
@@ -2264,69 +2395,180 @@ bien $L_{A'} = L_1 \cup L_2$.
 \begin{prop}\label{nfa-concatenation}
 Si $L_1,L_2$ sont des langages reconnaissables (sur un même
 alphabet $\Sigma$), alors la concaténation $L_1 L_2$ est
-reconnaissable ; de plus, un εNFA la reconnaissant se déduit
-algorithmiquement de εNFA reconnaissant $L_1$ et $L_2$.
+reconnaissable ; de plus, un NFA la reconnaissant se déduit
+algorithmiquement de NFA reconnaissant $L_1$ et $L_2$.
 \end{prop}
 \begin{proof}
-Par hypothèse, il existe des εNFA $A_1 = (Q_1,I_1,F_1,\delta_1)$ et
-$A_2 = (Q_2,I_2,F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 =
-L_{A_2}$.  Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' =
-Q_1 \uplus Q_2$ où $\uplus$ désigne la réunion disjointe, dont les
-états initiaux sont $I_1$, les états finaux sont $F_2$, et la relation
-de transition $\delta'$ est $\delta_1 \cup \delta_2$ (l'ensemble des
-transitions existant déjà dans $A_1$ ou $A_2$) à quoi on ajoute encore
-une ε-transition $(q,\varepsilon,q')$ pour chaque $q\in F_1$ et
-chaque $q'\in I_2$.  Symboliquement :
+Par hypothèse, il existe des NFA reconnaissant $L_1$ et $L_2$ :
+d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils sont
+\emph{standards} en ce sens qu'ils ont un unique état initial qui
+n'est la cible d'aucune transition.  Disons que $A_1 =
+(Q_1,\{q_1\},F_1,\delta_1)$ et $A_2 = (Q_2,\{q_2\},F_2,\delta_2)$ sont
+des NFA standards tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$.
+
+L'automate $A'$ s'obtient en réunissant $A_1$ et $A_2$, en ne gardant
+que les états finaux de $A_2$, en supprimant $q_2$ et en remplaçant
+chaque transition sortant de $q_2$ par une transition identiquement
+étiquetée partant de chaque état final de $A_1$ :
 
 \begin{center}
-\begin{tikzpicture}[>=latex,line join=bevel,automaton]
-\node (A1) at (0bp,0bp) [draw,dotted,circle,initial] {$A_1$};
-\node (A2) at (70bp,0bp) [draw,dotted,circle,final] {$A_2$};
-  \draw [->] (A1) to node[auto] {$\varepsilon$} (A2);
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_1$};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\end{tikzpicture}
+et
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A_2$};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_2$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\end{tikzpicture}
+\\deviennent\\
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A1) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_1$}};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_1$};
+\node (A1) at (90bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A_2$}};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (l1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (l2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (l3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (r1) at (80bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (r2) at (80bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (105bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (115bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (105bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (l1) to[out=0,in=180] (r1);
+\draw [->] (l1) to[out=0,in=180] (r2);
+\draw [->] (l2) to[out=0,in=180] (r1);
+\draw [->] (l2) to[out=0,in=180] (r2);
+\draw [->] (l3) to[out=0,in=180] (r1);
+\draw [->] (l3) to[out=0,in=180] (r2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
 \end{tikzpicture}
 \end{center}
 
-Il est alors clair qu'un chemin d'un état initial à un état final dans
-cet automate $A'$ consiste en un chemin d'un état initial à un état
-final dans $A_1$ suivi d'une ε-transition et d'un chemin d'un état
-initial à un état final dans $A_2$.  On a donc bien $L_{A'} = L_1
-L_2$.
+De façon plus formelle, considérons un nouvel ensemble d'états $Q' =
+(Q_1 \uplus Q_2) \setminus \{q_2\}$ où $\uplus$ désigne la réunion
+disjointe.  On définit alors l'automate $A'$ dont l'ensemble d'états
+est $Q'$, l'état initial est $q_1$, les états finaux $F' = F_2$, et la
+relation de transition $\delta$ est la réunion de $\delta_1$, de
+l'ensemble des triplets $(q,x,q') \in \delta_2$ tels que $q\neq q_2$,
+et enfin de l'ensemble des triplets $(q,x,q')$ tels que $(q_2,x,q')
+\in \delta_2$ et que $q\in F_1$.
+
+(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
+ajoutant d'abord à la réunion disjointe de $A_1$ et $A_2$ une
+ε-transition de chaque état final de $A_1$ vers $q_2$, puis en
+éliminant les ε-transitions qu'on vient d'ajouter
+(cf. \ref{removal-of-epsilon-transitions}) ainsi que l'état $q_2$
+devenu inutile.  Cela donne le même résultat que ce qui vient d'être
+dit.)
+
+Il est alors clair qu'un chemin de l'état initial $q_1$ à un état
+final dans cet automate $A'$ consiste en un chemin de $q_1$ à un état
+final dans $A_1$ suivi d'un chemin de $q_2$ à un état final dans $A_2$
+(moins $q_2$ lui-même).  On a donc bien $L_{A'} = L_1 L_2$.
 \end{proof}
 
 \begin{prop}\label{nfa-star}
 Si $L$ est un langage reconnaissable (sur un alphabet $\Sigma$), alors
-l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un εNFA la
-reconnaissant se déduit algorithmiquement de εNFA reconnaissant $L$.
+l'étoile de Kleene $L^*$ est reconnaissable ; de plus, un NFA la
+reconnaissant se déduit algorithmiquement de NFA reconnaissant $L$.
 \end{prop}
 \begin{proof}
-Par hypothèse, il existe un εNFA $A = (Q,I,F,\delta)$ tel que $L =
-L_A$.  Considérons le εNFA $A'$ dont l'ensemble d'états est $Q' =
-\{q_0\} \uplus Q$ (où $q_0$ est un nouvel état) dont les états
-initiaux sont $I' = \{q_0\}$, les états finaux sont $F' = \{q_0\}$, et
-la relation de transition $\delta'$ est $\delta$ (l'ensemble des
-transitions existant déjà dans $A$) à quoi on ajoute encore une
-ε-transition $(q_0,\varepsilon,q)$ pour chaque $q\in I$ et une autre
-$(q,\varepsilon,q_0)$ pour chaque $q\in F$.  Symboliquement :
+Par hypothèse, il existe un NFA reconnaissant $L$ :
+d'après \ref{standard-automaton-lemma}, on peut supposer qu'ils est
+\emph{standard} en ce sens qu'il a un unique état initial qui n'est la
+cible d'aucune transition.  Disons que $A = (Q,\{q_0\},F,\delta)$ est
+un NFA standard tel que $L = L_A$.
+
+L'automate $A'$ s'obtient en ajoutant à $A$, pour chaque transition
+sortant de $q_0$, une transition identiquement étiquetée partant de
+chaque état final de $A$, et en rendant $q_0$ final s'il ne l'était
+pas déjà :
 
 \begin{center}
-\begin{tikzpicture}[>=latex,line join=bevel,automaton]
-\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$q_0$};
-\node (A) at (70bp,0bp) [draw,dotted,circle] {$A$};
-  \draw [->,out=45,in=135] (q0) to node[auto] {$\varepsilon$} (A);
-  \draw [->,out=225,in=315] (A) to node[auto] {$\varepsilon$} (q0);
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {$A$};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,fill=white] {$q_0$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\end{tikzpicture}
+devient
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
+\node (A) at (0bp,0bp) [draw,dotted,circle,minimum size=60bp] {\phantom{$A$}};
+\node (q0) at (-35bp,0bp) [draw,circle,state,initial,accepting below,fill=white] {$q_0$};
+\node (i1) at (-10bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (i2) at (-10bp,-20bp) [circle,inner sep=2bp,fill] {};
+\node (o1) at (15bp,20bp) [circle,inner sep=2bp,fill] {};
+\node (o2) at (25bp,0bp) [circle,inner sep=2bp,fill] {};
+\node (o3) at (15bp,-20bp) [circle,inner sep=2bp,fill] {};
+\draw [->] (q0) -- (i1);
+\draw [->] (q0) -- (i2);
+\draw [->] (o1) -- ($(o1.east)+(3ex,0)$);
+\draw [->] (o2) -- ($(o2.east)+(3ex,0)$);
+\draw [->] (o3) -- ($(o3.east)+(3ex,0)$);
+\draw [->] (o1) -- (i1);
+\draw [->] (o1) -- (i2);
+\draw [->] (o2) -- (i1);
+\draw [->] (o2) -- (i2);
+\draw [->] (o3) -- (i1);
+\draw [->] (o3) -- (i2);
 \end{tikzpicture}
 \end{center}
 
-Il est alors clair qu'un chemin de l'état initial $q_0$ à l'état final
-$q_0$ dans cet automate $A'$ consiste en un nombre quelconque
+De façon plus formelle, on considère l'automate $A'$ dont l'ensemble
+d'états est $Q' := Q$, l'état initial est $q_0$, les états finaux $F'
+:= F$, et la relation de transition $\delta'$ est la réunion de
+$\delta$ et de l'ensemble des triplets $(q,x,q')$ tels que $(q_0,x,q')
+\in \delta$ et que $q \in F$.
+
+(\emph{Remarque : } De façon équivalente, on peut fabriquer $A'$ en
+ajoutant d'abord à $A$ une ε-transition de chaque état final de $A$
+vers $q_0$, puis en éliminant les ε-transitions qu'on vient d'ajouter
+(cf. \ref{removal-of-epsilon-transitions}), et enfin en marquant $q_0$
+comme final.  Cela donne le même résultat que ce qui vient d'être
+dit.)
+
+Il est alors clair qu'un chemin de l'état initial $q_0$ à un état
+final dans cet automate $A'$ consiste en un nombre quelconque
 (éventuellement nul) de chemins d'un état initial à un état final
-dans $A$ chacun précédé d'une ε-transition de $q_0$ vers l'état
-initial de $A$ en question et suivi d'une ε-transition de l'état final
-de $A$ en question vers $q_0$.  On a donc bien $L_{A'} = L^*$.
+dans $A$.  On a donc bien $L_{A'} = L^*$.
 \end{proof}
 
 \begin{cor}\label{rational-languages-are-recognizable}
-Tout langage rationnel est reconnaissable ; de plus, un εNFA le
+Tout langage rationnel est reconnaissable ; de plus, un NFA le
 reconnaissant se déduit algorithmiquement d'une expression rationnelle
 le dénotant.  (Et en particulier, il est possible de décider
 algorithmiquement si un mot vérifie une expression rationnelle.)
@@ -2340,11 +2582,10 @@ 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 (i.e.,
-construire un εNFA reconnaissant le langage qu'elle dénote) comme on
-vient de l'expliquer, et transformer ensuite cet automate en DFA
-quitte à éliminer les ε-transitions
-(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser
+commencer par transformer cette expression rationnelle en NFA standard
+(i.e., construire un NFA standard reconnaissant le langage qu'elle
+dénote) comme on vient de l'expliquer, et transformer ensuite cet
+automate en DFA quitte déterminiser
 (cf. \ref{determinization-of-nfa}), après quoi il est facile de tester
 si l'automate accepte le mot.
 \end{proof}