summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2020-01-21 22:03:46 +0100
committerDavid A. Madore <david+git@madore.org>2020-01-21 22:03:46 +0100
commitde1f73b88cdfcd6f4764f072866433a9dd96f7e0 (patch)
treebf75f49d97f0951ceb2d92f254a0147584328e6a
parentca644c1d85015e1c4bce66d42db4922edd8729b0 (diff)
downloadinf105-de1f73b88cdfcd6f4764f072866433a9dd96f7e0.tar.gz
inf105-de1f73b88cdfcd6f4764f072866433a9dd96f7e0.tar.bz2
inf105-de1f73b88cdfcd6f4764f072866433a9dd96f7e0.zip
More re-reading.
-rw-r--r--controle-20200123.tex10
1 files changed, 9 insertions, 1 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex
index 00792d7..889a969 100644
--- a/controle-20200123.tex
+++ b/controle-20200123.tex
@@ -420,7 +420,7 @@ $2$, $4$ et $7$.
(6) Expliquer rapidement pourquoi un automate fini déterministe
complet sans état inaccessible $\mathscr{A}$ sur $\Sigma = \{a\}$
prend nécessairement la forme suivante : si on note $j_2$ son nombre
-d'états, on peut numéroter ses états de $0$ à $j_2-1$, avec $0$ l'état
+d'états, on peut numéroter ces états de $0$ à $j_2-1$, avec $0$ l'état
initial, et de façon qu'il y ait une unique transition étiquetée $a$
de l'état $i$ vers l'état $i+1$ pour chaque $0\leq i<j_2-1$, ainsi
qu'une transition étiquetée $a$ de l'état $j_2-1$ vers l'état $j_1$
@@ -506,6 +506,14 @@ critère trouvé en (7) pour savoir si ce langage est fini et, le cas
exactement les $a^n$ pour les $n$ qui ne peuvent pas s'écrire sous la
forme $\ell_1 m_1 + \cdots + \ell_r m_r$ avec $m_1,\ldots,m_r \in
\mathbb{N}$.
+
+\emph{Remarque :} En fait, il s'avère que l'ensemble $\mathbb{N}
+\setminus \{\ell_1 m_1 + \cdots + \ell_r m_r : (m_1,\ldots,m_r)\in
+\mathbb{N}^r\}$ est fini si et seulement si le pgcd de
+$\ell_1,\ldots,\ell_r$ vaut $1$ (i.e., si et seulement si ces nombres
+sont premiers entre eux dans leur ensemble), ce qui est aussi testable
+algorithmiquement ; mais ce n'était pas demandé ici, et ceci ne résout
+pas la question d'énumérer explicitement l'ensemble.
\end{corrige}