diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 146 |
1 files changed, 118 insertions, 28 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 1efcf60..76e2189 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -181,15 +181,15 @@ des mots \emph{non vides} sur l'alphabet $\Sigma$ (par opposition à $\Sigma^*$ qui désigne l'ensemble de tous les mots, y compris le mot vide). -\thingy Les mots d'une seule lettre sont naturellement en -correspondance avec les lettres elles-mêmes : on identifiera souvent -tacitement, quoique un peu abusivement, une lettre $x\in\Sigma$ et le -mot de longueur $1$ formé de la seule lettre $x$. (En informatique, -cette identification entre \emph{caractères} et \emph{chaînes de - caractères de longueur $1$} est faite par certains langages de -programmation, mais pas par tous : \textit{caveat programmator}.) -Ceci permet d'écrire par exemple $\Sigma \subseteq \Sigma^*$ ou bien -$|x|=1 \liff x\in\Sigma$. +\thingy\label{convention-on-words-of-length-one} Les mots d'une seule +lettre sont naturellement en correspondance avec les lettres +elles-mêmes : on identifiera souvent tacitement, quoique un peu +abusivement, une lettre $x\in\Sigma$ et le mot de longueur $1$ formé +de la seule lettre $x$. (En informatique, cette identification entre +\emph{caractères} et \emph{chaînes de caractères de longueur $1$} est +faite par certains langages de programmation, mais pas par tous : +\textit{caveat programmator}.) Ceci permet d'écrire par exemple +$\Sigma \subseteq \Sigma^*$ ou bien $|x|=1 \liff x\in\Sigma$. \thingy\label{number-of-words-of-length-n} Si le cardinal de l'alphabet $\Sigma$ vaut $\#\Sigma = N$, alors, pour chaque $n$, le @@ -326,14 +326,14 @@ est souvent appelé « sous-chaîne [de caractères] ». Il ne faut cependant pas confondre ce concept avec celui de sous-mot défini ci-dessous. -\thingy Si $u_0,\ldots,u_r$ et $v_1,\ldots,v_r$ sont des mots sur un -même alphabet $\Sigma$, on dira que $v := v_1\cdots v_r$ est un -\textbf{sous-mot} du mot $w := u_0 v_1 u_1 v_2 \cdots u_{r-1} v_r -u_r$. En plus clair, cela signifie que $v$ est obtenu en ne gardant -que certaines lettres du mot $w$ (celles des $v_i$), dans le même -ordre, mais en en effaçant d'autres (celles des $u_i$) ; à la -différence du concept de facteur, celui de sous-mot n'exige pas que -les lettres gardées soient consécutives. +\thingy\label{definition-subword} Si $u_0,\ldots,u_r$ et +$v_1,\ldots,v_r$ sont des mots sur un même alphabet $\Sigma$, on dira +que $v := v_1\cdots v_r$ est un \textbf{sous-mot} du mot $w := u_0 v_1 +u_1 v_2 \cdots u_{r-1} v_r u_r$. En plus clair, cela signifie que $v$ +est obtenu en ne gardant que certaines lettres du mot $w$ (celles +des $v_i$), dans le même ordre, mais en en effaçant d'autres (celles +des $u_i$) ; à la différence du concept de facteur, celui de sous-mot +n'exige pas que les lettres gardées soient consécutives. À titre d'exemple, le mot $acb$ est un sous-mot du mot $abbcab$ (obtenu en gardant les lettres soulignées ici : @@ -713,17 +713,23 @@ alphabet $\Sigma$ est la donnée \textbf{fonction de transition}. \end{itemize} -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 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 part\footnote{Certains auteurs - préfèrent d'autres conventions, par exemple celle consistant à - entourer deux fois les états finaux.}. +\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 +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 +part\footnote{Certains auteurs préfèrent d'autres conventions, par + exemple celle consistant à entourer deux fois les états finaux.}. + +Lorsque plusieurs arêtes étiquetées par des symboles $x,y$ différents +relient les mêmes sommets $q,q'$ (i.e., lorsqu'on a à la fois +$\delta(q,x) = q'$ et $\delta(q,y) = q'$), on pourra écrire « $x,y$ » +ou « $x|y$ » sur l'arête en question (et ne la tracer qu'une seule +fois). Voir \ref{discussion-example2} ci-dessous pour un exemple. \thingy Pour donner un exemple simple, l'automate sur $\Sigma = \{a,b\}$ représenté ci-dessous a $Q = \{0,1\}$ et $q_0 = 0$ et $F = @@ -749,6 +755,90 @@ automate accepte les mots dont le nombre de $b$ est pair. %%% end example1 %%% \end{center} +\thingy Il faut comprendre le fonctionnement d'un DFA de la manière +suivante : initialement, l'automate est dans l'état initial $q_0$. On +va lui présenter un mot $w \in \Sigma^*$, lettre par lettre, de la +gauche vers la droite : i.e., si $w = x_1\cdots x_n$ on va faire +consommer à l'automate les lettres $x_1,x_2,\ldots,x_n$ dans cet +ordre. Le fait de consommer une lettre $x$ fait passer l'automate de +l'état $q$ à l'état $\delta(q,x)$ (autrement dit, l'automate passe +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)$). 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$. + +Graphiquement, on peut présenter la procédure de la manière suivante : +on part de l'état $q_0$ (sommet du graphe représentant l'automate) +indiqué par la flèche entrante (pointant de nulle part), et pour +chaque lettre du mot $w = x_1\cdots x_n$ considéré, on suit l'arête +portant ce symbole (et partant de l'état où on se trouve +actuellement). Si à la fin l'état $q_n$ est acceptant (représenté par +une flèche pointant vers nulle part), le mot $w$ est accepté, sinon il +est rejeté. + +\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFA sur +l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon +Q\times\Sigma^* \to Q$ par $\delta^*(q,x_1\cdots x_n) = +\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ ou, ce qui revient +au même (par récurrence sur la longueur du second argument) : +\begin{itemize} +\item $\delta^*(q,\varepsilon) = q$ quel que soit $q\in Q$ (où + $\varepsilon$ désigne le mot vide), +\item $\delta^*(q,wx) = \delta(\delta^*(q,w),x)$ quels que soient + $q\in Q$, $w\in\Sigma^*$ et $x\in\Sigma$, +\end{itemize} +(en particulier, $\delta^*(q,x) = \delta(q,x)$ si $x\in\Sigma$, donc +avec la convention faite en \ref{convention-on-words-of-length-one}, +on peut dire que $\delta^*$ prolonge $\delta$). + +Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ +\textbf{accepte} un mot $w$ lorsque $\delta^*(q_0,w) =: q_n \in F$ ; +dans le cas contraire, on dira qu'il \textbf{rejette} le mot $w$. + +L'ensemble $L_A$ des mots acceptés par l'automate $A$ s'appelle +\textbf{langage accepté}, ou \textbf{reconnu}, ou \textbf{défini}, par +l'automate $A$. + +\textbf Un langage $L \subseteq \Sigma^*$ qui peut s'écrire sous la +forme du langage $L_A$ accepté par un DFA $A$ s'appelle +\textbf{reconnaissable} (sous-entendu : par automate déterministe +fini). + +\thingy\label{discussion-example2} L'automate fini ci-dessous sur +$\Sigma := \{a,b,c\}$ a trois états, $Q = \{0,1,2\}$. On peut en +faire la description informelle suivante : l'automate commence dans +l'état $0$, où il reste jusqu'à rencontrer un $a$ qui le fait passer +dans l'état $1$, où il reste ensuite jusqu'à rencontrer un $b$ qui le +fait passer dans l'état $2$, où il reste définitivement et qui +constitue un état acceptant. + +\begin{center} +%%% begin example2 %%% + +\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] {$a$} (q1); + \draw [->] (q1) ..controls (89.406bp,44.625bp) and (91.75bp,54bp) .. (98bp,54bp) .. controls (102bp,54bp) and (104.4bp,50.152bp) .. node[auto] {$a,c$} (q1); + \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$b$} (q2); + \draw [->] (q0) ..controls (9.4062bp,44.625bp) and (11.75bp,54bp) .. (18bp,54bp) .. controls (22.004bp,54bp) and (24.405bp,50.152bp) .. node[auto] {$b,c$} (q0); + \draw [->] (q2) ..controls (169.41bp,44.625bp) and (171.75bp,54bp) .. (178bp,54bp) .. controls (182bp,54bp) and (184.4bp,50.152bp) .. node[auto] {$a,b,c$} (q2); +% +\end{tikzpicture} + +%%% end example2 %%% +\end{center} + +Cette description rend claire le fait que l'automate en question +accepte exactement les mots contenant un $a$ suivi, pas forcément +immédiatement, d'un $b$ ; autrement dit, les mots dont $ab$ est un +sous-mot (cf. \ref{definition-subword}). Ce langage est donc +reconnaissable. + % % |