Rational languages are recognizable.

1 files changed, 148 insertions, 29 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index d31b9dd..67b31ec 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -544,7 +544,7 @@ $L^{\mathsf{R}}$ comme l'ensemble des mots miroirs des mots de $L$,
 c'est-à-dire $L^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L\}$.
 
 
-\subsection{Langages rationnels et expressions rationnelles}
+\subsection{Langages rationnels et expressions rationnelles}\label{subsection-rational-languages}
 
 \thingy Soit $\Sigma$ un alphabet.  On va considérer les langages
 de base triviaux suivants :
@@ -1509,11 +1509,13 @@ donc accepté par $A'$.  La réciproque est analogue.
 
 \thingy On dit que le NFA $A'$ est obtenu en \textbf{supprimant les
   ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la
-procédure décrite dans la démonstration de cette proposition.
-Algorithmiquement, il s'agit donc, pour chaque état $q\in Q$ et chaque
-$q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer une transition
-$q\to q'$ étiquetée par $x$ dans $A'$ pour chaque transition
-$q^\sharp\to q'$ étiquetée par $x$ dans $A$.
+procédure décrite dans la démonstration de cette proposition, et en
+supprimant tous les états non-initiaux de $A'$ auxquels n'aboutissent
+dans $A$ que des ε-transitions (ces états sont devenus inaccessibles
+dans $A'$).  Algorithmiquement, il s'agit donc, pour chaque état $q\in
+Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer
+une transition $q\to q'$ étiquetée par $x$ dans $A'$ pour chaque
+transition $q^\sharp\to q'$ étiquetée par $x$ dans $A$.
 
 \thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$
 présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
@@ -1563,7 +1565,7 @@ Nous allons maintenant montrer que les langages reconnaissables sont
 stables par différentes opérations : complémentaire, union,
 intersection, concaténation et étoile de Kleene.
 
-\begin{prop}
+\begin{prop}\label{dfa-complement}
 Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
 le complémentaire $\Sigma^*\setminus L$ de $L$ est reconnaissable ; de
 plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA
@@ -1588,7 +1590,7 @@ reconnaissables par les DFA : il était crucial de le faire, et les
 autres sortes d'automates définis plus haut n'auraient pas permis
 d'arriver (simplement) à la même conclusion.  Pourquoi ?
 
-\begin{prop}
+\begin{prop}\label{dfa-union-and-intersection}
 Si $L_1,L_2$ sont des langages reconnaissables (sur un même
 alphabet $\Sigma$), alors la réunion $L_1\cup L_2$ et l'intersection
 $L_1\cap L_2$ sont reconnaissables ; de plus, un DFA reconnaissant
@@ -1627,26 +1629,7 @@ NFA, un mot est accepté dès qu'\emph{il existe} un chemin qui
 l'accepte, or le quantificateur $\exists$ distribue sur les
 disjonctions mais pas sur les conjonctions).
 
-Ceci étant, il existe une construction plus simple pour faire la
-réunion $L_1 \cup L_2$ de deux langages définis par des εNFA $A_1$ et
-$A_2$ : il suffit de construire l'automate $A'$ dont l'ensemble
-d'états est la réunion disjointe de ceux de $A_1$ et de $A_2$ et d'un
-nouvel état $q_0$ (seul état initial de $A'$), garder les états finaux
-de $A_1$ et de $A_2$ (i.e., prendre leur réunion), ainsi que leurs
-transitions, et ajouter des transitions spontanées de $q_0$ vers les
-états initiaux de $A_1$ et vers ceux de $A_2$.  Symboliquement :
-
-\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) {$A_1$};
-\node (A2) at (50bp,-30bp) {$A_2$};
-  \draw [->] (q0) to node[auto] {$\varepsilon$} (A1);
-  \draw [->] (q0) to node[auto] {$\varepsilon$} (A2);
-\end{tikzpicture}
-\end{center}
-
-\begin{prop}
+\begin{prop}\label{nfa-mirror}
 Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
 le langage miroir (cf. \ref{definition-mirror-language})
 $L^{\mathsf{R}}$ de $L$ est reconnaissable ; de plus, un NFA ou εNFA
@@ -1669,7 +1652,143 @@ l'intersection s'effectuaient naturellement sur les DFA, celle du
 langage miroir s'effectue naturellement sur les NFA.  (On peut, bien
 sûr, considérer un DFA comme un NFA particulier, et effectuer dessus
 l'opération d'inversion des flèches qu'on vient de décrire, mais en
-général on n'obtiendra pas un DFA, seulement un NFA.)
+général on n'obtiendra pas un DFA, seulement un NFA ; les NFA dont
+l'inversion des flèches est déterministe — c'est-à-dire tels que, pour
+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 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
+εNFA :
+
+\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).
+\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 :
+
+\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$};
+\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}
+
+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
+état final dans $A_1$ soit en un tel chemin dans $A_2$.  On a donc
+bien $L_{A'} = L_1 \cup L_2$.
+\end{proof}
+
+\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$.
+\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 :
+
+\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);
+\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$.
+\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$.
+\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 :
+
+\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);
+\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
+(é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^*$.
+\end{proof}
+
+\begin{prop}\label{rational-languages-are-recognizable}
+Tout langage rationnel est reconnaissable ; de plus, un εNFA le
+reconnaissant se déduit algorithmiquement d'une expression rationnelle
+le désignant.
+\end{prop}
+\begin{proof}
+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}.
+\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).}
 
 
 %