diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 272 |
1 files changed, 257 insertions, 15 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 90a0889..f46a27a 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -53,7 +53,7 @@ % % NOTE: compile dot files with % dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot > file.tex -\tikzstyle{automaton}=[>=stealth',initial text={},every loop/.style={min distance=7mm,looseness=5}] +\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}] \tikzstyle{state}=[] \tikzstyle{final}=[accepting by arrow] % @@ -716,12 +716,12 @@ ou en abrégé \textbf{DFA} (pour \textit{deterministic finite \thingy Graphiquement, on représente un DFA comme un graphe orienté aux arêtes étiquetées par des éléments de $\Sigma$ : plus exactement, on trace un nœud pour chaque élément $q \in Q$, et lorsque -$\delta(q,x) = q'$ on introduit une arête $q \to q'$ étiquetée par la +$\delta(q,x) = q'$ on introduit une flèche $q \to q'$ étiquetée par la lettre $x$. La condition sur $\delta$ (pour être un DFA) est alors que, pour chaque état $q \in Q$ et chaque lettre $x \in \Sigma$, il existe une unique arête partant de $q$ et étiquetée par $x$. En -outre, on introduit une arête pointant de nulle part vers $q_0$, et -pour chaque $q\in F$ une arête pointant de $q$ vers nulle +outre, on introduit une flèche pointant de nulle part vers $q_0$, et +pour chaque $q\in F$ une flèche pointant de $q$ vers nulle part\footnote{Certains auteurs préfèrent d'autres conventions, par exemple celle consistant à entourer deux fois les états finaux.}. @@ -767,7 +767,7 @@ successivement dans les états $q_0$ puis $q_1 := \delta(q_0,x_1)$ puis $q_2 := \delta(q_1,x_2)$, et ainsi de suite jusqu'à $q_n := \delta(q_{n-1},x_n)$) ; on dit que l'automate effectue les transitions $q_0\to q_1$ (en consommant $x_1$) puis $q_1\to q_2$ (en -consommant $x_2$q) et ainsi de suite. Si $q_n$ est l'état dans lequel +consommant $x_2$) et ainsi de suite. Si $q_n$ est l'état dans lequel se trouve l'automate une fois qu'il a consommé le mot $w$, on dira que l'automate \emph{acepte} ou \emph{rejette} le mot selon que $q_n \in F$ ou que $q_n \not\in F$. @@ -986,10 +986,11 @@ $c{*}ac{*}bc{*}$.) \begin{prop} Soit $A = (Q,q_0,F,\delta)$ un DFAI sur un alphabet $\Sigma$. Alors -il existe un DFA $A' = (Q',q'_0,F',\delta')$ qui équivalent à $A$ au -sens où il reconnaît le même langage $L_{A'} = L_A$. De plus, $A'$ se -déduit algorithmiquement de $A$ en ajoutant au plus un état -\textbf{puits} à $A$ : on a $\#Q' \leq \#Q + 1$. +il existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même +alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît +le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit +algorithmiquement de $A$ en ajoutant au plus un état \textbf{puits} +à $A$ : on a $\#Q' \leq \#Q + 1$. \end{prop} \begin{proof} On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état @@ -1012,12 +1013,12 @@ $A'$ « tombe dans le puits » lorsque le DFAI $A$ cesse de fonctionner). En particulier, ils reconnaissent les mêmes langages. \end{proof} -On dit que le DFA $A'$ est obtenu en \textbf{complétant} le DFAI $A$ -lorsqu'il est obtenu par la procédure décrite par la démonstration de -cette proposition, c'est-à-dire par l'addition d'un état puits, sauf -si $A$ est déjà complet, auquel cas on convient qu'il est son propre -complété (i.e., on n'ajoute un puits que quand c'est réellement -nécessaire). +\thingy On dit que le DFA $A'$ est obtenu en \textbf{complétant} le +DFAI $A$ lorsqu'il est obtenu par la procédure décrite dans la +démonstration de cette proposition, c'est-à-dire par l'addition d'un +état puits, sauf si $A$ est déjà complet, auquel cas on convient qu'il +est son propre complété (i.e., on n'ajoute un puits que quand c'est +réellement nécessaire). \thingy À titre d'exemple, le DFA suivant représente la complétion du DFAI représenté en \ref{discussion-example2b} : @@ -1075,6 +1076,247 @@ co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé. +\subsection{Automates finis non-déterministes (=NFA)} + +\thingy Un \textbf{automate fini non-déterministe}, en abrégé +\textbf{NFA}, sur un alphabet $\Sigma$ est la donnée +\begin{itemize} +\item d'un ensemble fini $Q$ d'états, +\item d'un ensemble $I \subseteq Q$ d'états dits initiaux, +\item d'un ensemble $F \subseteq Q$ d'états dits finaux, +\item d'une \emph{relation} de transition $\delta \subseteq Q \times + \Sigma \times Q$ (c'est-à-dire une partie du produit cartésien $Q + \times \Sigma \times Q$, i.e., un ensemble de triplets $(q,x,q') \in + Q \times \Sigma \times Q$). +\end{itemize} +Autrement dit, on autorise maintenant un ensemble quelconque d'états +initiaux, et de même, au lieu qu'un état $q$ et un symbole $x$ +déterminent un unique état $q' = \delta(q,x)$, on a maintenant affaire +à un ensemble quelconque de triplets $(q,x,q')$. + +\thingy Graphiquement, on représente un NFA comme un DFA comme un +graphe orienté dont les nœuds sont les éléments de $Q$, et où on place +une arête étiquetée $x$ de $q$ vers $q'$ pour chaque triplet $(q,x,q') +\in \delta$ ; comme précédemment, on marque les états initiaux par une +flèche entrante (i.e., pointant de nulle part) et les états finaux par +une flèche sortante (i.e., pointant vers nulle part). + +\thingy Il faut comprendre le fonctionnement d'un NFA de la manière +suivante : un mot $w = x_1\cdots x_n$ est accepté par l'automate +lorsqu'\emph{il existe} un chemin conduisant d'\emph{un} état initial +à un état final et dont les arêtes sont étiquetées par les lettres +$x_1,\ldots,x_n$ de $w$ (dans l'ordre) ; autrement dit, $w$ est +accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ tels que $q_0 +\in I$ et $q_n\in F$ et $(q_{i-1},x_i,q_i) \in \delta$ pour +chaque $1\leq i\leq n$. + +Il existe plusieurs manières de reformuler ce comportement : on peut +par exemple dire que l'automate est dans plusieurs états à la fois, +qu'il commence dans tous les états initiaux à la fois, et qu'à chaque +fois qu'il consomme un symbole $x$, il effectue toutes les transitions +possibles à partir d'un état où et étiquetées par ce symbole, et qu'au +bout du compte l'automate accepte le mot lorsqu'il est dans \emph{au + moins un} état acceptant (même s'il est, par ailleurs, dans d'autres +états). C'est cette façon de voir les choses qui conduira à +l'équivalence entre NFA et DFA (cf. \ref{determinization-of-nfa}). + +Une autre façon de présenter les choses est que l'automate « devine » +par quel état initial commencer, et à chaque symbole consommé, +« devine » quelle transition effectuer, de manière à accepter le mot +si c'est possible. + +En tout état de cause, la définition formelle va être donnée +ci-dessous. + +\thingy Si $A = (Q,I,F,\delta)$ est un NFA sur l'alphabet $\Sigma$, on +définit une relation $\delta^* \subseteq Q \times \Sigma^* \times Q$ +par $(q,w,q') \in \delta^*$ lorsque $w = x_1\cdots x_n$ et qu'il +existe $(q_0,\ldots,q_n)$ tels que $q_0 = q$ et $q_n = q'$ et +$(q_{i-1},x_i,q_i) \in \delta$ pour chaque $1\leq i\leq n$ ; ou, ce +qui revient au même (par récurrence sur la longueur de $w$) : +\begin{itemize} +\item $(q,\varepsilon,q') \in \delta^*$ si et seulement si $q'=q$, +\item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q_1$ tel + que $(q,w,q_1) \in \delta^*$ et $(q_1,x,q') \in \delta$. +\end{itemize} + +Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ +et $q_\infty\in F$ tels que $(q_0,w,q_\infty) \in \delta^*$. Le +langage accepté $L_A$ et l'équivalence de deux automates sont définis +de façon analogue aux DFA +(cf. \ref{definition-recognizable-language}). + +\thingy\label{discussion-example4} Pour illustrer le fonctionnement +des NFA, considérons l'automate à trois états sur $\Sigma=\{a,b\}$ +représenté par la figure suivante : on a $Q = \{0,1,2\}$ avec +$I=\{0\}$ et $F=\{2\}$ et $\delta = \{(0,a,0),\penalty0 +(0,b,0),\penalty-100 (0,a,1),\penalty-50 (1,a,2),\penalty0 (1,b,2)\}$. + +\begin{center} +%%% begin example4 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (98bp,18bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$}; + \node (q2) at (188bp,18bp) [draw,circle,state,final] {$2$}; + \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp) .. node[auto] {$a$} (q1); + \draw [->] (q1) ..controls (128.76bp,18bp) and (145.63bp,18bp) .. node[auto] {$a,b$} (q2); + \draw [->] (q0) to[loop above] node[auto] {$a,b$} (q0); +% +\end{tikzpicture} + +%%% end example4 %%% +\end{center} + +Cet automate n'est pas déterministe car il existe deux transitions +étiquetées $a$ partant de l'état $0$. En considérant les différents +chemins possibles entre $0$ et $2$ dans ce graphe, on comprend que le +langage qu'il reconnaît est le langage des mots sur $\{a,b\}$ dont +l'avant-dernière lettre est un $a$ (c'est aussi le langage désigné par +l'expression rationnelle $(a|b){*}a(a|b)$). Une façon de présenter le +non-déterminisme est que l'automate « devine », quand il est dans +l'état $0$ et qu'on lui fait consommer un $a$, si ce $a$ sera +l'avant-dernière lettre, et, dans ce cas, passe dans l'état $1$ pour +pouvoir accepter le mot. + +\begin{prop}\label{determinization-of-nfa} +Soit $A = (Q,I,F,\delta)$ un NFA sur un alphabet $\Sigma$. Alors il +existe un DFA $A' = (Q',q'_0,F',\delta')$ (sur le même +alphabet $\Sigma$) qui soit équivalent à $A$ au sens où il reconnaît +le même langage $L_{A'} = L_A$. De plus, $A'$ se déduit +algorithmiquement de $A$ avec une augmentation au plus exponentielle +du nombre d'états : $\#Q' \leq 2^{\#Q}$. +\end{prop} +\begin{proof} +On définit $Q' = \mathscr{P}(Q) = \{\mathbf{q} \subseteq Q\}$ +l'\emph{ensemble des parties} de $Q$ : c'est ce qui servira d'ensemble +d'états du DFA $A'$ qu'on construit (i.e., un état de $A'$ est un +ensemble d'états de $A$ — intuitivement, c'est l'ensemble des états +dans lesquels on se trouve simultanément). On pose $q'_0 = I$ et $F' += \{\mathbf{q}\subseteq Q :\penalty-100 \mathbf{q}\cap F +\neq\varnothing\}$ l'ensemble des états de $A'$ 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} +((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$. + +Il est alors facile de voir (par récurrence sur $|w|$) que +$\delta^{\prime*}(\mathbf{q},w)$ est l'ensemble de tous les les états +$q_1 \in Q$ tels que $(q_0,w,q_1)\in\delta^*$, i.e., auxquels on peut +accéder depuis un état $q_0$ dans $\mathbf{q}$ par une suite de +transitions de $A$ étiquetées par les lettres de $w$. En particulier, +$\delta^{\prime*}(I,w)$ est l'ensemble de tous les états de $A$ +auxquels on peut accéder depuis un état initial de $A$ par une suite +de transitions de $A$ étiquetées par les lettres de $w$ : le mot $w$ +appartient à $L_A$ si et seulement si cet ensemble contient un élément +de $F$, ce qui par définition de $F'$ signifie exactement +$\delta^{\prime*}(I,w) \in F'$. On a bien prouvé $L_{A'} = L_A$. + +Enfin, $\#Q' = \#\mathscr{P}(Q) = 2^{\#Q}$ (car une partie de $Q$ peut +se voir comme sa fonction indicatrice, qui est une fonction $Q \to +\{0,1\}$). +\end{proof} + +\thingy On dit que le DFA $A'$ est obtenu en \textbf{déterminisant} le +NFA $A$ lorsqu'il est obtenu par la procédure décrite dans la +démonstration de cette proposition en ne gardant que les états +accessibles. + +Algorithmiquement, la déterminisation de $A$ s'obtient par la +procéduire suivante : +\begin{itemize} +\item créer une file (ou une pile) d'ensembles d'états de $A$ ; + initialiser cette file avec le seul élément $I$ (vu comme un + sous-ensemble de $Q$) ; et créer l'automate $A'$ avec initialement + l'unique état $I$, marqué comme état initial, et aussi comme final + s'il contient un état final de $A$ ; +\item tant que la file/pile n'est pas vide : en extraire un élément + $\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 + triplets $(q_0,x,q_1)$ 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 + ajouter, et dans ce cas, l'ajouter à la file/pile, et de plus, si + $\mathbf{q}'$ contient un état final de $A$, marquer cet état comme + final pour $A'$, +\item et ajouter à $A'$ la transition $\delta'(\mathbf{q},x) = + \mathbf{q}'$. +\end{itemize} +\end{itemize} + +La file/pile sert à stocker les états de $A'$ qui ont été créés mais +pour lesquels les transitions sortantes n'ont pas encore été +calculées. L'algorithme se termine quand la file/pile se vide, ce qui +se produit toujours en au plus $2^{\#Q}$ étapes car chaque $\mathbf{q} +\subseteq Q$ ne peut apparaître qu'une seule fois dans la file/pile. + +Il se peut que l'état $\varnothing$ soit créé : cet état servira +effectivement de puits, au sens où on aura $\delta'(\varnothing,x) = +\varnothing$ quel que soit $x$ (et l'état n'est pas acceptant). + +Il arrive souvent que l'automate déterminisé soit plus petit que les +$2^{\#Q}$ états qu'il a dans le pire cas. + +\thingy À titre d'exemple, déterminisons le NFA $A$ présenté +en \ref{discussion-example4} : on commence par construire un état +$\{0\}$ pour $A'$ car le NFA a $\{0\}$ pour ensemble d'états +initiaux ; on a $\delta'(\{0\},a) = \{0,1\}$ car $0$ et $1$ sont les +deux états auxquels on peut arriver dans $A$ par une transition +partant de $0$ et étiquetée par $a$, tandis que $\delta'(\{0\},b) = +\{0\}$ ; ensuite, $\delta'(\{0,1\},a) = \{0,1,2\}$ car $0,1,2$ sont +les trois états auxquels on peut arriver dans $A$ par une transition +partant de $0$ ou $1$ et étiquetée par $a$ ; et ainsi de suite. En +procédant ainsi, on constuit l'automate à $4$ états qui suit : + +\begin{center} +\footnotesize +%%% begin example4det %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\begin{scope} + \pgfsetstrokecolor{black} + \definecolor{strokecol}{rgb}{1.0,1.0,1.0}; + \pgfsetstrokecolor{strokecol} + \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; + \pgfsetfillcolor{fillcol} + \filldraw (0bp,0bp) -- (0bp,204bp) -- (274bp,204bp) -- (274bp,0bp) -- cycle; +\end{scope} + \node (q02) at (236bp,30bp) [draw,circle,state,final] {$\{0,2\}$}; + \node (q0) at (24bp,54bp) [draw,circle,state,initial] {$\{0\}$}; + \node (q01) at (123bp,94bp) [draw,circle,state] {$\{0,1\}$}; + \node (q012) at (236bp,134bp) [draw,circle,state,final] {$\{0,1,2\}$}; + \draw [->] (q01) ..controls (164.77bp,70.495bp) and (183.92bp,59.452bp) .. node[auto] {$b$} (q02); + \draw [->] (q0) ..controls (57.935bp,67.582bp) and (72.263bp,73.49bp) .. node[auto] {$a$} (q01); + \draw [->] (q0) to[loop above] node[auto] {$b$} (q0); + \draw [->] (q01) ..controls (163.68bp,108.3bp) and (177.52bp,113.29bp) .. node[auto] {$a$} (q012); + \draw [->] (q012) to[loop above] node[auto] {$a$} (q012); + \draw [->] (q02) ..controls (176.26bp,31.326bp) and (130.91bp,33.455bp) .. (92bp,39bp) .. controls (80.643bp,40.618bp) and (68.355bp,43.14bp) .. node[auto] {$a,b$} (q0); + \draw [->] (q012) ..controls (236bp,87.978bp) and (236bp,79.013bp) .. node[auto] {$b$} (q02); +% +\end{tikzpicture} + +%%% end example4det %%% +\end{center} + +On remarquera qu'on a construit moins que les $2^3 = 8$ états qu'on +pouvait craindre. + +Il est par ailleurs instructif de regarder comment fonctionne +l'automate $A'$ ci-dessus pour déterminer si l'avant-dernière lettre +d'un mot est un $a$ : intuitivement, l'état $\{0\}$ mémorise +l'information « la dernière lettre n'était pas un $a$, et la + précédente ne l'était pas », l'état $\{0,1\}$ mémorise « la dernière + lettre était un $a$, mais la précédente ne l'état pas », l'état +$\{0,1,2\}$ mémorise « les deux dernières lettres étaient des $a$ », +et l'état $\{0,2\}$ mémorise « la dernière lettre était un $b$, mais + la précédente était un $a$ ». + % % % |