diff options
Diffstat (limited to 'notes-inf105.tex')
| -rw-r--r-- | notes-inf105.tex | 233 |
1 files changed, 198 insertions, 35 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index a8572db..ded4af0 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={}] +\tikzstyle{automaton}=[>=stealth',initial text={},every loop/.style={min distance=7mm,looseness=5}] \tikzstyle{state}=[] \tikzstyle{final}=[accepting by arrow] % @@ -368,7 +368,7 @@ qu'on ne demande pas que $L$ soit fini (mais il peut l'être). nombre quelconque (éventuellement nul) de $c$ est un langage sur l'alphabet $\Sigma = \{a,b,c,d\}$. On verra plus loin que ce langage est « rationnel » (et pourra être désigné par l'expression rationnelle -$dc*$). +$dc{*}$). Voici quelques autres exemples de langages : \begin{itemize} @@ -597,7 +597,7 @@ introduit un nouvel objet, les \textbf{expressions rationnelles} (certains préfèrent le terme d'\textbf{expressions régulières}), qui sont des expressions servant à désigner un langage rationnel. Par exemple, plutôt que d'écrire « $\{d\}(\{c\}^*)$ », on parlera du -langage désigné par l'expression rationnelle $dc*$. +langage désigné par l'expression rationnelle $dc{*}$. Plus exactement, une expression rationnelle (sur un alphabet $\Sigma$) est un mot sur l'alphabet $\Sigma \cup \{\bot, @@ -626,14 +626,14 @@ l'expression $r$, de la manière suivante : alors $(r_1|r_2)$ est une expression rationnelle et son langage désigné est $L_{(r_1|r_2)} := L_1\cup L_2$, \item si $r$ est une expression rationnelle et $L = L_r$ les langage - désigné correspondant, alors $(r)*$ est une expression rationnelle - et son langage désigné est $L_{(r)*} := L^*$. + désigné correspondant, alors $(r){*}$ est une expression rationnelle + et son langage désigné est $L_{(r){*}} := L^*$. \end{itemize} À titre d'exemple, sur l'alphabet $\Sigma = \{a,b,c,d\}$, $c$ est une -expression rationnelle qui désigne le langage $\{c\}$, donc $(c)*$ en +expression rationnelle qui désigne le langage $\{c\}$, donc $(c){*}$ en est une qui désigne le langage $\{c\}^* = \{\varepsilon, c, cc, -ccc,\ldots\}$, et enfin $d(c)*$ en est une qui désigne le langage $\{d, +ccc,\ldots\}$, et enfin $d(c){*}$ en est une qui désigne le langage $\{d, dc, dcc, \ldots\}$ des mots formés d'un $d$ et d'une succession quelconques de $c$. Voici quelques autres exemples, toujours sur $\Sigma = \{a,b,c,d\}$ : @@ -642,11 +642,11 @@ $\Sigma = \{a,b,c,d\}$ : \{b\} = \{a,b\}$ formé des deux mots d'une seule lettre $a$ et $b$ ; \item l'expression rationnelle $(a|b)c$ désigne le langage $\{a,b\}\{c\} = \{ac,bc\}$, de même que $(ac|bc)$ ; -\item l'expression rationnelle $(bc)*$ désigne le langage $\{bc\}^* = +\item l'expression rationnelle $(bc){*}$ désigne le langage $\{bc\}^* = \{\varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; -\item l'expression rationnelle $(a|(bc)*)$ désigne le langage $\{a\} +\item l'expression rationnelle $(a|(bc){*})$ désigne le langage $\{a\} \cup \{bc\}^* = \{a, \varepsilon, bc, bcbc, bcbcbc, \ldots\}$ ; -\item l'expression rationnelle $(a|(bc)*)d$ désigne le langage $\{a, d, +\item l'expression rationnelle $(a|(bc){*})d$ désigne le langage $\{a, d, bcd, bcbcd, bcbcbcd, \ldots\}$. \end{itemize} @@ -655,16 +655,16 @@ pour lequel il existe une expression rationnelle qui le désigne. On dira qu'un mot $w$ \textbf{vérifie} une expression rationnelle $r$ lorsque ce mot appartient au langage qu'elle désigne (i.e., $w \in -L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c)*$. +L_r$). Par exemple, $dccc$ vérifie l'expression rationnelle $d(c){*}$. La convention de parenthésage introduite ci-dessus est inambiguë mais parfois inutilement lourde : on se permettra parfois de l'alléger, par exemple d'écrire $(r_1|r_2|r_3)$ pour $((r_1|r_2)|r_3)$ (ou pour $(r_1|(r_2|r_3))$, ce qui n'a guère d'importance vu qu'elles désignent -le même langage), ou encore $x*$ pour $(x)*$ lorsque $x$ est formé +le même langage), ou encore $x{*}$ pour $(x){*}$ lorsque $x$ est formé d'un seul caractère. La convention essentielle est que l'opération -d'étoile $*$ est la plus prioritaire ($ab*$ se lit comme $a(b)*$ et -non pas comme $(ab)*$), la concaténation vient après, et la barre de +d'étoile ${*}$ est la plus prioritaire ($ab{*}$ se lit comme $a(b){*}$ et +non pas comme $(ab){*}$), la concaténation vient après, et la barre de disjonction $|$ est la moins prioritaire ($ab|cd$ se lit comme $(ab|cd)$ et pas comme $a(b|c)d$). @@ -680,7 +680,7 @@ notée $+$ par les mathématiciens. Il y a ici un risque de confusion lié au fait que, en informatique, le symbole \texttt{+} est utilisé par de nombreux moteurs d'expressions régulières (par exemple, \texttt{egrep}) pour désigner l'opération évoquée en \ref{kleene-plus} -(de sorte que $r+$ a le même sens que $rr*$). +(de sorte que $r+$ a le même sens que $rr{*}$). \section{Automates finis} @@ -748,8 +748,8 @@ dont le nombre de $b$ est pair. \node (q0) at (18bp,20.306bp) [draw,circle,state,initial] {$0$}; \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp) .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp) .. node[auto] {$b$} (q0); \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp) .. node[auto] {$b$} (q1); - \draw [->] (q1) ..controls (89.406bp,46.931bp) and (91.75bp,56.306bp) .. (98bp,56.306bp) .. controls (102bp,56.306bp) and (104.4bp,52.458bp) .. node[auto] {$a$} (q1); - \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp) .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp) .. node[auto] {$a$} (q0); + \draw [->] (q1) to[loop above] node[auto] {$a$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$a$} (q0); % \end{tikzpicture} @@ -765,8 +765,10 @@ 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 +\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 +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$. @@ -779,9 +781,10 @@ 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) = +\thingy\label{definition-multiple-transition-function} 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} @@ -799,14 +802,13 @@ Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ $\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$. +\thingy\label{definition-recognizable-language} 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). +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). On dit que deux DFA $A,A'$ sont \textbf{équivalents} lorsqu'ils reconnaissent le même langage, i.e., $L_A = L_{A'}$. @@ -828,10 +830,10 @@ constitue un état acceptant. \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) to[loop above] 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); + \draw [->] (q0) to[loop above] node[auto] {$b,c$} (q0); + \draw [->] (q2) to[loop above] node[auto] {$a,b,c$} (q2); % \end{tikzpicture} @@ -842,7 +844,8 @@ 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. +reconnaissable. (Il est aussi rationnel puisque désigné par +l'expression rationnelle $(b|c){*}a(b|c){*}b(a|b|c){*}$.) \thingy Un état $q$ d'un DFA $A$ est dit \textbf{accessible} lorsqu'il existe un mot $w \in \Sigma^*$ tel que $q = \delta(q_0,w)$, autrement @@ -868,8 +871,8 @@ cet état soit final ou non. \node (q2) at (172bp,20.306bp) [draw,circle,state,final] {$2$}; \draw [->] (q1) ..controls (75.212bp,3.6347bp) and (64.284bp,-1.3057bp) .. (54bp,1.3057bp) .. controls (50.042bp,2.3107bp) and (46.047bp,3.8633bp) .. node[auto] {$b$} (q0); \draw [->] (q0) ..controls (46.106bp,20.306bp) and (58.578bp,20.306bp) .. node[auto] {$b$} (q1); - \draw [->] (q1) ..controls (90.319bp,47.164bp) and (92.445bp,56.306bp) .. (98bp,56.306bp) .. controls (101.47bp,56.306bp) and (103.6bp,52.735bp) .. node[auto] {$a$} (q1); - \draw [->] (q0) ..controls (9.4062bp,46.931bp) and (11.75bp,56.306bp) .. (18bp,56.306bp) .. controls (22.004bp,56.306bp) and (24.405bp,52.458bp) .. node[auto] {$a$} (q0); + \draw [->] (q1) to[loop above] node[auto] {$a$} (q1); + \draw [->] (q0) to[loop above] node[auto] {$a$} (q0); % \end{tikzpicture} @@ -889,6 +892,166 @@ automates déterministes finis incomplets et on va donc commencer par eux. +\subsection{Automates finis déterministes à spécification incomplète (=DFAI)} + +\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 +\begin{itemize} +\item d'un ensemble fini $Q$ d'états, +\item d'un état initial $q_0 \in Q$, +\item d'un ensemble $F \subseteq Q$ d'états finaux, +\item d'une fonction de transition \emph{partielle}\footnote{Une + « 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 + Q\times\Sigma \dasharrow Q$, +\end{itemize} +autrement dit, la seule différence avec la définition faite +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$. + +\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 +partant de $q$ et étiquetée par $x$. + +\thingy Le fonctionnement d'un DFAI est le même que celui d'un DFA, à +la modification suivante près : si on donne à consommer à l'automate +un symbole pour lequel la transition n'est pas définie, i.e., s'il +rencontre un $x$ pendant qu'il se trouve dans un état $q$ pour lequel +$\delta(q,x)$ n'est pas défini, alors l'automate cesse de +fonctionner : l'automate n'a plus d'état, n'effectue plus de +transition, et n'acceptera pas le mot quelles que soient les lettres +ultérieures. + +\thingy Formellement : si $A = (Q,q_0,F,\delta)$ est un DFAI sur +l'alphabet $\Sigma$, on définit une fonction $\delta^* \colon +Q\times\Sigma^* \dasharrow Q$ par $\delta^*(q,x_1\cdots x_n) = +\delta(\cdots\delta(\delta(q,x_1),x_2)\cdots,x_n)$ avec la convention +que dès qu'une sous-expression n'est pas définie, toute l'expression +n'est pas définie, 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)$ à condition que $q' + := \delta^*(q,w)$ soit défini et que $\delta(q',x)$ le soit (et si + ces deux conditions ne sont pas satisfaites, $\delta^*(q,wx)$ n'est + pas défini). +\end{itemize} + +Enfin, l'automate $A$ accepte un mot $w$ lorsque $\delta^*(q_0,w)$ +\emph{est défini} et appartient à $F$ ; dans le cas contraire (que ce +soit parce que $\delta^*(q_0,w)$ n'est pas défini ou parce qu'étant +défini il n'appartient pas à $F$), l'automate rejette le mot. + +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-example2b} Voici un exemple de DFAI sur +l'alphabet $\Sigma = \{a,b,c\}$. Cet automate reconnaît exactement +les mots formés d'un nombre quelconque de $c$, suivis d'un $a$, suivis +d'un nombre quelconque de $c$, suivis d'un $b$, suivis d'un nombre +quelconque de $c$. + +\begin{center} +%%% begin example2b %%% + +\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) to[loop above] node[auto] {$c$} (q1); + \draw [->] (q1) ..controls (126.11bp,18bp) and (138.58bp,18bp) .. node[auto] {$b$} (q2); + \draw [->] (q0) to[loop above] node[auto] {$c$} (q0); + \draw [->] (q2) to[loop above] node[auto] {$c$} (q2); +% +\end{tikzpicture} + +%%% end example2b %%% +\end{center} + +(Ce langage est aussi désigné par l'expression rationnelle +$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$. +\end{prop} +\begin{proof} +On définit $Q' = Q \cup \{q_\bot\}$ où $q_\bot$ est un nouvel état +(n'appartenant pas à $Q$), qu'on appellera « puits ». On garde l'état +initial $q'_0 = q_0$. On garde l'ensemble $F' = F$ d'états finaux, +c'est-à-dire notamment que le puits n'est pas acceptant. Enfin, on +définit $\delta'(q,x)$ pour $q\in Q'$ et $x\in\Sigma$ par +\[ +\begin{aligned} +\delta'(q,x) &= \delta(q,x)\text{ si $\delta(q,x)$ est défini}\\ +\delta'(q,x) &= q_\bot\text{ sinon}\\ +\end{aligned} +\] +(notamment, $\delta'(q_\bot,x) = q_\bot$ quel que soit $x$). + +Il est alors facile de voir que $A'$ a le même comportement que $A$ au +sens où $\delta^{\prime*}(q,w) = \delta^*(q,w)$ lorsque le terme de +droite est défini et $\delta^{\prime*}(q,w) = q_\bot$ sinon (le DFA +$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 À titre d'exemple, le DFA suivant représente la complétion du +DFAI représenté en \ref{discussion-example2b} : + +\begin{center} +%%% begin example2c %%% + +\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,182bp) -- (214bp,182bp) -- (214bp,0bp) -- cycle; +\end{scope} + \node (q1) at (102bp,131bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,85bp) [draw,circle,state,initial] {$0$}; + \node (q2) at (196bp,85bp) [draw,circle,state,final] {$2$}; + \node (qbot) at (102bp,22bp) [draw,circle,state] {$\bot$}; + \draw [->] (q1) to[loop above] node[auto] {$c$} (q1); + \draw [->] (q2) to[loop above] node[auto] {$c$} (q2); + \draw [->] (qbot) to[loop below] node[auto] {$a,b,c$} (qbot); + \draw [->] (q0) ..controls (44.565bp,65.359bp) and (61.506bp,52.343bp) .. node[auto] {$b$} (qbot); + \draw [->] (q0) to[loop above] node[auto] {$c$} (q0); + \draw [->] (q1) ..controls (102bp,96.993bp) and (102bp,73.356bp) .. node[auto] {$a$} (qbot); + \draw [->] (q0) ..controls (46.061bp,100.18bp) and (63.141bp,109.76bp) .. node[auto] {$a$} (q1); + \draw [->] (q2) ..controls (166.87bp,65.735bp) and (145.76bp,51.281bp) .. node[auto] {$a,b$} (qbot); + \draw [->] (q1) ..controls (132.83bp,116.08bp) and (154.08bp,105.46bp) .. node[auto] {$b$} (q2); +% +\end{tikzpicture} + +%%% end example2c %%% +\end{center} + + % % % |