diff options
| -rw-r--r-- | notes-inf105.tex | 65 |
1 files changed, 64 insertions, 1 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex index 6d60fe7..afcc0cd 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -941,7 +941,9 @@ au même (par récurrence sur la longueur du second argument) : \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$). +on peut dire que $\delta^*$ prolonge $\delta$ ; il sera par ailleurs +utile de remarquer que $\delta^*(q,ww') = +\delta^*(\delta^*(q,w),w')$). Cette fonction $\delta^*$ étant définie, on dira que l'automate $A$ \textbf{accepte} ou \textbf{reconnaît} un mot $w$ lorsque @@ -2224,6 +2226,67 @@ conduit à l'automate suivant : \noindent et finalement à l'expression rationnelle $(0|11|10(1|00){*}01){*}$, qui est équivalente à la précédente. +\begin{cor} +La classe des langages rationnels et celle des langages +reconnaissables coïncident. (On pourra donc considérer ces termes +comme synonymes.) +\end{cor} + + +\subsection{Le lemme de pompage} + +\begin{prop}[lemme de pompage pour les langages rationnels] +Soit $L$ un langage rationnel. Il existe alors un entier $k$ tel que +tout mot de $t \in L$ de longueur $|t| \geq k$ admette une +factorisation $t = uvw$ en trois facteurs $u,v,w$ où : +\begin{itemize} +\item[(i)] $|v| \geq 1$ (c'est-à-dire $v\neq\varepsilon$, +\item[(ii)] $|uv| \leq k$, +\item[(iii)] pour tout $i\geq 0$ on a $uv^iw \in L$. +\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 = +\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 +précis, soit $j_2$ le plus petit possible tel que les états +$q_0,\ldots,q_{j_2}$ ne soient pas tous distincts, autrement dit, le +premier état répété, et soit $j_1$ la précédente occurrence (forcément +unique) de cet état, c'est-à-dire l'indice tel que $j_1<j_2$ et +$q_{j_1} = q_{j_2}$. + +Posons $u = x_1\cdots x_{j_1}$ (le préfixe de $t$ de longueur $j_1$, +qui est le mot vide si $j_1 = 0$) et $v = x_{j_1+1}\cdots x_{j_2}$ (de +longueur $j_2 - j_1$), et enfin $w = x_{j_2+1}\cdots x_n$ (le suffixe +de $t$ de longueur $n-j_2$, avec la convention $w = \varepsilon$ si +$j_2 = n$). Ceci définit bien une factorisation $t = uvw$. + +On a bien (i) $|v| \geq 1$ puisque $j_2 > j_1$. On a par ailleurs +(ii) $|uv| \leq k$ puisque $|uv| = j_2$ et que les $j_2$ états +$q_0,\ldots,q_{j_2-1}$ sont distincts (c'est la minimalité de $j_2$) +de sorte que $j_2 \leq k$ (toujours par le principe des tiroirs). + +Montrons enfin (iii). On rappelle tout d'abord que +$\delta^*(q,x_1\cdots x_j) =\penalty0 \delta(\cdots\penalty500 +\delta(\delta(q,x_1),x_2)\cdots,x_j)$. Remarquons que +$\delta^*(q_0,u) = \delta^*(q_0,x_1\cdots x_{j_1}) = q_{j_1}$, et que +$\delta^*(q_{j_1},v) = \delta^*(q_{j_1},x_{j_1+1}\cdots x_{j_2}) = +q_{j_2} = q_{j_1}$. De cette dernière égalité, on tire +$\delta^*(q_{j_1},v^i) = q_{j_1}$ pour tout $i \geq 0$ (par récurrence +sur $i$). Enfin, $\delta^*(q_{j_1},w) = \delta^*(q_{j_2},w) = +\delta^*(q_{j_2}, x_{j_2+1}\cdots x_n) = q_n$ (qui est un état final). +En mettant ces faits ensemble, on a $\delta^*(q_0, uv^iw) = +\delta^*(q_{j_1}, v^iw) = \delta^*(q_{j_1}, w) = q_n$, et puisque +$q_n$ est final, ceci montre que le mot $uv^iw$ est accepté par $A$, +i.e., $uv^iw \in L$. +\end{proof} + % % |