diff options
| -rw-r--r-- | notes-inf105.tex | 124 |
1 files changed, 72 insertions, 52 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 3e2e511..e027205 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -1049,8 +1049,10 @@ eux. \thingy Un \textbf{automate fini déterministe à spécification incomplète} ou \textbf{...partielle}, ou simplement \textbf{automate - fini déterministe incomplet}, en abrégé \textbf{DFAI}, sur un -alphabet $\Sigma$ est la donnée + fini déterministe incomplet}\footnote{Le mot « incomplet » signifie + en fait « non nécessairement complet », i.e., l'automate a le droit + de manquer certaines transitions, il peut très bien être complet.}, +en abrégé \textbf{DFAI}, sur un alphabet $\Sigma$ est la donnée \begin{itemize} \item d'un ensemble fini $Q$ d'états, \item d'un état initial $q_0 \in Q$, @@ -1059,7 +1061,8 @@ alphabet $\Sigma$ est la donnée « fonction partielle » $f\colon X\dasharrow Y$, où $X, Y$ sont deux ensembles est, par définition, la même chose qu'une fonction $f\colon D\to Y$ où $D\subseteq X$ est un sous-ensemble de $X$ - appelé \textbf{ensemble de définition} de $f$.} $\delta \colon + appelé \textbf{ensemble de définition} de $f$. (Lorsque en fait + $D=X$, la fonction est dite « totale ».)} $\delta \colon Q\times\Sigma \dasharrow Q$, \end{itemize} autrement dit, la seule différence avec la définition faite @@ -1228,6 +1231,10 @@ co-accessibles (on les dit aussi \textbf{utiles}) est parfois appelé \textbf{émondé}. On peut émonder un DFAI en ne conservant que ses états utiles : ainsi, tout DFAI est équivalent à un DFAI émondé. +\thingy Il faut prendre garde au fait que certains auteurs définissent +les automates finis déterministes comme étant complets, d'autres comme +étant incomplets. + \subsection{Automates finis non-déterministes (=NFA)} @@ -1254,7 +1261,7 @@ la relation de transition du NFA comme le graphe de la fonction de transition du DFAI (c'est-à-dire $(q,x,q') \in \delta_{\mathrm{NFA}}$ lorsque $\delta_{\mathrm{DFAI}}(q,x)$ est défini et vaut $q'$). -\thingy Graphiquement, on représente un NFA comme un DFA comme un +\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 @@ -1716,11 +1723,11 @@ plus, un DFA reconnaissant l'un se déduit algorithmiquement d'un DFA reconnaissant l'autre. \end{prop} \begin{proof} -Par hypothèse, il existe un DFA $A = (Q,q_0,F,\delta)$ tel que $L = -L_A$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = Q$, -l'état initial $q'_0 = q_0$, la fonction de transition $\delta' = -\delta$ et pour seul changement l'ensemble d'états finaux $F' = Q -\setminus F$ complémentaire de $F$. +Par hypothèse, il existe un DFA (complet !) $A = (Q,q_0,F,\delta)$ tel +que $L = L_A$. Considérons le DFA $A'$ défini par l'ensemble d'états +$Q' = Q$, l'état initial $q'_0 = q_0$, la fonction de transition +$\delta' = \delta$ et pour seul changement l'ensemble d'états finaux +$F' = Q \setminus F$ complémentaire de $F$. Si $w \in \Sigma^*$, on a $w \in L_{A'}$ si et seulement si $\delta^{\prime*}(q_0,w) \in F'$, c'est-à-dire $\delta^*(q_0,w) \in @@ -1732,7 +1739,11 @@ L_A$. Ceci montre bien que $L_{A'}$ est le complémentaire de $L_A$. \thingy Cette démonstration a utilisé la caractérisation des langages 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 ? +d'arriver (simplement) à la même conclusion. Il est intéressant de +réfléchir à pourquoi. (Essentiellement, dans un NFA, un mot est +accepté dès qu'\emph{il existe} un chemin qui l'accepte, or +l'existence d'un chemin aboutissant à un état non-final n'est pas la +même chose que l'inexistence d'un chemin aboutissant à un état final.) \begin{prop}\label{dfa-union-and-intersection} Si $L_1,L_2$ sont des langages reconnaissables (sur un même @@ -1742,36 +1753,45 @@ l'un comme l'autre se déduit algorithmiquement de DFA reconnaissant $L_1$ et $L_2$. \end{prop} \begin{proof} -Par hypothèse, il existe des DFA $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et -$A_2 = (Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 = +Traitons le cas de l'intersection. Par hypothèse, il existe des DFA +(complets !) $A_1 = (Q_1,q_{0,1},F_1,\delta_1)$ et $A_2 = +(Q_2,q_{0,2},F_2,\delta_2)$ tels que $L_1 = L_{A_1}$ et $L_2 = L_{A_2}$. Considérons le DFA $A'$ défini par l'ensemble d'états $Q' = -Q_1 \times Q_2$, l'état initial $q'_0 = (q_{0,1},q_{0,2})$, la -fonction de transition $\delta' \colon ((p_1,p_2),x) \mapsto -(\delta_1(p_1,x), \delta_2(p_2,x))$ et pour ensemble d'états finaux -$F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ (si on cherche à -reconnaître $L_1\cup L_2$) respectivement $F' = F_1\times F_2$ (si on -cherche à reconnaître $L_1\cap L_2$). Remarquons que $(p_1,p_2) \in -Q'$ appartient à $F' = (F_1\times Q_2) \cup (Q_1 \times F_2)$ -respectivement $F' = F_1\times F_2$ si et seulement si $p_1 \in F_1$ -ou $p_2 \in F_2$ respectivement $p_1 \in F_1$ et $p_2 \in F_2$. Par -ailleurs, si $w\in \Sigma^*$, on a $\delta'(q_0',w) = -(\delta_1(q_{0,1},w), \delta_2(q_{0,2},w))$. On voit donc qu'un mot -$w$ appartient à $L_{A'}$ si et seulement il appartient à $L_1 \cup -L_2$ respectivement $L_1 \cap L_2$, ce qu'il fallait démontrer. +Q_1 \times Q_2$ (c'est-à-dire l'ensemble des couples formés d'un état +de $A_1$ et d'un état de $A_2$), l'état initial $q'_0 = +(q_{0,1},q_{0,2})$, la fonction de transition $\delta' \colon +((p_1,p_2),x) \mapsto (\delta_1(p_1,x), \delta_2(p_2,x))$ et pour +ensemble d'états finaux $F' = F_1\times F_2$. Remarquons que +$(p_1,p_2) \in Q'$ appartient à $F' = F_1\times F_2$ si et seulement +si $p_1 \in F_1$ \emph{et} $p_2 \in F_2$ (i.e., $F' \subseteq Q'$ est +l'ensemble des couples dont les deux composantes sont finales). Par +ailleurs, si $w\in \Sigma^*$, on a $\delta^{\prime*}(q_0',w) = +(\delta_1^*(q_{0,1},w), \delta_2^*(q_{0,2},w))$, et par ce qui vient +d'être dit, ceci appartient à $F'$ si et seulement +$\delta_1^*(q_{0,1},w) \in F_1$ et $\delta_2^*(q_{0,2},w) \in F_2$. +On voit donc qu'un mot $w$ appartient à $L_{A'}$ si et seulement il +appartient à la fois à $L_1$ et à $L_2$, ce qu'il fallait démontrer. + +Pour la réunion, on peut invoquer le fait que la réunion est le +complémentaire de l'intersection des complémentaires, et +utiliser \ref{dfa-complement} ; si on déroule cette démonstration, on +voit qu'on construit un DFA $A''$ exactement égal à $A'$ construit +ci-dessus, à la seule différence près que son ensemble d'états finaux +est $F'' = (F_1\times Q_2) \cup (Q_1\times F_2)$, qui est le +sous-ensemble de $Q'' = Q_1\times Q_2$ formé des couples dont +\emph{l'une au moins} des deux composantes est finale. \end{proof} -\thingy On pouvait aussi traiter uniquement l'une des deux opérations -booléennes et déduire l'autre par complémentaire, mais le gain de -place est faible (et la construction est exactement la même). +\thingy La construction $A'$ ci-dessus est parfois appelée +\emph{produit} des DFA $A_1$ et $A_2$. -La construction ci-dessus est un \emph{produit} de DFA (que ce soit -pour prendre la réunion ou l'intersection). La construction produit -fonctionnerait encore avec les NFA \emph{pour la réunion de langages - mais pas pour l'intersection} : il est intéressant de réfléchir à -pourquoi (essentiellement, ce qui casse la symétrie est que dans un -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). +La construction de l'automate produit pour fabriquer le langage +intersection utilise la caractérisation des langages reconnaissables +par les DFA : elle aurait aussi fonctionné pour les DFAI mais pas pour +les NFA ; il est intéressant de réfléchir à pourquoi. (Une +construction du type produit pourrait fonctionner sur les NFA pour le +langage réunion, mais elle n'a aucun intérêt par rapport à la +construction présentée en \ref{nfa-union}.) \begin{prop}\label{nfa-mirror} Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors @@ -2259,12 +2279,12 @@ factorisation $t = uvw$ en trois facteurs $u,v,w$ où : \end{itemize} \end{prop} \begin{proof} -Soit $A$ un DFA qui reconnaît $L$, et soit $k$ son nombre d'états : on -va montrer que $k$ vérifie les propriétés énoncées. Pour cela, soit -$t = x_1 \cdots x_n$ un mot de $L$ de longueur $n \geq k$, et soient -$q_0,\ldots,q_n$ les états traversés par $A$ pendant la consommation -de $t$, autrement dit, $q_0$ est l'état initial, et $q_j = -\delta(q_{j-1}, x_j)$ pour chaque $1\leq j\leq n$ ; l'état $q_n = +Soit $A$ un DFA (complet) qui reconnaît $L$, et soit $k$ son nombre +d'états : on va montrer que $k$ vérifie les propriétés énoncées. Pour +cela, soit $t = x_1 \cdots x_n$ un mot de $L$ de longueur $n \geq k$, +et soient $q_0,\ldots,q_n$ les états traversés par $A$ pendant la +consommation de $t$, autrement dit, $q_0$ est l'état initial, et $q_j += \delta(q_{j-1}, x_j)$ pour chaque $1\leq j\leq n$ ; l'état $q_n = \delta^*(q_0, t)$ est final puisque $t \in L$. Comme $n+1 > k$ et comme l'automate $A$ a $k$ états, par le principe des tiroirs, il existe $j_1\neq j_2$ tels que $q_{j_1} = q_{j_2}$ : pour être plus @@ -2384,11 +2404,11 @@ Alors : \item le langage $L$ est rationnel si et seulement si la relation d'équivalence $\equiv$ possède un nombre \emph{fini} $k$ de classes d'équivalence, -\item lorsque c'est le cas, il existe un DFA ayant $k$ états qui - reconnaît $L$, il est unique à renommage des +\item lorsque c'est le cas, il existe un DFA (complet) ayant $k$ états + qui reconnaît $L$, il est unique à renommage des états\footnote{C'est-à-dire, si on préfère ce terme, isomorphisme - d'automates.} près, et il n'existe pas de DFA ayant $<k$ états qui - reconnaisse $L$. + d'automates.} près, et il n'existe pas de DFA (complet) ayant $<k$ + états qui reconnaisse $L$. \end{itemize} \end{thm} \begin{proof} @@ -2456,12 +2476,12 @@ isomorphisme d'automates (un renommage des états). \end{proof} \thingy Ce théorème affirme donc qu'il existe (à renommage des états -près) un unique DFA ayant un nombre minimal d'états parmi ceux qui -reconnaissent le langage rationnel $L$ : on l'appelle \textbf{automate - canonique} ou \textbf{automate minimal} du langage $L$. La -démonstration ci-dessus en donne une construction à partir d'une -relation d'équivalence, mais cette démonstration n'est pas -algorithmique : on va voir comment on peut le construire de fącon +près) un unique DFA (complet) ayant un nombre minimal d'états parmi +ceux qui reconnaissent le langage rationnel $L$ : on l'appelle +\textbf{automate canonique} ou \textbf{automate minimal} du +langage $L$. La démonstration ci-dessus en donne une construction à +partir d'une relation d'équivalence, mais cette démonstration n'est +pas algorithmique : on va voir comment on peut le construire de fącon algorithmique à partir d'un DFA quelconque qui reconnaît $L$. \begin{prop} |