Write a number of multiple-choice questions.

1 files changed, 256 insertions, 35 deletions

diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
index 8d80361..85773b0 100644
--- a/controle-2020qcm.tex
+++ b/controle-2020qcm.tex
@@ -39,7 +39,7 @@
 \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
 %
 \newif\ifcorrige
-\corrigefalse
+\corrigetrue
 %
 %
 % NOTE: compile dot files with
@@ -108,31 +108,37 @@ Git: \input{vcline.tex}
 
 \begin{question}
 
-Quelle est la couleur du cheval blanc d'Henri IV ?
+Lequel des mots suivants est un sous-mot de $abcabcabc$ ?
 
 \rightanswer
-Blanc
+$acbac$
 
 \answer
-Noir
+$abacbab$
 
 \answer
-Bleu à pois roses
+$aabbcc$
+
+\answer
+$acbba$
 
 \end{question}
 
 \begin{question}
 
-Quelle est la couleur du cheval noir de Charlemagne ?
+Lequel des mots suivants est un sous-mot de $abcabcbca$ ?
 
 \rightanswer
-Noir
+$acbba$
 
 \answer
-Blanc
+$abacbab$
 
 \answer
-Bleu à pois roses
+$aabbcc$
+
+\answer
+$acbac$
 
 \end{question}
 
@@ -143,21 +149,48 @@ Bleu à pois roses
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
+sous-mots de $w$ est...
+
+\rightanswer
+fini et rationnel
+
+\answer
+fini mais pas rationnel
+
+\answer
+rationnel mais pas fini
+
+\answer
+ni fini ni rationnel
+
+\end{question}
+
 \begin{question}
 
-Qui est enterré dans le tombeau de Grant ?
+Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
+mots dont $w$ est un sous-mot est...
 
 \rightanswer
-Grant
+rationnel mais pas fini
 
 \answer
-Charlemagne
+fini et rationnel
 
 \answer
-Obi-Wan Kenobi
+fini mais pas rationnel
+
+\answer
+ni fini ni rationnel
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
@@ -165,16 +198,20 @@ Obi-Wan Kenobi
 
 \begin{question}
 
-Combien fait $2+2$ ?
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $(ab|ba){*}$ ?
 
 \rightanswer
-$4$
+$abbaab$
+
+\answer
+$abaabb$
 
 \answer
-$696\,729\,600$
+$aaabbb$
 
 \answer
-$e^{\pi\sqrt{163}}$
+$abbabba$
 
 \end{question}
 
@@ -183,69 +220,198 @@ $e^{\pi\sqrt{163}}$
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Laquelle des expresssions rationnelles suivantes est équivalente
+à $a{*}(bba{*}){*}$ ?
+
+\rightanswer
+$(a|bb){*}$
+
+\answer
+$a{*}(bb){*}a{*}$
+
+\answer
+$a{*}bba{*}$
+
+\answer
+$(abba){*}$
+
+\end{question}
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $a{*}(bba{*}){*}$ ?
+
+\rightanswer
+$abbabba$
+
+\answer
+$aaabbb$
+
+\answer
+$abbaab$
+
+\answer
+$abaabb$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Le langage engendré par la grammaire hors-contexte $S \rightarrow
+abS\;|\;baS\;|\;\varepsilon$ est...
+
+\rightanswer
+rationnel et algébrique
+
+\answer
+rationnel mais pas algébrique
+
+\answer
+algébrique mais pas rationnel
+
+\answer
+ni algébrique ni rationnel
+
+\end{question}
+
 \begin{question}
 
-David Madore est-il... ?
+Le langage engendré par la grammaire hors-contexte $S \rightarrow
+abS\;|\;Sba\;|\;\varepsilon$ est...
 
 \rightanswer
-l'auteur de ces questions
+algébrique mais pas rationnel
 
 \answer
-un arbre
+rationnel et algébrique
 
 \answer
-une application Android
+rationnel mais pas algébrique
 
 \answer
-le fils caché de la reine d'Angleterre
+ni algébrique ni rationnel
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Soit $L := \{a^{2^i} : i\in\mathbb{N}\}$ l'ensemble des mots sur
+$\Sigma := \{a\}$ dont la longueur est une puissance de $2$.  Ce
+langage $L$ est...
+
+\rightanswer
+décidable mais non algébrique
+
+\answer
+algébrique mais non rationnel
+
+\answer
+rationnel mais infini
+
+\answer
+fini
+
+\answer
+semi-décidable mais non décidable
+
+\end{question}
+
 \begin{question}
 
-Complétez les vers : « Ô rage ! ô désespoir ! ô vieillesse ennemie ! /
-N'ai-je donc tant vécu que pour cette... ? »
+Soit $L := \{a^{12i} : i\in\mathbb{N}\}$ l'ensemble des mots sur
+$\Sigma := \{a\}$ dont la longueur est multiple de $12$.  Ce
+langage $L$ est...
 
 \rightanswer
-infamie
+rationnel mais infini
+
+\answer
+décidable mais non algébrique
 
 \answer
-alchimie
+algébrique mais non rationnel
 
 \answer
-momie
+fini
 
+\answer
+semi-décidable mais non décidable
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
 %
 
+\begin{qvar}
+
 \begin{question}
 
-La réponse correcte à cette question est-elle... ?
+Un alphabet $\Sigma$ étant fixé, si $r$ est une expression rationnelle
+sur $\Sigma$, existe-t-il toujours une expression rationnelle $r'$ qui
+dénote le langage formé des mots qui \emph{ne vérifient pas} $r$ ?
 
 \rightanswer
-celle-ci
+oui, et on dispose d'un algorithme permettant de calculer $r'$ en
+fonction de $r$
 
 \answer
-une autre que celle-ci
+oui, mais on ne dispose pas d'algorithme permettant de calculer $r'$
+en fonction de $r$
 
 \answer
-inexistante
+non, ce langage n'est pas forcément rationnel
+
+\end{question}
+
+\begin{question}
+
+Un alphabet $\Sigma$ étant fixé, si $r_1$ et $r_2$ sont deux
+expressions rationnelles sur $\Sigma$, existe-t-il toujours une
+expression rationnelle $r'$ qui dénote le langage formé des mots qui
+vérifient \emph{à la fois} $r_1$ \emph{et} $r_2$ ?
+
+\rightanswer
+oui, et on dispose d'un algorithme permettant de calculer $r'$ en
+fonction de $r_1$ et $r_2$
+
+\answer
+oui, mais on ne dispose pas d'algorithme permettant de calculer $r'$
+en fonction de $r_1$ et $r_2$
 
 \answer
-toutes à la fois
+non, ce langage n'est pas forcément rationnel
 
 \end{question}
 
+\end{qvar}
+
 
 %
 %
@@ -253,13 +419,68 @@ toutes à la fois
 
 \begin{question}
 
-Un quart d'heure avant sa mort, il était encore... ?
+L'automate fini sur l'alphabet $\Sigma := \{a,b\}$ représenté
+ci-dessous
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q1) to node[auto] {$\varepsilon$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\noindent est-il...
 
 \rightanswer
-en vie
+un automate fini non-déterministe à transitions spontanées
+
+\answer
+un automate fini déterministe incomplet à transitions spontanées
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+L'élimination des transitions spontanées sur l'automate fini sur
+l'alphabet $\Sigma := \{a,b\}$ représenté ci-dessous
+
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2) at (70bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (140bp,0bp) [draw,circle,state,final] {$3$};
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q1) to node[auto] {$\varepsilon$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\noindent s'obtient-elle...
+
+\rightanswer
+en supprimant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
+et en ajoutant une transition étiquetée $b$ reliant $1$ à $3$
+
+\answer
+en supprimant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
+et en ajoutant une transition étiquetée $a$ reliant $1$ à $3$
+
+\answer
+en remplaçant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
+par une transition étiquetée $b$ (toujours reliant $1$ à $2$)
 
 \answer
-mort
+en remplaçant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
+par une transition étiquetée $a$ (toujours reliant $1$ à $2$)
 
 \end{question}