summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-31 22:56:39 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-10-31 22:56:39 (GMT)
commit24527475fbf2fa526f8142edc08615ae73d94600 (patch)
tree3b1d0778019bd0f2bad1cc235cbe439a089a71cc /notes-inf105.tex
parent2c1c106024f4737086c629b802dff15bc1daa4df (diff)
downloadinf105-24527475fbf2fa526f8142edc08615ae73d94600.zip
inf105-24527475fbf2fa526f8142edc08615ae73d94600.tar.gz
inf105-24527475fbf2fa526f8142edc08615ae73d94600.tar.bz2
Reread sections on recognizable languages: various updates, clarifications, fixes.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex135
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 :