diff options
| -rw-r--r-- | controle-20190328.tex | 91 |
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. % % |