diff options
| -rw-r--r-- | controle-20200123.tex | 44 |
1 files changed, 39 insertions, 5 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex index e0c0c1f..b05f9d0 100644 --- a/controle-20200123.tex +++ b/controle-20200123.tex @@ -126,9 +126,14 @@ Git: \input{vcline.tex} Dans cet exercice, on pose $\Sigma = \{a\}$ (alphabet à une seule lettre). -On considère l'expression rationnelle $r$ suivante : $(aaa|aaaaa){*}$ -(sur l'alphabet $\Sigma$). On appelle $L := L(r)$ le langage qu'elle -dénote et $M := \Sigma^* \setminus L$ son complémentaire. +\medskip + +\textbf{Première partie : étude d'un cas particulier.} + +Dans cette partie, on considère l'expression rationnelle $r$ +suivante : $(aaa|aaaaa){*}$ (sur l'alphabet $\Sigma$). On appelle $L +:= L(r)$ le langage qu'elle dénote et $M := \Sigma^* \setminus L$ son +complémentaire. (1) Traiter l'une \emph{ou} l'autre des questions suivantes : (i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ; @@ -165,8 +170,37 @@ $\mathscr{A}_3$ l'automate canonique ainsi obtenu. := \Sigma^*\setminus L$ complémentaire de $L$. Ce langage $M$ est fini : énumérer exhaustivement les mots qu'il contient. -(5) Quels sont les entiers naturels ne pouvant pas s'écrire sous la -forme $3m+5n$ avec $m,n\in\mathbb{N}$ ? +(5) En utilisant la question précédente, dire quels sont les entiers +naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec +$m,m'\in\mathbb{N}$. + +\medbreak + +\textbf{Seconde partie : considérations générales.} + +(6) Expliquer rapidement pourquoi un automate déterministe complet +$\mathscr{A}$ sur $\Sigma$ 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 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$ pour un certain $0\leq j_1<j_2$. +Remarquer que l'automate $\mathscr{A}$ est alors complètement décrit +par les entiers $0\leq j_1<j_2$ et par le sous-ensemble $F$ de +$\{0,\ldots,j_2-1\}$ formé des états finaux. + +(7) Une fois un automate déterministe complet sur $\Sigma$ présenté +comme décrit à la question (6), à quelle condition le langage qu'il +reconnaît est-il fini ? + +(8) Déduire de l'ensemble de cet exercice que le problème suivant est +calculable algorithmiquement\footnote{Autrement dit, montrer qu'il + existe un algorithme qui, prenant en entrée $\ell_1,\ldots,\ell_r + \in \mathbb{N}$, répond au problème posé.} : donné des entiers +naturels $\ell_1,\ldots,\ell_r \in \mathbb{N}$, décider s'il y a un +nombre fini d'entiers naturels 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}$, et, le cas échéant, les énumérer. % % |