diff options
Diffstat (limited to 'controle-20200123.tex')
| -rw-r--r-- | controle-20200123.tex | 19 |
1 files changed, 10 insertions, 9 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex index f87eb0e..d8a6774 100644 --- a/controle-20200123.tex +++ b/controle-20200123.tex @@ -189,19 +189,20 @@ de $\mathscr{A}_2$ plus facile à mener sans se tromper.) Pour simplifier les questions suivantes (ainsi que le travail du correcteur), on renommera si nécessaire les états de $\mathscr{A}_2$ de façon que, autant que possible, l'état résultant de la lecture du -mot $a^k$ par l'automate soit numéroté $k$. +mot $a^i$ par l'automate soit numéroté $i$. (3) Minimiser l'automate $\mathscr{A}_2$. On appellera $\mathscr{A}_3$ l'automate canonique ainsi obtenu. (On obtient un automate ayant $9$ états.) -(4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M -:= \Sigma^*\setminus L$ complémentaire de $L$. Ce langage $M$ est -fini : énumérer exhaustivement les mots qu'il contient. +(4) Construire un automate déterministe complet $\mathscr{A}_4$ +reconnaissant le langage $M := \Sigma^*\setminus L$ complémentaire +de $L$. Ce langage $M$ est fini : énumérer exhaustivement les mots +qu'il contient. -(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 +(5) En utilisant la question précédente, dire quels sont les (quatre) +entiers naturels ne pouvant pas s'écrire sous la forme $3m+5m'$ avec $m,m'\in\mathbb{N}$. \medbreak @@ -220,8 +221,8 @@ 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 ? +comme décrit à la question (6), à quelle condition (sur $j_1,j_2,F$) +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 @@ -259,7 +260,7 @@ $cacbcac$ et $cbcacbc$. fait, rationnel et donner une expression rationnelle qui le dénote. (On pourra commencer par décrire le langage $L' := L(G,T) := \{w \in \Sigma^* : T \mathrel{\Rightarrow^*_G} w\}$ des mots qui dérivent -de $T$ dans $G$.) +de $T$ selon $G$.) % |