diff options
| -rw-r--r-- | controle-20200123.tex | 10 |
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} |