diff options
| -rw-r--r-- | figs/example5ne.dot | 14 | ||||
| -rw-r--r-- | notes-inf105.tex | 118 |
2 files changed, 123 insertions, 9 deletions
diff --git a/figs/example5ne.dot b/figs/example5ne.dot new file mode 100644 index 0000000..8371593 --- /dev/null +++ b/figs/example5ne.dot @@ -0,0 +1,14 @@ +digraph example5ne { + rankdir="LR"; + node [texmode="math",shape="circle",style="state"]; + q0 [style="state,initial",label="0"]; + q1 [style="state",label="1"]; + q2 [style="state,final",label="2"]; + edge [texmode="math",lblstyle="auto"]; + q0 -> q0 [label="a",topath="loop above"]; + q0 -> q1 [label="b"]; + q1 -> q1 [label="b",topath="loop above"]; + q1 -> q2 [label="c"]; + q2 -> q2 [label="c",topath="loop above"]; + q0 -> q2 [label="c"]; +} diff --git a/notes-inf105.tex b/notes-inf105.tex index 1c9646f..1098ac5 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -918,6 +918,9 @@ en \ref{definition-dfa} est que la fonction $\delta$ est partielle, ce qui signifie qu'elle n'est pas obligatoirement définie sur tout couple $(q,x) \in Q\times\Sigma$. +(Un DFA est considéré comme un DFAI particulier où la fonction de +transition $\delta$ se trouve être définie partout.) + \thingy Graphiquement, on représente un DFAI comme un DFA, à la différence près que pour chaque $q\in Q$ et chaque $x\in \Sigma$, il y a maintenant \emph{au plus une} (et non plus exactement une) arête @@ -1095,6 +1098,13 @@ 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 Un DFAI (ou \textit{a fortiori} un DFA) est considéré comme un +NFA particulier en définissant l'ensemble des états initiaux du NFA +comme $I_{\mathrm{NFA}} = \{q_{0,\mathrm{DFAI}}\}$ et en définissant +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 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') @@ -1343,6 +1353,8 @@ autrement, \emph{un automate qui possède des $\varepsilon$-transitions La représentation graphique des εNFA est évidente (on utilisera le symbole « $\varepsilon$ » pour étiqueter les transitions spontanées). +Un NFA est considéré comme un εNFA particulier pour lequel il n'y a +pas de ε-transition. \thingy Un εNFA accepte un mot $w$ lorsqu'il existe un chemin conduisant d'un état initial à un état final et dont les arêtes sont @@ -1432,15 +1444,103 @@ nombre quelconque de $b$ suivi d'un nombre quelconque de $c$, ou, si on préfère, le langage désigné par l'expression rationnelle $a{*}b{*}c{*}$. -\thingy Si $q$ est un état d'un εNFA, on appelle -\textbf{$\varepsilon$-fermeture} de $q$ l'ensemble des états $q'$ (y -compris $q$ lui-même) accessibles depuis $q$ par une succession -quelconque de ε-transitions, c'est-à-dire, si on veut, $\{q'\in Q -:\penalty0 (q,\varepsilon,q') \in\delta^*\}$. On notera -temporairement $C(q)$ cet ensemble. (Par exemple, dans -l'exemple \ref{discussion-example5} ci-dessus, on a $C(0) = \{0,1,2\}$ -et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout NFA sans -ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) +\thingy Si $q$ est un état d'un εNFA, on appelle \textbf{ε-fermeture} +de $q$ l'ensemble des états $q'$ (y compris $q$ lui-même) accessibles +depuis $q$ par une succession quelconque de ε-transitions, +c'est-à-dire, si on veut, $\{q'\in Q :\penalty0 (q,\varepsilon,q') +\in\delta^*\}$. On notera temporairement $C(q)$ cet ensemble. (Par +exemple, dans l'exemple \ref{discussion-example5} ci-dessus, on a +$C(0) = \{0,1,2\}$ et $C(1) = \{1,2\}$ et $C(2) = \{2\}$. Dans tout +NFA sans ε-transitions, on a $C(q) = \{q\}$ pour tout état $q$.) + +Il est clair qu'on peut calculer algorithmiquement $C(q)$ (par exemple +par un algorithme de Dijkstra sur le graphe dont l'ensemble des +sommets est $Q$ et l'ensemble des arêtes est l'ensemble des +ε-transitions de $A$ : la ε-fermeture $C(q)$ est simplement l'ensemble +des sommets accessibles depuis $q$ dans ce graphe). + +\begin{prop}\label{removal-of-epsilon-transitions} +Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$. Alors il +existe un NFA $A' = (Q,I',F',\delta')$ (sur le même alphabet $\Sigma$) +ayant le même ensemble d'états $Q$ que $A$ et 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$. +\end{prop} +\begin{proof} +On pose $I' = I$ (mêmes états initiaux). L'idée est maintenant de +faire une transition $(q,x,q') \in \delta'$ à chaque fois qu'on peut +atteindre $q'$ à partir de $q$ dans $A$ par une suite quelconque de +ε-transitions suivie d'une unique transition étiquetée par $x$, +autrement dit, $(q,\varepsilon,q^\sharp) \in \delta^*$ (c'est-à-dire +$q^\sharp \in C(q)$) et $(q^\sharp,x,q') \in \delta$. + +On définit donc $\delta' \subseteq Q\times\Sigma\times Q'$ par +$(q,x,q') \in \delta'$ lorsqu'il existe $q^\sharp \in C(q)$ tel que +$(q^\sharp,x,q') \in \delta$ : autrement dit, pour créer les +transitions $q\to q'$ dans $A'$, on parcourt tous les $q^\sharp \in +C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$ dans $A'$ +lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée par ce $x$ +dans $A$. De même, on définit $F' \subseteq Q$ comme l'ensemble des +$q\in Q$ tels que $C(q) \cap F \neq \varnothing$, c'est-à-dire, qu'on +peut atteindre un état final par une succession de ε-transitions. + +Si on a un chemin $q_0 \to q_1 \to \cdots \to q_n$ dans $A$ menant +d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et +étiquetées par $t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ +(c'est-à-dire $(q_{i-1},t_i,q_i) \in \delta$), appelons +$j_1<\ldots<j_m$ les indices tels que $t_j \in\Sigma$, autrement dit, +tels que la transition $q_{j-1} \to q_j$ ne soit pas spontanée, et +posons $j_0 = 0$. Alors on passe de $q_{j_{i-1}}$ à $q_{j_i}$ par une +succession de ε-transitions (de $q_{j_{i-1}}$ à $q_{(j_i)-1}$) suivie +par une unique transition non spontanée : on a $q_{(j_i)-1} \in +C(q_{j_{i-1}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$, +autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta'$ ; et comme +le mot $w = t_1\cdots t_n$ s'écrit aussi $t_{j_1}\cdots t_{j_m}$, on a +un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F'$ (puisque +$q_n \in C(q_{j_m}) \cap F$). Le mot $w$ supposé accepté par $A$ est +donc accepté par $A'$. La réciproque est analogue. +\end{proof} + +\thingy On dit que le NFA $A'$ est obtenu en \textbf{supprimant les + ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la +procédure décrite dans la démonstration de cette proposition. +Algorithmiquement, il s'agit donc, pour chaque état $q\in Q$ et chaque +$q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer une transition +$q\to q'$ étiquetée par $x$ dans $A'$ pour chaque transition +$q^\sharp\to q'$ étiquetée par $x$ dans $A$. + +\thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$ +présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on +fait partir de $0$ toutes les transitions partant d'un des états +$0,1,2$ et étiquetées par une lettre, et de même, comme $C(1) = +\{1,2\}$, on fait pratir de $1$ toutes les transitions partant d'un +des états $1,2$ et étiquetées par une lettre. On obtient finalement +l'automate suivant : + +\begin{center} +%%% begin example5ne %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,48bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$}; + \node (q2) at (176bp,18bp) [draw,circle,state,final] {$2$}; + \draw [->] (q0) ..controls (47.643bp,10.917bp) and (64.2bp,7.4655bp) .. (79bp,6bp) .. controls (94.922bp,4.4234bp) and (99.078bp,4.4234bp) .. (115bp,6bp) .. controls (125.98bp,7.0877bp) and (137.94bp,9.2693bp) .. node[auto] {$c$} (q2); + \draw [->] (q2) to[loop above] node[auto] {$c$} (q2); + \draw [->] (q0) to[loop above] node[auto] {$a$} (q0); + \draw [->] (q1) to[loop above] node[auto] {$b$} (q1); + \draw [->] (q1) ..controls (124.28bp,37.762bp) and (137.94bp,32.438bp) .. node[auto] {$c$} (q2); + \draw [->] (q0) ..controls (45.279bp,28.238bp) and (58.943bp,33.562bp) .. node[auto] {$b$} (q1); +% +\end{tikzpicture} + +%%% end example5ne %%% +\end{center} + +(Sur cet exemple précis, on obtient un automate déterministe +incomplet, mais ce n'est pas un phénomène général : en général il faut +s'attendre à obtenir un NFA.) + % % |