path: root/controle-2020qcm.tex

%% 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}