From ad62395720f074e73283387e951191e342dd0f93 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 4 Jun 2020 16:51:03 +0200 Subject: More questions. --- controle-2020qcm.tex | 394 +++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file 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} % % -- cgit v1.2.3