1 files changed, 1292 insertions, 0 deletions
diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
new file mode 100644
index 0000000..275e174
--- /dev/null
+++ b/controle-2020qcm.tex
@@ -0,0 +1,1292 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\newenvironment{qcm}{\relax}{\relax}
+\newenvironment{qvar}{\relax}{\relax}
+\newcounter{quescnt}
+\newenvironment{question}%
+{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
+{\relax}
+\newcounter{answcnt}[quescnt]
+\newcommand\answer{%
+\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
+\let\rightanswer=\answer
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+\newif\ifcorrige
+\corrigefalse
+\def\seedval{test}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{12 juin 2020}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Ce contrôle de connaissances est un QCM (questionnaire à choix
+multiples).  Chaque question admet une unique réponse correcte.  Les
+questions sont totalement indépendantes les unes des autres.  La
+sélection des questions et l'ordre ont été tirés aléatoirement et
+n'obéissent donc à aucune logique particulière.
+
+La réponse est attendue sous forme d'une liste de numéros de question
+suivie de la réponse proposée : par exemple, « \verb=1A 2B 4D= » pour
+signifier que la réponse proposée à la question 1 est (A), la réponse
+proposée à la question 2 est (B), et la réponse proposée à la
+question 4 est (D).
+
+Une réponse incorrecte sera (deux fois) plus fortement pénalisée
+qu'une absence de réponse : il est donc préférable de ne pas répondre
+à une question que de répondre aléatoirement.
+
+\medbreak
+
+Durée : 1h de 15h30 à 16h30 (sauf 1h20 pour les tiers-temps, de 15h30
+à 16h50)
+
+\vfill
+
+\noindent
+Sujet généré pour : \texttt{\seedval}
+
+\medskip
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+\begin{qcm}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Lequel des mots suivants est un sous-mot de $abcabcabc$ ?
+
+\rightanswer
+$acbac$
+
+\answer
+$abacbab$
+
+\answer
+$aabbcc$
+
+\answer
+$acbba$
+
+\end{question}
+
+\begin{question}
+
+Lequel des mots suivants est un sous-mot de $abcabcbca$ ?
+
+\rightanswer
+$acbba$
+
+\answer
+$abacbab$
+
+\answer
+$aabbcc$
+
+\answer
+$acbac$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{question}
+
+Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage formé
+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}
+
+Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage formé
+des mots dont $w$ est un sous-mot est...
+
+\rightanswer
+rationnel mais pas fini
+
+\answer
+fini et rationnel
+
+\answer
+fini mais pas rationnel
+
+\answer
+ni fini ni rationnel
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $(ab|ba){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+$abbaab$
+
+\answer
+$abaabb$
+
+\answer
+$aaabbb$
+
+\answer
+$abbbba$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $(aa{*}){*}$ sur
+l'alphabet $\Sigma := \{a\}$ ?
+
+\rightanswer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 2\}$ des mots de longueur au
+moins deux
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\in 2\mathbb{N}\}$ des mots de
+longueur paire
+
+\end{question}
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $aa{*}(aa{*}){*}$ sur
+l'alphabet $\Sigma := \{a\}$ ?
+
+\rightanswer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 2\}$ des mots de longueur au
+moins deux
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\in 2\mathbb{N}\text{~et~}|w|>0\}$ des
+mots de longueur paire non nulle
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $(ba{*}){*}$ sur
+l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+l'ensemble des mots qui sont soit le mot vide soit commencent par
+un $b$
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides
+
+\answer
+l'ensemble $\{(ba)^i : i\in\mathbb{N}\}$ des répétitions arbitraires
+du mot $ba$
+
+\answer
+l'ensemble des mots commençant et finissant par un $b$
+
+\answer
+l'ensemble des mots commençant par $b$ et finissant par $a$
+
+\end{question}
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $a{*}(ba{*}){*}$ sur
+l'alphabet $\Sigma := \{a\}$ ?
+
+\rightanswer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\answer
+l'ensemble des mots qui sont soit le mot vide soit commencent par
+un $b$
+
+\answer
+l'ensemble $\{w\in\Sigma^* : |w|\geq 1\}$ des mots non vides
+
+\answer
+l'ensemble $\{(ba)^i : i\in\mathbb{N}\}$ des répétitions arbitraires
+du mot $ba$
+
+\answer
+l'ensemble des mots commençant et finissant par un $a$
+
+\answer
+l'ensemble des mots finissant par $a$
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Laquelle des expresssions rationnelles suivantes est équivalente
+à $a{*}(bba{*}){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\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{*}){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+$abbbba$
+
+\answer
+$aaabbb$
+
+\answer
+$abbaab$
+
+\answer
+$abaabb$
+
+\end{question}
+
+\end{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}
+
+Le langage engendré par la grammaire hors-contexte $S \rightarrow
+aSb\;|\;bSa\;|\;\varepsilon$ est...
+
+\rightanswer
+algébrique mais pas rationnel
+
+\answer
+rationnel et algébrique
+
+\answer
+rationnel mais pas algébrique
+
+\answer
+ni algébrique ni rationnel
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Le langage engendré par la grammaire hors-contexte $S \rightarrow
+abS\;|\;Sba\;|\;\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}
+
+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
+
+\answer
+non semi-décidable
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+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
+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}
+
+
+%
+%
+%
+
+\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}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+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
+oui, et on dispose d'un algorithme permettant de calculer $r'$ en
+fonction de $r$
+
+\answer
+oui, mais on ne dispose pas d'algorithme permettant de calculer $r'$
+en fonction de $r$
+
+\answer
+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
+non, ce langage n'est pas forcément rationnel
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{question}
+
+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
+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
+en remplaçant la transition étiquetée $\varepsilon$ reliant $1$ à $2$
+par une transition étiquetée $a$ (toujours reliant $1$ à $2$)
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Soit $\mathscr{A}$ 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,b$} (q1);
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+Le nombre d'états de l'automate canonique (= automate fini
+déterministe complet ayant le nombre minimum possible d'états)
+équivalent à $\mathscr{A}$ vaut :
+
+\rightanswer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\answer
+quatre ($4$)
+
+\end{question}
+
+\begin{question}
+
+Soit $r := (a|b){*}ab$, expression rationnelle sur l'alphabet $\Sigma
+:= \{a,b\}$.  Le nombre d'états de l'automate canonique (= automate
+fini déterministe complet ayant le nombre minimum possible d'états)
+reconnaissant le langage $L(r)$ dénoté par $r$ vaut :
+
+\rightanswer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\answer
+quatre ($4$)
+
+\end{question}
+
+\begin{question}
+
+Soit $L := \Sigma^*\{ab\} = \{wab : w\in\Sigma^*\}$, le langage des
+mots sur l'alphabet $\Sigma := \{a,b\}$ ayant $ab$ pour suffixe.  Le
+nombre d'états de l'automate canonique (= automate fini déterministe
+complet ayant le nombre minimum possible d'états) reconnaissant le
+langage $L$ vaut :
+
+\rightanswer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\answer
+quatre ($4$)
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{qvar}
+
+\begin{question}
+
+Soit $\mathscr{A}$ 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 node[auto] {$a$} (q2);
+  \draw [->] (q2) to node[auto] {$b$} (q3);
+  \draw [->] (q3) to[loop above] node[auto] {$a,b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+Le nombre d'états de l'automate canonique (= automate fini
+déterministe complet ayant le nombre minimum possible d'états)
+équivalent à $\mathscr{A}$ vaut :
+
+\rightanswer
+quatre ($4$)
+
+\answer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\end{question}
+
+\begin{question}
+
+Soit $r := ab(a|b){*}$, expression rationnelle sur l'alphabet $\Sigma
+:= \{a,b\}$.  Le nombre d'états de l'automate canonique (= automate
+fini déterministe complet ayant le nombre minimum possible d'états)
+reconnaissant le langage $L(r)$ dénoté par $r$ vaut :
+
+\rightanswer
+quatre ($4$)
+
+\answer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\end{question}
+
+\begin{question}
+
+Soit $L := \{ab\}\Sigma^* = \{abw : w\in\Sigma^*\}$, le langage des
+mots sur l'alphabet $\Sigma := \{a,b\}$ ayant $ab$ pour préfixe.  Le
+nombre d'états de l'automate canonique (= automate fini déterministe
+complet ayant le nombre minimum possible d'états) reconnaissant le
+langage $L$ vaut :
+
+\rightanswer
+quatre ($4$)
+
+\answer
+trois ($3$)
+
+\answer
+un ($1$)
+
+\answer
+deux ($2$)
+
+\end{question}
+
+\end{qvar}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des langages suivants sur $\Sigma := \{a,b\}$ \emph{n'est pas}
+rationnel ?
+
+\rightanswer
+l'ensemble des mots dont le nombre total de $a$ vaut au moins $6$ de
+plus que le nombre total de $b$
+
+\answer
+l'ensemble des mots dont la longueur est multiple de $6$
+
+\answer
+l'ensemble des mots dont le nombre total de $a$ est multiple de $6$
+
+\answer
+l'ensemble des mots commençant par $6$ fois la lettre $a$
+
+\answer
+l'ensemble des mots dont le nombre total de $a$ vaut au moins $6$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des langages suivants sur $\Sigma := \{a\}$ est rationnel ?
+
+\rightanswer
+l'ensemble des mots dont la longueur est multiple de $42$ et
+supérieure ou égale à $1729$
+
+\answer
+l'ensemble des mots dont la longueur est une puissance $42$-ième
+(c'est-à-dire de la forme $i^{42}$ pour $i\in\mathbb{N}$)
+
+\answer
+l'ensemble des mots dont la longueur est un nombre premier
+
+\answer
+l'ensemble des mots dont la longueur est une puissance de $42$
+(c'est-à-dire de la forme $42^i$ pour $i\in\mathbb{N}$)
+
+\end{question}
+
+
+%
+%
+%
+
+\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 :=
+\{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 (00bp,-70bp) [draw,circle,state] {$3$};
+\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q3) to node[auto] {$b$} (q4);
+  \draw [->] (q1) to node[auto] {$b$} (q3);
+  \draw [->] (q2) to node[auto] {$a$} (q4);
+  \draw [->] (q2) to[loop right] node[auto] {$a,b$} (q2);
+  \draw [->] (q3) to[loop left] node[auto] {$a,b$} (q3);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+le langage formé des mots de longueur $\geq 2$ dont la dernière lettre
+est égale à la première
+
+\answer
+le langage formé des mots comportant au moins deux $a$ et comportant
+au moins deux $b$
+
+\answer
+le langage formé des mots comportant (quelque part) deux lettres
+identiques consécutives
+
+\answer
+le langage formé des mots dont le nombre de $a$ et le nombre de $b$
+sont tous les deux pairs
+
+\answer
+le langage formé des mots ayant $ab$ comme facteur
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel langage reconnaît 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 (00bp,-70bp) [draw,circle,state] {$3$};
+\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q3) to node[auto] {$b$} (q4);
+  \draw [->] (q1) to node[auto] {$b$} (q3);
+  \draw [->] (q2) to node[auto] {$a$} (q4);
+  \draw [->] (q1) to[loop above] node[auto] {$a,b$} (q1);
+  \draw [->] (q4) to[loop below] node[auto] {$a,b$} (q4);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+le langage formé des mots comportant (quelque part) deux lettres
+identiques consécutives
+
+\answer
+le langage formé des mots de longueur $\geq 2$ dont la dernière lettre
+est égale à la première
+
+\answer
+le langage formé des mots comportant au moins deux $a$ et comportant
+au moins deux $b$
+
+\answer
+le langage formé des mots dont le nombre de $a$ et le nombre de $b$
+sont tous les deux pairs
+
+\answer
+le langage formé des mots ayant $ab$ comme facteur
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel langage reconnaît 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 (00bp,-70bp) [draw,circle,state] {$3$};
+\node (q4) at (70bp,-70bp) [draw,circle,state,final] {$4$};
+  \draw [->] (q1) to node[auto] {$a$} (q2);
+  \draw [->] (q3) to node[auto] {$b$} (q4);
+  \draw [->] (q1) to node[auto] {$a$} (q3);
+  \draw [->] (q2) to node[auto] {$b$} (q4);
+  \draw [->] (q1) to[loop above] node[auto] {$a,b$} (q1);
+  \draw [->] (q4) to[loop below] node[auto] {$a,b$} (q4);
+\end{tikzpicture}
+\end{center}
+
+\rightanswer
+le langage formé des mots ayant $ab$ comme facteur
+
+\answer
+le langage formé des mots comportant (quelque part) deux lettres
+identiques consécutives
+
+\answer
+le langage formé des mots de longueur $\geq 2$ dont la dernière lettre
+est égale à la première
+
+\answer
+le langage formé des mots comportant au moins deux $a$ et comportant
+au moins deux $b$
+
+\answer
+le langage formé des mots dont le nombre de $a$ et le nombre de $b$
+sont tous les deux pairs
+
+\answer
+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\;|\;a\;|\;b$
+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 engendré par la
+grammaire hors-contexte $S \rightarrow aSbS\;|\;\varepsilon$ sur
+l'alphabet $\Sigma := \{a,b\}$ ?
+
+\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}
+%
+%
+%
+\end{document}