diff options
| -rw-r--r-- | exercices1.tex | 25 |
1 files changed, 25 insertions, 0 deletions
diff --git a/exercices1.tex b/exercices1.tex index 26533e8..1eb8b74 100644 --- a/exercices1.tex +++ b/exercices1.tex @@ -214,4 +214,29 @@ par l'expression rationnelle $10{*}$. % % % + +\exercice + +Soit $\Sigma = \{a\}$. Montrer que le langage $L = \{a^2, a^3, a^5, +a^7, a^{11}, a^{13}\ldots\}$ constitué des mots ayant un nombre +\emph{premier} de $a$, n'est pas rationnel. + +\begin{corrige} +Supposons par l'absurde que $L$ soit rationnel. D'après le lemme de +pompage, il existe un certain $k$ tel que tout mot de $L$ de longueur +$\geq k$ se factorise sous la forme $uvw$ avec (i) $|v|\geq 1$, +(ii) $|uv|\leq k$ et (iii) $uv^iw \in L$ pour tout $i\geq 0$. Soit +$p$ un nombre premier supérieur ou égal à $k$ : le mot $a^p \in L$ +admet une factorisation comme on vient de dire. Posons $|u| =: m$ et +$|v| =: n$, si bien que $|w| = p-m-n$. On a alors $n\geq 1$ +d'après (i), et $|uv^iw| = m + in + (p-m-n) = p+(i-1)n$ est premier +pour tout $i\geq 0$ d'après (iii). En particulier pour $i=p+1$ on +voit que $p + pn = p(n+1)$ est premier, ce qui contredit le fait qu'il +s'agit d'un multiple non-trivial ($n+1\geq 2$) de $p$. +\end{corrige} + + +% +% +% \end{document} |