diff options
| -rw-r--r-- | figs/example4det.dot | 8 | ||||
| -rw-r--r-- | figs/example5.dot | 13 | ||||
| -rw-r--r-- | notes-inf105.tex | 139 |
3 files changed, 144 insertions, 16 deletions
diff --git a/figs/example4det.dot b/figs/example4det.dot index 2d88a37..7121690 100644 --- a/figs/example4det.dot +++ b/figs/example4det.dot @@ -1,10 +1,10 @@ digraph example4det { rankdir="LR"; node [texmode="math",shape="circle",style="state"]; - q0 [style="state,initial",label="\{0\}"]; - q01 [style="state",label="\{0,1\}"]; - q02 [style="state,final",label="\{0,2\}"]; - q012 [style="state,final",label="\{0,1,2\}"]; + q0 [style="state,initial",label="0",texlbl="$\{0\}$"]; + q01 [style="state",label="01",texlbl="$\{0,1\}$"]; + q02 [style="state,final",label="02",texlbl="$\{0,2\}$"]; + q012 [style="state,final",label="012",texlbl="$\{0,1,2\}$"]; edge [texmode="math",lblstyle="auto"]; q0 -> q0 [label="b",topath="loop above"]; q0 -> q01 [label="a"]; diff --git a/figs/example5.dot b/figs/example5.dot new file mode 100644 index 0000000..7c5e403 --- /dev/null +++ b/figs/example5.dot @@ -0,0 +1,13 @@ +digraph example5 { + 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="e",texlbl="$\varepsilon$"]; + q1 -> q1 [label="b",topath="loop above"]; + q1 -> q2 [label="e",texlbl="$\varepsilon$"]; + q2 -> q2 [label="c",topath="loop above"]; +} diff --git a/notes-inf105.tex b/notes-inf105.tex index f46a27a..ae1f0e1 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -37,6 +37,7 @@ \newcommand{\liff}{\mathrel{\Longleftrightarrow}\relax} % \DeclareUnicodeCharacter{00A0}{~} +\DeclareUnicodeCharacter{03B5}{$\varepsilon$} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} @@ -1136,8 +1137,9 @@ $(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$. +\item $(q,wx,q') \in \delta^*$ si et seulement si il existe $q^\sharp$ + tel que $(q,w,q^\sharp) \in \delta^*$ et $(q^\sharp,x,q') \in + \delta$. \end{itemize} Enfin, l'automate $A$ accepte un mot $w$ lorsqu'il existe $q_0\in I$ @@ -1285,19 +1287,19 @@ procédant ainsi, on constuit l'automate à $4$ états qui suit : \pgfsetstrokecolor{strokecol} \definecolor{fillcol}{rgb}{1.0,1.0,1.0}; \pgfsetfillcolor{fillcol} - \filldraw (0bp,0bp) -- (0bp,204bp) -- (274bp,204bp) -- (274bp,0bp) -- cycle; + \filldraw (0bp,0bp) -- (0bp,155bp) -- (212bp,155bp) -- (212bp,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); + \node (q02) at (188bp,19bp) [draw,circle,state,final] {$\{0,2\}$}; + \node (q0) at (18bp,40bp) [draw,circle,state,initial] {$\{0\}$}; + \node (q01) at (100bp,71bp) [draw,circle,state] {$\{0,1\}$}; + \node (q012) at (188bp,98bp) [draw,circle,state,final] {$\{0,1,2\}$}; + \draw [->] (q01) ..controls (129.79bp,53.593bp) and (147.53bp,42.867bp) .. node[auto] {$b$} (q02); + \draw [->] (q0) ..controls (45.781bp,50.378bp) and (59.874bp,55.839bp) .. 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 [->] (q01) ..controls (129.27bp,79.877bp) and (142.8bp,84.122bp) .. 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); + \draw [->] (q02) ..controls (146.97bp,21.169bp) and (110.83bp,23.684bp) .. (80bp,28bp) .. controls (68.696bp,29.582bp) and (56.322bp,31.905bp) .. node[auto] {$a,b$} (q0); + \draw [->] (q012) ..controls (188bp,65.926bp) and (188bp,56.965bp) .. node[auto] {$b$} (q02); % \end{tikzpicture} @@ -1317,6 +1319,119 @@ $\{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$ ». + +\subsection{Automates finis non-déterministes à transitions spontanées (=εNFA)} + +\thingy Un \textbf{automate fini non-déterministe à transitions + spontanées} ou \textbf{...à $\varepsilon$-transitions}, 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 relation de transition $\delta \subseteq Q \times + (\Sigma\cup\{\varepsilon\}) \times Q$. +\end{itemize} +Autrement dit, on autorise maintenant des transitions étiquetées par +le mot vide $\varepsilon$ plutôt que par une lettre $x \in\Sigma$ : +ces transitions sont dites spontanées, ou $\varepsilon$-transitions. + +Soulignons qu'on ne définit les $\varepsilon$-transitions \emph{que} +pour les automates non-déterministes : ou, pour dire les choses +autrement, \emph{un automate qui possède des $\varepsilon$-transitions + est par nature même non-déterministe}. + +La représentation graphique des εNFA est évidente (on utilisera le +symbole « $\varepsilon$ » pour étiqueter les transitions spontanées). + +\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 +étiquetées par les lettres de $w$ ou bien des $\varepsilon$ insérés à +n'importe quel endroit et en n'importe quel nombre. Autrement dit, +$w$ est accepté lorsqu'\emph{il existe} $q_0,\ldots,q_n \in Q$ et +$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$ tels que $q_0 \in I$ +et $q_n\in F$ et $(q_{i-1},t_i,q_i) \in \delta$ pour chaque $1\leq +i\leq n$ et $w = t_1\cdots t_n$ (\emph{attention} : dans cette +écriture, $t_1,\ldots,t_n$ ne sont pas forcément les lettres de $w$, +certains des $t_i$ peuvent être le symbole $\varepsilon$, les lettres +de $w$ sont obtenues en ignorant ces symboles). + +De façon plus intuitive, cela signifie que l'automate a la possibilité +de passer spontanément, c'est-à-dire sans consommer de lettre, d'un +état $q$ à un état $q'$, lorsque ces états sont reliés par une +ε-transition. + +\thingy Voici une formalisation possible : 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^*$ +lorsqu'il existe $q_0,\ldots,q_n \in Q$ et $t_1,\ldots,t_n \in +(\Sigma\cup\{\varepsilon\})$ tels que $q_0 = q$ et $q_n = q'$ et +$(q_{i-1},t_i,q_i) \in\delta$ pour chaque $1\leq i\leq n$, et enfin $w += t_1\cdots t_n$. + +Si on préfère, on peut définir par récurrence sur $n \geq 0$ une +relation $\delta^{(n)} \subseteq Q \times \Sigma^* \times Q$ de la +manière suivante : +\begin{itemize} +\item $(q,w,q') \in \delta^{(0)}$ si et seulement si $q'=q$ et + $v=\varepsilon$, +\item $\delta^{(1)} = \delta \subseteq Q \times + (\Sigma\cup\{\varepsilon\})$ (faisant partie de la donnée de $A$), +\item $(q,v,q') \in \delta^{(n+1)}$ si et seulement si il existe + $q^\sharp \in Q$ et $t \in \Sigma\cup\{\varepsilon\}$ tels que + $(q,w,q^\sharp) \in \delta^{(n)}$ et $(q^\sharp,t,q') \in \delta$ et + $v = wt$ (ce qui signifie que : soit $t=\varepsilon$ et $v=w$, soit + $t\in\Sigma$ est la dernière lettre de $w$ et $v$ est le préfixe + correspondant) ; +\end{itemize} +et on définit $\delta^* = \bigcup_{n=1}^{+\infty} \delta^{(n)}$, +autrement dit $(q,w,q') \in \delta^*$ lorsqu'il existe $n$ tel que +$(q,w,q') \in \delta^{(n)}$. + +Concrètement, $(q,w,q') \in \delta^{(n)}$ signifie que le εNFA peut +passer de l'état $q$ à l'état $q'$ en effectuant (exactement) $n$ +transitions ($q_0\to q_1 \to \cdots \to q_n$ étiquetées par +$t_1,\ldots,t_n \in (\Sigma\cup\{\varepsilon\})$) et en consommant le +mot $w$ (soit $w = t_1\cdots t_n$) ; et $(q,w,q') \in \delta^*$ +signifie la même chose mais sans contrainte sur le nombre de +transitions. La différence avec les NFA est que le nombre $n$ de +transitions n'est plus forcément égal à la longueur de $w$. + +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 Voici un exemple de εNFA particulièrement simple sur $\Sigma = +\{a,b,c\}$: + +\begin{center} +%%% begin example5 %%% + +\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 (178bp,18bp) [draw,circle,state,final] {$2$}; + \draw [->] (q0) ..controls (46.106bp,18bp) and (58.578bp,18bp) .. node[auto] {$\varepsilon$} (q1); + \draw [->] (q1) to[loop above] node[auto] {$b$} (q1); + \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$\varepsilon$} (q2); + \draw [->] (q0) to[loop above] node[auto] {$a$} (q0); + \draw [->] (q2) to[loop above] node[auto] {$c$} (q2); +% +\end{tikzpicture} + +%%% end example5 %%% +\end{center} + +En considérant les différents chemins possibles entre $0$ et $2$ sur +ce graphe, on comprend que le langage qu'il reconnaît est celui des +mots sur $\{a,b,c\}$ formés d'un nombre quelconque de $a$ suivi d'un +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{*}$. + % % % |