diff options
| -rw-r--r-- | notes-inf105.tex | 135 |
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 : |