More questions.

1 files changed, 382 insertions, 12 deletions

diff --git a/controle-2020qcm.tex b/controle-2020qcm.tex
index 85773b0..b91c05c 100644
--- a/controle-2020qcm.tex
+++ b/controle-2020qcm.tex
@@ -149,8 +149,6 @@ $acbac$
 %
 %
 
-\begin{qvar}
-
 \begin{question}
 
 Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
@@ -170,6 +168,11 @@ ni fini ni rationnel
 
 \end{question}
 
+
+%
+%
+%
+
 \begin{question}
 
 Soit $w$ un mot quelconque sur un alphabet $\Sigma$.  Le langage des
@@ -189,8 +192,6 @@ ni fini ni rationnel
 
 \end{question}
 
-\end{qvar}
-
 
 %
 %
@@ -267,8 +268,6 @@ $abaabb$
 %
 %
 
-\begin{qvar}
-
 \begin{question}
 
 Le langage engendré par la grammaire hors-contexte $S \rightarrow
@@ -288,6 +287,11 @@ ni algébrique ni rationnel
 
 \end{question}
 
+
+%
+%
+%
+
 \begin{question}
 
 Le langage engendré par la grammaire hors-contexte $S \rightarrow
@@ -307,15 +311,11 @@ 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
@@ -339,6 +339,11 @@ semi-décidable mais non décidable
 
 \end{question}
 
+
+%
+%
+%
+
 \begin{question}
 
 Soit $L := \{a^{12i} : i\in\mathbb{N}\}$ l'ensemble des mots sur
@@ -362,8 +367,6 @@ semi-décidable mais non décidable
 
 \end{question}
 
-\end{qvar}
-
 
 %
 %
@@ -485,6 +488,373 @@ 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{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}
+
+
 \end{qcm}
 %
 %