1 files changed, 78 insertions, 13 deletions
diff --git a/controle-20190328.tex b/controle-20190328.tex
index e3e1391..5632c1e 100644
--- a/controle-20190328.tex
+++ b/controle-20190328.tex
@@ -46,7 +46,7 @@
 %
 \newcommand{\spaceout}{\hskip1emplus2emminus.5em}
 \newif\ifcorrige
-\corrigetrue
+\corrigefalse
 \newenvironment{corrige}%
 {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
 \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
@@ -84,7 +84,10 @@
 
 \noindent\textbf{Consignes.}
 
-\textcolor{red}{À remplir}
+Les exercices sont indépendants.  Il est recommandé de les traiter
+dans l'ordre du sujet, mais ce n'est pas nécessaire ; cependant, on
+demande de faire apparaître de façon très visible dans les copies où
+commence chaque exercice.
 
 \medbreak
 
@@ -97,12 +100,12 @@ L'usage des appareils électroniques est interdit.
 
 Durée : 1h30
 
-Barème \emph{indicatif} : \textcolor{red}{xxx}.
+Barème \emph{indicatif} : 11+4+5.
 
 \ifcorrige
 Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse)
 \else
-Cet énoncé comporte \textcolor{red}{xxx} pages (page de garde incluse)
+Cet énoncé comporte 3 pages (page de garde incluse)
 \fi
 
 \vfill
@@ -120,7 +123,7 @@ Git: \input{vcline.tex}
 %
 %
 
-\exercice
+\exercice\label{exercise-on-finite-automata}
 
 Dans cet exercice, on pose $\Sigma = \{a,b\}$.
 
@@ -130,7 +133,7 @@ expression rationnelle $r_1$ dénotant le langage $L_1$.\quad(b) Donner
 l'automate fini déterministe complet minimal $\mathscr{A}_1$
 reconnaissant $L_1$ (on pourra préalablement passer par d'autres
 sortes d'automates comme étapes intermédiaires ; pour obtenir la
-totalité des points, on passera impérativement par des constructions
+totalité des points, on utilisera impérativement des constructions
 vues en cours, qu'on précisera).
 
 \emph{Information :} L'automate $\mathscr{A}_1$ correct a trois états.
@@ -154,7 +157,7 @@ Même conseil que ci-dessus.
 
 (3) Soit $L_3 = L_2^{\mathsf{R}} = \{w^{\mathsf{R}} : w \in L_2\}$ le
 langage miroir de $L_2$, c'est-à-dire le langage formé des mots
-miroirs des mots de $L_2$ (on rappelle que le mot « moir »
+miroirs des mots de $L_2$ (on rappelle que le mot « miroir »
 $w^{\mathsf{R}}$ d'un mot $w$ s'obtient en inversant l'ordre de ses
 lettres).\quad(a) Déduire de $\mathscr{A}_2$ un automate fini
 $\mathscr{A}_3$ reconnaissant $L_3$.\quad(b) Quel est le rapport entre
@@ -171,8 +174,8 @@ $\mathscr{A}_{4\mathrm{a}}$ ayant six états
 reconnaissant $L_4$.\quad(b) Donner l'automate fini déterministe
 complet minimal $\mathscr{A}_{4\mathrm{b}}$ reconnaissant $L_4$.
 
-\emph{Information :} L'automate $\mathscr{A}_4$ correct a quatre
-états.  Même conseil que pour la question (1).
+\emph{Information :} L'automate $\mathscr{A}_{4\mathrm{b}}$ correct a
+quatre états.  Même conseil que pour la question (1).
 
 \medskip
 
@@ -182,10 +185,72 @@ dénotant le langage $L_4$.
 
 \medskip
 
-(6) Sans raisonner sur les automates, proposer une expression
-rationnelle $r_6$ différente de celle trouvée en $r_5$ et qui dénote
-aussi le langage $L_4$ (dont on donnera au préalable une description
-en français).
+(6) Sans raisonner sur les automates, proposer directement une
+expression rationnelle $r_6$ différente de celle trouvée en $r_5$ et
+qui dénote aussi le langage $L_4$ (dont on donnera au préalable une
+description en français).
+
+
+%
+%
+%
+
+\exercice\label{exercise-two}
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.
+
+Soit $L$ le langage formé des mots de $\Sigma^*$ ayant à la fois
+$a$ comme première lettre et aussi comme dernière lettre
+(c'est-à-dire, les mots ayant $a$ comme préfixe et aussi $a$ comme
+suffixe).
+
+\smallskip
+
+(1) (a) Expliciter une grammaire hors contexte $G$
+engrendrant $L$.\quad(b) Cette grammaire $G$ est-elle déterministe ?
+(On justifiera la réponse.)
+
+\medskip
+
+(2) La langage $L$ est-il décidable ?  Est-il semi-décidable ?  On
+justifiera soigneusement la réponse.
+
+
+%
+%
+%
+
+\exercice\label{exercise-three}
+
+Dans cet exercice, on pose $\Sigma = \{a\}$.
+
+Soit $L = \{a, aa, aaaa, aaaaaaaa,\ldots\} = \{a^{2^k} :
+k\in\mathbb{N}\}$ le langage formé des mots de $\Sigma^*$ dont la
+longueur est une puissance de $2$.
+
+\smallskip
+
+(1) Le langage $L$ est-il rationnel ?  Si oui, on explicitera une
+expression rationnelle le dénotant ; si non, on démontrera ce fait.
+
+\medskip
+
+(2) Le langage $L$ est-il algébrique (autrement dit, existe-t-il une
+grammaire hors contexte $G$ engendrant $L$) ?  Si oui, on explicitera
+une grammaire hors contexte l'engendrant ; si non, on démontrera ce
+fait.
+
+\medskip
+
+(3) La langage $L$ est-il décidable ?  Est-il semi-décidable ?  Comme
+pour les questions précédentes, on justifiera soigneusement la
+réponse.
+
+\medskip
+
+\emph{Remarque :} Il est loisible de répondre aux questions de cet
+exercice dans un ordre différent par exemple pour éviter de répéter
+inutilement des raisonnements.
 
 %
 %