From 28b43e0af19e0867f48d9b65aee823499da05edd Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 4 Jun 2020 00:58:32 +0200 Subject: Write a number of multiple-choice questions. --- controle-2020qcm.tex | 291 ++++++++++++++++++++++++++++++++++++++++++++------- 1 file 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} -- cgit v1.2.3