summaryrefslogtreecommitdiffstats
path: root/controle-20170330.tex
diff options
context:
space:
mode:
Diffstat (limited to 'controle-20170330.tex')
-rw-r--r--controle-20170330.tex8
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\}$