summaryrefslogtreecommitdiffstats
path: root/exercices1.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-11-29 15:57:19 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-11-29 15:57:19 (GMT)
commitda6ff34fb72f5dc7d3d1366d53efe81b31a811bc (patch)
tree996298d11a0dc0c2582376f6ab33aa05be8cf779 /exercices1.tex
parentde5663ac0f366f6d751599983a70b743ca549017 (diff)
downloadinf105-da6ff34fb72f5dc7d3d1366d53efe81b31a811bc.zip
inf105-da6ff34fb72f5dc7d3d1366d53efe81b31a811bc.tar.gz
inf105-da6ff34fb72f5dc7d3d1366d53efe81b31a811bc.tar.bz2
Another exercise on rational languages.
Diffstat (limited to 'exercices1.tex')
-rw-r--r--exercices1.tex25
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}