summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2020-06-04 00:58:32 +0200
committerDavid A. Madore <david+git@madore.org>2020-06-04 00:58:32 +0200
commit28b43e0af19e0867f48d9b65aee823499da05edd (patch)
tree4c4c37c6025b066c9cdce83737500a5435557792
parent95c305cfe98b74ff3ffa01f28e56229fa6c26c56 (diff)
downloadinf105-28b43e0af19e0867f48d9b65aee823499da05edd.tar.gz
inf105-28b43e0af19e0867f48d9b65aee823499da05edd.tar.bz2
inf105-28b43e0af19e0867f48d9b65aee823499da05edd.zip
Write a number of multiple-choice questions.
-rw-r--r--controle-2020qcm.tex291
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}