From 05290959b2d8f39f403580a1454cc2bf9f55d076 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Wed, 30 Nov 2016 18:32:33 +0100
Subject: Clarifications.

---
 exercices1.tex | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

(limited to 'exercices1.tex')

diff --git a/exercices1.tex b/exercices1.tex
index 60fef33..b0595a7 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -226,7 +226,8 @@ 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$
+$p$ un nombre premier supérieur ou égal à $k$ (qui existe car
+l'ensemble des nombres premiers est infini) : 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
@@ -396,14 +397,15 @@ le NFA précédent et partant des états parmi $\{0,2,3,7\}$ sont $0\to
 0$, $0\to 5$, $3\to 7$ et $7\to 7$.  Tous les états contenant l'un des
 symboles $3,6,7$ sont finaux.)
 
-(2) On a affaire à un DFA dont tous les états sont accessibles, on
-peut donc appliquer directement l'algorithme de Moore.  Une première
-partition sépare les états finaux, soit $023, 0237, 027, 056, 0567,
-057$ des non-finaux, soit $0, 02, 05$.  L'étape suivante distingue
-$02$ parce que sa $a$-transition conduit à une classe différente que
-celles de $0$ et $05$, et $05$ parce que sa $b$-transition conduit à
-une classe différente de $0$ et $02$.  Les étapes suivantes ne
-changent rien.  Finalement, on arrive à un automate à quatre états :
+(2) On a affaire à un DFA (sous-entendu : \emph{complet}) dont tous
+les états sont accessibles, on peut donc appliquer directement
+l'algorithme de Moore.  Une première partition sépare les états
+finaux, soit $023, 0237, 027, 056, 0567, 057$ des non-finaux, soit $0,
+02, 05$.  L'étape suivante distingue $02$ parce que sa $a$-transition
+conduit à une classe différente que celles de $0$ et $05$, et $05$
+parce que sa $b$-transition conduit à une classe différente de $0$ et
+$02$.  Les étapes suivantes ne changent rien.  Finalement, on arrive à
+un automate à quatre états :
 \begin{center}
 %%% begin ex1p2d %%%
 
-- 
cgit v1.2.3

