diff options
Diffstat (limited to 'controle-20170330.tex')
| -rw-r--r-- | controle-20170330.tex | 8 |
1 files changed, 4 insertions, 4 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex index 1764ad1..5c53a7b 100644 --- a/controle-20170330.tex +++ b/controle-20170330.tex @@ -129,7 +129,7 @@ Cet énoncé comporte 3 pages (page de garde incluse) Soit $\Sigma = \{a,b\}$. (1) Représenter l'automate de Thompson $A_1$ associé à l'expression -rationnelle $r$ suivante : $a{*}(ba{*}){*}$ (pour éviter toute erreur +rationnelle $r$ suivante : $a^{*}(ba^{*})^{*}$ (pour éviter toute erreur de lecture, on rappelle que dans l'écriture des expressions rationnelles, l'étoile de Kleene $*$ a une priorité plus grande que la concaténation). @@ -153,7 +153,7 @@ l'automate déterminisé. (5) Donner une autre expression rationnelle équivalente à $r$. \begin{corrige} -(1) L'automate de Thompson de $r := a{*}(ba{*}){*}$ doit comporter +(1) L'automate de Thompson de $r := a^{*}(ba^{*})^{*}$ doit comporter $12$ états (numérotés de $0$ à $11$ selon la consigne) puisque cette expression rationnelle contient $6$ symboles parenthèses non comptées. Il est l'automate $A_1$ suivant (où on a omis les @@ -274,7 +274,7 @@ lui-même : (5) L'automate $A_4$ reconnaît manifestement le langage $\Sigma^*$ de tous les mots sur $\Sigma$. On peut donc proposer l'expression -rationnelle $(a|b){*}$ (nous notons ici $|$ pour la disjonction, qu'on +rationnelle $(a|b)^{*}$ (nous notons ici $|$ pour la disjonction, qu'on peut aussi noter $+$). \end{corrige} @@ -318,7 +318,7 @@ algébrique. Justifier soigneusement. Pour cette question et les suivantes, on pourra introduire le langage auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a b^{+} -a b^{+}$ où $b^{+}$ est une abréviation pour $bb{*}$ (dénotant au moins +a b^{+}$ où $b^{+}$ est une abréviation pour $bb^{*}$ (dénotant au moins une répétition de $b$). (4a) Montrer que le langage $M := \{b^p a b^q a b^q a b^p : p,q>0\}$ |