1 files changed, 284 insertions, 0 deletions
diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
index 0af2a58..6aeb653 100644
--- a/controle-2020qcm.tex
+++ b/controle-2020qcm.tex
@@ -337,6 +337,9 @@ fini
 \answer
 semi-décidable mais non décidable
 
+\answer
+non semi-décidable
+
 \end{question}
 
 
@@ -365,6 +368,40 @@ fini
 \answer
 semi-décidable mais non décidable
 
+\answer
+non semi-décidable
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Soit $L := \{w \in \Sigma^* : |w|\geq 42\}$ l'ensemble des mots sur
+$\Sigma := \{a,b\}$ dont la longueur est supérieure ou égale à $42$.
+Ce langage $L$ est...
+
+\rightanswer
+rationnel mais infini
+
+\answer
+décidable mais non algébrique
+
+\answer
+algébrique mais non rationnel
+
+\answer
+fini
+
+\answer
+semi-décidable mais non décidable
+
+\answer
+non semi-décidable
+
 \end{question}
 
 
@@ -718,6 +755,65 @@ l'ensemble des mots dont la longueur est une puissance de $42$
 %
 %
 
+\begin{qvar}
+
+\begin{question}
+
+Lequel des langages suivants sur $\Sigma := \{a,b,c\}$ est rationnel ?
+
+\rightanswer
+l'ensemble des mots de longueur $\geq 6$ dont le suffixe de
+longueur $6$ coïncide avec le préfixe de longueur $6$ (c'est-à-dire
+que les six dernières lettres sont les mêmes que les six premières,
+dans le même ordre)
+
+\answer
+l'ensemble des mots qui sont des palindromes, c'est-à-dire
+$\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne
+le mot miroir de $w$)
+
+\answer
+l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 :
+w\in\Sigma^*\}$
+
+\answer
+l'ensemble des mots ayant le même nombre total de $a$ que de $b$ que
+de $c$
+
+\end{question}
+
+\begin{question}
+
+Lequel des langages suivants sur $\Sigma := \{a,b,c\}$ est rationnel ?
+
+\rightanswer
+l'ensemble des mots de longueur $\geq 6$ dont le suffixe de
+longueur $6$ est le miroir du préfixe de longueur $6$ (c'est-à-dire
+que les six dernières lettres sont les mêmes que les six premières,
+mais dans l'ordre inverse)
+
+\answer
+l'ensemble des mots qui sont des palindromes, c'est-à-dire
+$\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne
+le mot miroir de $w$)
+
+\answer
+l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 :
+w\in\Sigma^*\}$
+
+\answer
+l'ensemble des mots ayant le même nombre total de $a$ que de $b$ que
+de $c$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
 \begin{question}
 
 Quel langage reconnaît l'automate fini sur l'alphabet $\Sigma :=
@@ -855,6 +951,194 @@ rien du tout car ce n'est pas un automate fini valable
 \end{question}
 
 
+%
+%
+%
+
+\begin{question}
+
+Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire
+hors-contexte $S \rightarrow aSa\;|\;bSb\;|\;\varepsilon$ est...
+
+\rightanswer
+l'ensemble des mots qui sont des palindromes, c'est-à-dire
+$\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne
+le mot miroir de $w$)
+
+\answer
+l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 :
+w\in\Sigma^*\}$
+
+\answer
+l'ensemble des expressions bien-parenthésées si $a$ désigne une
+parenthèse ouvrante et $b$ une parenthèse fermante
+
+\answer
+l'ensemble des mots ayant le même nombre total de $a$ que de $b$
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire
+hors-contexte $S \rightarrow aSbS\;|\;\varepsilon$ est...
+
+\rightanswer
+l'ensemble des expressions bien-parenthésées si $a$ désigne une
+parenthèse ouvrante et $b$ une parenthèse fermante
+
+\answer
+l'ensemble des mots qui sont des palindromes, c'est-à-dire
+$\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne
+le mot miroir de $w$)
+
+\answer
+l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 :
+w\in\Sigma^*\}$
+
+\answer
+l'ensemble des mots ayant le même nombre total de $a$ que de $b$
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$
+
+\end{question}
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage sur $\Sigma = \{a,b\}$
+engendré par la grammaire hors-contexte $S \rightarrow
+aSbS\;|\;\varepsilon$ ?
+
+\rightanswer
+$abaaabbabb$
+
+\answer
+$abbaabbaab$
+
+\answer
+$aaabbabbba$
+
+\answer
+$aaaaabbbab$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{question}
+
+Le langage sur $\Sigma = \{a,b\}$ engendré par la grammaire
+hors-contexte dont les règles sont $S \rightarrow TT$ et $T
+\rightarrow aT\;|\;bT\;|\;\varepsilon$ est...
+
+\rightanswer
+l'ensemble $\Sigma^*$ de tous les mots sur $\Sigma$
+
+\answer
+l'ensemble des mots qui sont des palindromes, c'est-à-dire
+$\{w\in\Sigma^* : w = w^{\textsf{R}}\}$ (où $w^{\textsf{R}}$ désigne
+le mot miroir de $w$)
+
+\answer
+l'ensemble des mots qui sont des carrés, c'est-à-dire $\{w^2 :
+w\in\Sigma^*\}$
+
+\answer
+l'ensemble des expressions bien-parenthésées si $a$ désigne une
+parenthèse ouvrante et $b$ une parenthèse fermante
+
+\answer
+l'ensemble des mots ayant le même nombre total de $a$ que de $b$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Supposons fixé un modèle standard de calculabilité, par exemple la
+machine de Turing.  L'ensemble des couples $(e,n)$ formés d'un
+programme $e$ et d'un entier naturel $n$ et vérifiant la propriété
+« l'exécution du programme $e$ termine en exactement $n$ étapes »
+est-il :
+
+\rightanswer
+décidable
+
+\answer
+semi-décidable mais non décidable
+
+\answer
+non semi-décidable
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Supposons fixé un modèle standard de calculabilité, par exemple la
+machine de Turing.  L'ensemble des programmes $e$ dont l'exécution ne
+termine jamais est-il :
+
+\rightanswer
+non semi-décidable
+
+\answer
+décidable
+
+\answer
+semi-décidable mais non décidable
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Supposons fixé un modèle standard de calculabilité, par exemple la
+machine de Turing, et soit $\Sigma := \{a,b,c\}$.  L'ensemble des
+couples $(r,w)$ formés d'une expression rationnelle $r$ sur $\Sigma$
+et d'un mot $w$ sur $\Sigma$ vérifiant $r$ (c'est-à-dire appartenant
+au langage dénoté par $r$) est-il :
+
+\rightanswer
+décidable
+
+\answer
+semi-décidable mais non décidable
+
+\answer
+non semi-décidable
+
+\end{question}
+
+
 \end{qcm}
 %
 %