Reread sections on recognizable languages: various updates, clarifications, fixes.

1 files changed, 86 insertions, 49 deletions

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 961a916..b51e3c5 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1856,7 +1856,7 @@ comme un élément de $Q'$) ; et on pose $F' = \{\mathbf{q}\subseteq Q
 de $A'$ sont les états $\mathbf{q}$ qui, vus comme des ensembles
 d'états de $A$, contiennent \emph{au moins un} état final.  Enfin,
 pour $\mathbf{q}\subseteq Q$ et $x \in \Sigma$, on définit
-$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q}\;
+$\delta'(\mathbf{q},x) = \{q_1\in Q : \exists q_0\in\mathbf{q}\,
 ((q_0,x,q_1) \in \delta)\}$ comme l'ensemble de tous les états $q_1$
 de $A$ auxquels on peut accéder depuis un état $q_0$ dans $\mathbf{q}$
 par une transition $(q_0,x,q_1)$ (étiquetée par $x$) de $A$.
@@ -1895,7 +1895,7 @@ procéduire suivante :
   $\mathbf{q}$, et, pour chaque lettre $x\in\Sigma$,
 \begin{itemize}
 \item calculer l'ensemble $\mathbf{q}' = \{q_1\in Q : \exists
-  q_0\in\mathbf{q}\; ((q_0,x,q_1) \in \delta)\}$ (en listant tous les
+  q_0\in\mathbf{q}\, ((q_0,x,q_1) \in \delta)\}$ (en listant tous les
   triplets $(q_0,x,q_1) \in\delta$ dont le premier élément est
   dans $\mathbf{q}$ et le second élément est $x$),
 \item si $\mathbf{q}'$ n'existe pas déjà comme état de $A'$, l'y
@@ -2429,16 +2429,16 @@ 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$.
+étiquetée, et de même cible, 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$.
+disjointe\footnote{C'est-à-dire qu'on exige que $q_0$ n'appartienne
+  pas à $Q$ (c'est un nouvel état).}), et $\delta'$ est la réunion de
+l'ensemble des transitions $(q,x,q')$ qui étaient déjà dans $\delta$
+et de l'ensemble 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}
@@ -2559,11 +2559,12 @@ 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$.
+$\varphi_2\colon Q_2 \to Q'$ de façon analogue.  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,q'\in Q_1$ et des
+$(\varphi_2(q),x,q')$ où $q,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
@@ -2596,8 +2597,8 @@ 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 \emph{chaque} état final de $A_1$.
-Graphiquement :
+étiquetée, et de même cible, partant de \emph{chaque} état final
+de $A_1$.  Graphiquement :
 
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(A.base)]
@@ -2694,9 +2695,9 @@ 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à :
+sortant de $q_0$, une transition identiquement étiquetée, et de même
+cible, 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,baseline=(A.base)]
@@ -2751,7 +2752,7 @@ 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
+(éventuellement nul) de chemins de l'état initial à un état final
 dans $A$.  On a donc bien $L_{A'} = L^*$.
 \end{proof}
 
@@ -3204,13 +3205,19 @@ de \ref{removal-of-epsilon-transitions}, suivie de la suppression des
 rationnelle conduit à l'automate de Glushkov de cette même expression.
 \end{prop}
 
+Sans que cela constitue une démonstration, on peut comprendre l'idée
+en considérant les « remarques » qui ont été faites dans la
+démonstration de \ref{nfa-union}, \ref{nfa-concatenation}
+et \ref{nfa-star}.
+
 
 
 
 \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA), algorithme d'élimination des états}\label{subsection-rnfa-and-kleenes-algorithm}
 
 \thingy On cherche dans cette section à montrer la réciproque
-de \ref{rational-languages-are-recognizable}.  On va pour cela donner
+de \ref{rational-languages-are-recognizable}, c'est-à-dire, que les
+langages rationnels sont reconnaissables.  On va pour cela donner
 un algorithme (très coûteux !) qui transforme un automate en
 expression rationnelle (dénotant le langage qu'il reconnaît).  Cette
 algorithme « d'élimination des états » fonctionne naturellement sur
@@ -3353,9 +3360,9 @@ rationnelle $r$ sur $\Sigma$ qui dénote le langage reconnu par $A$,
 soit $L_r = L_A$.  De plus, $r$ se déduit algorithmiquement de $A$.
 \end{prop}
 \begin{proof}
-On a vu qu'on pouvait considérer une expression rationnelle comme un
-RNFA ayant un unique état initial, un unique état final, et une unique
-transition de l'un vers l'autre (étiquetée par l'expression
+On a expliqué qu'on pouvait considérer une expression rationnelle
+comme un RNFA ayant un unique état initial, un unique état final, et
+une unique transition de l'un vers l'autre (étiquetée par l'expression
 rationnelle en question).  On va construire montrer que $A$ est
 équivalent à un RNFA de cette nature, ce qui montrera bien qu'il est
 équivalent à une expression rationnelle.
@@ -3450,8 +3457,11 @@ l'automate, au moins dans le pire cas, mais aussi dans beaucoup de cas
 \thingy\label{example-of-state-elimination} À titre d'exemple,
 considérons le DFA suivant sur l'alphabet $\{0,1\}$, qui reconnaît les
 suites binaires qui représentent un nombre multiple de $3$ écrit en
-binaire (en convenant que le mot vide est une représentation binaire
-du nombre $0$, ce qui est logique) :
+binaire\footnote{Les états $0,1,2$ représentent respectivement les
+  états dans lesquels le nombre binaire lu jusqu'à présent par
+  l'automate est congru à $0,1,2$ modulo $3$.} (en convenant que le
+mot vide est une représentation binaire du nombre $0$, ce qui est
+logique) :
 
 \begin{center}
 %%% begin example6 %%%
@@ -3540,11 +3550,11 @@ Récapitulons le contenu essentiel à retenir comme conséquence
 immédiate de \ref{rational-languages-are-recognizable}
 et \ref{recognizable-languages-are-rational} :
 
-\begin{cor}[Kleene]\label{kleenes-theorem}\index{Kleene (théorème de)}
+\begin{thm}[Kleene]\label{kleenes-theorem}\index{Kleene (théorème de)}
 La classe des langages rationnels et celle des langages
 reconnaissables coïncident.  (On pourra donc considérer ces termes
 comme synonymes.)
-\end{cor}
+\end{thm}
 
 Il faut cependant retenir que s'il y a, mathématiquement, équivalence
 entre ces deux classes de langages, cette équivalence \emph{a un coût
@@ -3555,6 +3565,32 @@ exponentielle dans le pire cas.  Il est donc pertinent, en
 informatique, de ne pas considérer les descriptions d'un langage par
 une expression rationnelle, un DFA, et un NFA, comme interchangeables.
 
+\thingy Une conséquence de \ref{kleenes-theorem} est, par exemple, que
+le complémentaire d'un langage rationnel est rationnel
+(cf. \ref{dfa-complement}) ou que l'intersection de deux langages
+rationnels est rationnelle (cf. \ref{dfa-union-and-intersection}), et
+que ces opérations se calculent algorithmiquement.  Il est donc
+possible, en principe, à partir d'une expression rationnelle $r$ (sur
+un alphabet $\Sigma$), de fabriquer algorithmiquement une expression
+rationnelle $r'$ (« négation » de $r$) qui dénote le langage
+complémentaire de celui dénoté par $r$ ; et de même, à partir
+d'expressions rationnelles $r_1,r_2$, de fabriquer algorithmiquement
+une expression rationnelle $r''$ (« conjonction » de $r_1$ et $r_2$)
+qui dénote le langage intersection de ceux dénotés par $r_1$ et $r_2$.
+
+Le coût de ces opérations, cependant, est astronomique : doublement
+exponentiel, puisqu'il s'agit de convertir l'expression en NFA, de
+déterminiser le NFA en DFA (à un premier coût exponentiel),
+d'effectuer l'opération sur un DFA, et de reconvertir le DFA en
+expression rationnelle (à un deuxième coût exponentiel).  Ce n'est pas
+faute d'avoir les bons algorithmes : on peut montrer qu'il existe
+effectivement des familles d'expressions rationnelles pour lesquelles
+la négation ou la conjonction produisent une augmentation de taille
+doublement exponentielle.
+
+%% Gelade & Neven (STACS 2008),
+%% "Succinctness of the Complement and Intersection of Regular Expressions"
+
 
 \subsection{Le lemme de pompage}
 
@@ -3680,8 +3716,8 @@ doit démontrer un tel énoncé, mais la démonstration a été faite
 ci-dessus et il est donc plus fréquent de devoir appliquer le lemme de
 pompage.
 
-Le modèle d'une démonstration par l'absurde pour montrer qu'un langage
-$L$ n'est pas rationnel est donc quelque chose comme ceci :
+\thingy Le modèle d'une démonstration par l'absurde pour montrer qu'un
+langage $L$ n'est pas rationnel est donc quelque chose comme ceci :
 \begin{itemize}
 \item on entame un raisonnement par l'absurde en supposant que $L$ est
   rationnel, et on choisit $L$ pour appliquer le lemme de pompage
@@ -3716,8 +3752,9 @@ l'existence.  Considérons le mot $t := a^k b^k$ : il doit alors
 exister une factorisation $t = uvw$ pour laquelle on a (i) $|v|\geq
 1$, (ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$.  La
 propriété (ii) assure que $uv$ est formé d'un certain nombre de
-répétitions de la lettre $a$ : disons $u = a^\ell$ et $v = a^m$, si
-bien que $w = a^{k-\ell-m} b^k$.  La propriété (ii) donne $m\geq 1$.
+répétitions de la lettre $a$ (car tout préfixe de longueur $\leq k$ de
+$a^k b^k$ est de cette forme) ; disons $u = a^\ell$ et $v = a^m$, si
+bien que $w = a^{k-\ell-m} b^k$.  La propriété (i) donne $m\geq 1$.
 Enfin, la propriété (iii) affirme que le mot $uv^iw = a^{k+(i-1)m}
 b^k$ appartient à $L$ ; mais dès que $i\neq 1$, ceci est faux : il
 suffit donc de prendre $i=0$ pour avoir une contradiction.
@@ -3784,7 +3821,7 @@ l'ensemble $\{[u] : u\in L\}$ des classes incluses dans $L$.  Enfin
 remarquons que si $u\equiv v$ (pour $u,v\in\Sigma^*$) et $x\in\Sigma$,
 on a encore $ux \equiv vx$ (en effet, $uxt \in L \liff vxt \in L$ pour
 tout $t\in L$) : il y a donc un sens à définir $\delta([u], x) =
-[ux]$.  On a ainsi fabriqué un automate fini $A = (Q,q_0,F,\delta)$.
+[ux]$.  On a ainsi fabriqué un DFA $A = (Q,q_0,F,\delta)$.
 Vues les définitions de $q_0$ et $\delta$, il est clair que
 $\delta^*(q_0,w) = [w]$ pour cet automate, et vue la définition de
 $F$, on a $\delta^*(q_0,w) \in F$ si et seulement si $w\in L$.  Ceci
@@ -3800,12 +3837,13 @@ d'équivalence $\mathrel{\equiv_B}$ sur $\Sigma^*$ par : $u
 \delta_B^*(q_{0,B}, v)$ (autrement dit, les mots $u$ et $v$ mettent
 l'automate $B$ dans le même état).  Si on a $u \mathrel{\equiv_B} v$,
 on a aussi $u \equiv v$ : en effet, pour tout $t\in L$ on a
-$\delta_B^*(q_{0,B}, ut) = \delta_B^*(q_{0,B}, vt)$, et notamment le
-membre de gauche appartient à $F_B$ si et seulement si le membre de
-droite y appartient, c'est-à-dire que $ut\in L \liff vt\in L$.  On
-vient donc de montrer que $u \mathrel{\equiv_B} v$ implique $u \equiv
-v$ (la relation $\equiv_B$ est \emph{plus fine} que $\equiv$) : si on
-préfère, chaque classe d'équivalence pour $\equiv$ est donc une
+$\delta_B^*(q_{0,B}, ut) = \delta_B^*(\delta_B^*(q_{0,B}, u), t) =
+\delta_B^*(\delta_B^*(q_{0,B}, v), t) = \delta_B^*(q_{0,B}, vt)$, et
+notamment le membre de gauche appartient à $F_B$ si et seulement si le
+membre de droite y appartient, c'est-à-dire que $ut\in L \liff vt\in
+L$.  On vient donc de montrer que $u \mathrel{\equiv_B} v$ implique $u
+\equiv v$ (la relation $\equiv_B$ est \emph{plus fine} que $\equiv$) :
+si on préfère, chaque classe d'équivalence pour $\equiv$ est donc une
 réunion de classes d'équivalences pour $\equiv_B$.  Notamment, comme
 $\equiv_B$ a un nombre fini de classes d'équivalence (puisque
 $\delta_B^*(q_{0,B}, u)$ ne peut prendre qu'un nombre fini de valeurs,
@@ -4060,7 +4098,8 @@ d'aller vers l'état $3$), c'est-à-dire :
 \end{center}
 
 \noindent alors la minimisation ne sépare pas les états $0$ et $1$, et
-on obtient
+on obtient (le même automate qu'en \ref{discussion-example2}, à
+savoir) :
 
 \begin{center}
 %%% begin example7bm %%%
@@ -4249,15 +4288,14 @@ contient que des terminaux.
 
 \thingy Intuitivement, il faut comprendre la grammaire de la manière
 suivante.  Les règles $(T,\alpha)$, où on rappelle que $T$ est un
-symbole nonterminal et $\alpha$ un pseudo-mot (et on notera $T
-\rightarrow \alpha$, cf. ci-dessous) doivent se comprendre
-intuitivement comme « le symbole $T$ peut être remplacé
-par $\alpha$ ».  On part de l'axiome $S$, et on peut effectuer
-librement des substitutions $T \rightarrow \alpha$ (consistant à
-remplacer un nonterminal $T$ par un pseudo-mot $\alpha$) autorisées
-par les règles : le langage défini par la grammaire est l'ensemble de
-tous les mots (ne comportant plus aucun nonterminal) qu'on peut
-obtenir de la sorte.
+symbole nonterminal et $\alpha$ un pseudo-mot doivent se comprendre
+intuitivement comme « le symbole $T$ peut être remplacé par $\alpha$ »
+(et on notera $T \rightarrow \alpha$, cf. ci-dessous).  On part de
+l'axiome $S$, et on peut effectuer librement des substitutions $T
+\rightarrow \alpha$ (consistant à remplacer un nonterminal $T$ par un
+pseudo-mot $\alpha$) autorisées par les règles : le langage défini par
+la grammaire est l'ensemble de tous les mots (ne comportant plus aucun
+nonterminal) qu'on peut obtenir de la sorte.
 
 Rendons maintenant cette définition précise :
 
@@ -5076,7 +5114,6 @@ factorisation $t = uvwxy$ en cinq facteurs $u,v,w,x,y$ où :
 \item[(iii)] pour tout $i\geq 0$ on a $uv^iwx^iy \in L$.
 \end{itemize}
 \end{prop}
-\begin{proof}\textcolor{red}{(Omise.)}\end{proof}
 
 Donnons maintenant un exemple d'utilisation du lemme :