diff options
Diffstat (limited to 'controle-20170330.tex')
| -rw-r--r-- | controle-20170330.tex | 18 |
1 files changed, 6 insertions, 12 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex index db38fc7..1764ad1 100644 --- a/controle-20170330.tex +++ b/controle-20170330.tex @@ -136,12 +136,8 @@ concaténation). On demande l'automate \emph{exact} donné par la construction de Thompson pour $r$ : aucune variation ne sera autorisée, même si elle -conduit à un automate équivalent. - -Par ailleurs, pour simplifier le travail du correcteur, on demande -d'étiqueter les états de $A_1$ par les entiers naturels à partir -de $0$ (soit $0,1,2,3,\ldots$) dans l'ordre correspondant à la lecture -de l'expression rationnelle de la gauche vers la droite. +conduit à un automate équivalent. Pour simplifier le travail du +correcteur, on numérotera $0$ l'état initial. (2) Éliminer les transitions spontanées de l'automate $A_1$ obtenu en (1), si nécessaire. (On supprimera les états devenus inutiles.) @@ -317,9 +313,7 @@ questions suivantes). (3) On \emph{admet}\footnote{Cela pourrait être démontré au moyen du lemme de pompage pour les langages algébriques, mais ce n'est pas demandé.} que le langage $M' := \{b^p a b^q a b^p a b^q : p,q>0\}$ -n'est pas algébrique. (Autrement dit, $M'$ est l'ensemble des mots de -la forme $b^p a b^q a b^p a b^q$ où $p$ et $q$ sont deux entiers -naturels non nuls.) En \emph{déduire} que le langage $L'$ n'est pas +n'est pas algébrique. En \emph{déduire} que le langage $L'$ n'est pas algébrique. Justifier soigneusement. Pour cette question et les suivantes, on pourra introduire le langage @@ -361,8 +355,8 @@ engendre le langage $L$ : en effet, les règles $S\rightarrow aSa$ et $S\rightarrow bSb$ permettent de placer des $a$ et $b$ symétriquement autour de $S$, c'est-à-dire de produire les $wSw^{\mathsf{R}}$ et donc $wAw^{\mathsf{R}}$, tandis que les règles $A\rightarrow\varepsilon$ et -$A\rightarrow aA$ reviennent à $A\rightarrow a{*}$ et permettent de -transformer $A$ en un nombre quelconque de $a$. +$A\rightarrow aA$ permettent de transformer $A$ en un nombre +quelconque de $a$. \smallbreak @@ -373,7 +367,7 @@ puisqu'un mot $b^p a b^q a b^p a b^q \in M'$ est évidemment dans $N$ et par ailleurs peut s'écrire $w a w$ où $w := b^p a b^q$. Mais réciproquement, on a $L'\cap N \subseteq M'$ : en effet, si pour certains $w \in \Sigma^*$ et $n \in \mathbb{N}$ le mot $w a^n w$ est -dans $N$, on a forcément $n\leq 1$ car il n'y a jamais plus qu'un $a$ +dans $N$, on a forcément $n\leq 1$ car il n'y a jamais plus d'un $a$ consécutif dans un mot de $N$, de là on en déduit que le nombre $|w|_a$ de $a$ dans $w$ vaut forcément exactement $1$ et que $n=1$ (seule possibilité pour avoir trois $a$ dans le mot au total), et |