summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20210618.tex272
-rw-r--r--notes-inf105.tex52
-rw-r--r--quiz-20220428.tex238
3 files changed, 444 insertions, 118 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex
index 585b9c1..aa30be9 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -102,7 +102,7 @@ Durée : 1h30
Barème \emph{indicatif} : 8+7+5.
\ifcorrige
-Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse).
+Ce corrigé comporte 9 pages (page de garde incluse).
\else
Cet énoncé comporte 3 pages (page de garde incluse).
\fi
@@ -193,7 +193,8 @@ un automate fini \emph{déterministe complet}.
\begin{corrige}
L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet :
pour le transformer en automate déterministe complet, on se contente
-de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ :
+pour obtenir l'automate $\mathscr{A}_2$ de lui ajouter un puits vers
+lequel on fait pointer la seule transition manquante :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
@@ -230,11 +231,11 @@ L'automate $\mathscr{A}_2$ est déterministe complet sans état
inaccessible. On commence l'algorithme de minimisation en séparant
les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$. On
sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$
-selon que la transition étiquetée $a$ conduit à un état final. Enfin,
-la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux.
-Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$,
-$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$
-suivant :
+selon que la transition étiquetée $a$ conduit à un état final ou non.
+Enfin, la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en
+deux. Finalement, on aboutit aux classes suivantes : $\{0\}$,
+$\{1,2\}$, $\{3,4,5\}$ et $\{\bot\}$ (qu'on rebaptise $0,1,3,\bot$
+respectivement), et à l'automate minimal $\mathscr{A}_3$ suivant :
\begin{center}
\begin{tikzpicture}[>=latex,line join=bevel,automaton]
\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
@@ -394,14 +395,17 @@ nécessairement $aba$ comme préfixe.
Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine
(étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre
(i.e., en démarrant par la règle $1$), les descendants du deuxième
-fils (celui étiqueté $S$) forment eux-mêmes un arbre d'analyse
-$\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ (d'après la
-question précédente) commence par $a$, si bien que le mot $w = aw'bc$
-analysé par $\mathscr{T}$ commence par $aa$. (Si on préfère : une
-dérivation de la forme $S \buildrel 1\over\Rightarrow aSbc
-\mathrel{\Rightarrow^*} w$ a nécessairement $w = aw'bc$ où $w'$ est le
-mot obtenu en appliquant les mêmes règles à $S$, qui commence donc
-par $a$, si bien que $w$ commence par $aa$.)
+fils (celui étiqueté $S$, y compris lui-même) forment eux-mêmes un
+arbre d'analyse $\mathscr{T}'$ selon $G$, dont le mot analysé $w'$
+commence par $a$ (d'après la question précédente), si bien que le mot
+$w = aw'bc$ analysé par $\mathscr{T}$ commence par $aa$. (Avec la
+notation qui sera introduite ci-dessous, on a $\mathscr{T} =
+\mathbf{R}_1(\mathscr{T}')$.)
+
+Si on préfère : une dérivation de la forme $S \buildrel
+1\over\Rightarrow aSbc \mathrel{\Rightarrow^*} w$ a nécessairement $w
+= aw'bc$ où $w'$ est le mot obtenu en appliquant les mêmes règles
+à $S$, qui commence donc par $a$, si bien que $w$ commence par $aa$.
Un raisonnement analogue conduit à conclure que tout mot dérivé en
démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc
@@ -415,10 +419,10 @@ les fils de la racine dans tout arbre d'analyse de $w$).
\begin{corrige}
Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots
-ayant une dérivation selon $G$ démarrant par les règles $0,1,2$
-respectivement, on a trivialement $L_0 = \{abc\}$ et on vient de voir
-que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ ont
-$aba$ comme préfixe. Notamment :
+ayant (au moins) une dérivation selon $G$ démarrant par les règles
+$0,1,2$ respectivement, on a trivialement $L_0 = \{abc\}$ et on vient
+de voir que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$
+ont $aba$ comme préfixe. Notamment :
\begin{itemize}
\item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle
démarre une dérivation de $w$ est déterminée par $w$), et
@@ -433,22 +437,90 @@ expliquer comment trouver tous les arbres d'analyse du mot $awbc$
d'une part, et du mot $abwc$ d'autre part.
\begin{corrige}
-Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, on obtient
-un arbre d'analyse $\mathscr{T}^\sharp$ de $w^\sharp := awbc$ de la
-façon suivante : les quatre fils de la racine (étiquetée $S$) de
-$\mathscr{T}^\sharp$ sont étiquetés $a,S,b,c$ respectivement (i.e., on
-démarre par la règle $1$), et le second fils (celui étiqueté $S$) a
-pour descendance une copie de $\mathscr{T}$ : ceci forme manifestement
-un arbre d'analyse selon $G$, dont le mot analysé est $w^\sharp :=
-awbc$. \emph{Réciproquement}, comme $w^\sharp := awbc$ commence
-par $aa$ (i.e., a $aa$ pour préfixe), on vient de voir que toute
-dérivation de ce mot selon $G$ démarre nécessairement par la
-règle $1$, donc a la forme qu'on vient de décrire. (Autrement dit :
-$\mathscr{T} \mapsto \mathscr{T}^\sharp$ définit une bijection entre
-les arbres d'analyse de $w$ et ceux de $awbc$.)
-
-Les mêmes considérations valent, \textit{mutatis mutandis} pour les
-mots de la forme $w^\flat := abwc$ en commençant par la règle $2$.
+Afin de s'épargner des répétitions fastidieuses, on définit pour toute
+la suite de ce corrigé des notations pour les arbres d'analyse
+selon $G$ démarrant par les règles $0,1,2$ respectivement, à savoir :
+\begin{itemize}
+\item on notera $\mathbf{R}_0$ l'arbre d'analyse associé à la
+ règle $0$, c'est-à-dire l'arbre dont la racine, étiquetée $S$, a
+ exactement trois fils, qui sont des feuilles, et qui sont étiquetés
+ $a,b,c$ dans cet ordre ;
+\item si $\mathscr{T}$ est un arbre d'analyse selon $G$, on notera
+ $\mathbf{R}_1(\mathscr{T})$ l'arbre d'analyse associé à la règle $1$
+ suivie des règles décrites par $\mathscr{T}$, c'est-à-dire l'arbre
+ dont la racine, étiquetée $S$, a exactement quatre fils, étiquetés
+ $a,S,b,c$ dans cet ordre, où le premier et les deux derniers sont
+ des feuilles et où les descendants du second (y compris lui-même)
+ forment une copie de l'arbre d'analyse $\mathscr{T}$ ;
+\item de façon analogue, si $\mathscr{T}$ est un arbre d'analyse
+ selon $G$, on notera $\mathbf{R}_2(\mathscr{T})$ l'arbre d'analyse
+ associé à la règle $2$ suivie des règles décrites par $\mathscr{T}$,
+ c'est-à-dire l'arbre dont la racine, étiquetée $S$, a exactement
+ quatre fils, étiquetés $a,b,S,c$ dans cet ordre, où les deux
+ premiers et le dernier sont des feuilles et où les descendants du
+ troisième (y compris lui-même) forment une copie de l'arbre
+ d'analyse $\mathscr{T}$.
+\end{itemize}
+
+Soit graphiquement :
+\begin{center}
+\begin{tabular}{c|c|c}
+$\mathbf{R}_0$&$\mathbf{R}_1(\mathscr{T})$&$\mathbf{R}_2(\mathscr{T})$\\
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (20.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0);
+\node (c0) at (40.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0);
+\node (S1) at (20.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1);
+\node (b0) at (40.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$}; \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$}; \draw (S0) -- (b0);
+\node (S1) at (40.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$}; \draw (S0) -- (S1);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$}; \draw (S0) -- (c0);
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+(par exemple, l'arbre d'analyse répondant à la question $1$ est
+l'arbre $\mathbf{R}_2(\mathbf{R}_1(\mathbf{R}_0))$).
+
+Manifestement, tout arbre d'analyse selon $G$ est soit l'arbre
+$\mathbf{R}_0$, soit de la forme $\mathbf{R}_1(\mathscr{T})$ ou
+$\mathbf{R}_2(\mathscr{T})$ avec $\mathscr{T}$ un autre arbre
+(strictement plus petit).
+
+Répondons maintenant à la question posée.
+
+Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, alors
+$\mathbf{R}_1(\mathscr{T})$ est un arbre d'analyse de $awbc$ (toujours
+selon $G$). Mais réciproquement, comme $awbc$ commence par $aa$
+(i.e., a $aa$ pour préfixe), on a vu en (4) que toute dérivation du
+mot $awbc$ selon $G$ démarre nécessairement par la règle $1$,
+c'est-à-dire que tout arbre d'analyse de $awbc$ est de la
+forme $\mathbf{R}_1(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du deuxième fils de la
+racine). Bref : $\mathbf{R}_1$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
+
+De même, si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$,
+alors $\mathbf{R}_2(\mathscr{T})$ est un arbre d'analyse de $abwc$.
+Mais réciproquement, comme $abwc$ commence par $aba$ (i.e., a $aba$
+pour préfixe), on a vu en (4) que toute dérivation du mot $abwc$
+selon $G$ démarre nécessairement par la règle $2$, c'est-à-dire que
+tout arbre d'analyse de $abwc$ est de la
+forme $\mathbf{R}_2(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du troisième fils de la
+racine). Bref : $\mathbf{R}_2$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
\end{corrige}
(6) En déduire que tout mot $w \in L$ possède un unique arbre
@@ -456,57 +528,60 @@ d'analyse selon $G$, et proposer (sur la base des questions
précédentes) un algorithme qui le calcule.
\begin{corrige}
-D'après les questions suivantes, tout mot de $L$ est dans un et un
-seul des trois cas suivants : soit c'est le mot $abc$ produit par la
-règle $abc$, soit il commence par $aa$ et c'est un mot de la forme
-$awbc$ produit par une dérivation démarrant par la règle $1$ puis en
-suivant une dérivation de $w$, soit il commence par $aba$ et c'est un
-mot de la forme $abwc$ produit par une dérivation démarrant par la
-règle $2$ puis en suivant une dérivation de $w$. (Si on veut, $L$ est
-réunion disjointe de $L_0,L_1,L_2$ où $L_0 = \{abc\}$ et $w \mapsto
-awbc$ est une bijection $L \to L_1$ et $w \mapsto abwc$ est une
-bijection $L \to L_2$.)
+En reformulant les conclusions des questions suivantes, tout mot $w$
+de $L$ est dans un et un seul des trois cas suivants :
+\begin{itemize}
+\item soit $w$ est le mot $abc$ et son unique arbre d'analyse selon $G$
+ est $\mathbf{R}_0$,
+\item soit $w$ commence par $aa$ et alors $w$ est de la forme $aw'bc$
+ et tout arbre d'analyse de $w$ selon $G$ est de la forme
+ $\mathbf{R}_1(\mathscr{T}')$ pour un unique arbre d'analyse
+ $\mathscr{T}'$ de $w'$,
+\item soit $w$ commence par $aba$ et alors $w$ est de la forme $abw'c$
+ et tout arbre d'analyse de $w$ selon $G$ est de la forme
+ $\mathbf{R}_2(\mathscr{T}')$ pour un unique arbre d'analyse
+ $\mathscr{T}'$ de $w'$.
+\end{itemize}
Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un
-unique arbre d'analyse selon $G$ : en effet, il est soit de la forme
-$abc$, soit de la forme $aw'bc$, soit de la forme $abw'c$ avec dans
-les deux derniers cas $|w'| < |w|$ (précisément $|w'| = |w|-3$), donc
-$w'$ a un unique arbre d'anayse selon $G$ par récurrence, d'où il
-résulte que $w$ a un unique arbre d'analyse (qui s'obtient à partir de
-celui de $w'$ en mettant la règle $1$ ou $2$ au sommet comme expliqué
-dans la question (5)).
+unique arbre d'analyse selon $G$ : en effet, dans le premier des trois
+cas ci-dessus, $w$ a pour unique arbre d'analyse $\mathbf{R}_0$, et
+dans les deux derniers cas on a $|w'| < |w|$ (précisément $|w'| =
+|w|-3$), donc $w'$ a un unique arbre d'anayse $\mathscr{T}'$ selon $G$
+par l'hypothèse de récurrence, d'où il résulte que $w$ a lui aussi un
+unique arbre d'analyse (à savoir $\mathbf{R}_1(\mathscr{T}')$ ou
+$\mathbf{R}_2(\mathscr{T}')$).
+
+La grammaire $G$ est donc inambiguë.
Cette démonstration est constructive, c'est-à-dire qu'on a
-l'algorithme suivant qui analyse un mot $w$ :
+l'algorithme suivant qui analyse un mot $w$ et renvoie l'unique arbre
+d'analyse de $w$ selon $G$ (s'il existe, ou signale une erreur
+d'analyse dans le cas contraire) :
\begin{itemize}
-\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre de la
- règle $0$ (c'est-à-dire ayant une racine étiquetée $S$ avec trois
- fils, tous des feuilles, étiquetés $a,b,c$ respectivement) ;
+\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre
+ $\mathbf{R}_0$ ;
\item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$
- (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
+ (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
obtenu en effaçant le $a$ initial et le $bc$ final, appliquer
récursivement l'algorithme qu'on est en train de définir au
- mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
- l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $1$ et
- de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
- étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,S,b,c$
- respectivement, et le second fils a pour descendance une copie
- de $\mathscr{T}'$) ;
+ mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+ et renvoyer $\mathbf{R}_1(\mathscr{T}')$ ;
\item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$
- (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
+ (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
obtenu en effaçant le $ab$ initial et le $c$ final, appliquer
récursivement l'algorithme qu'on est en train de définir au
- mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
- l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $2$ et
- de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
- étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,b,S,c$
- respectivement, et le troisième fils a pour descendance une copie
- de $\mathscr{T}'$) ;
+ mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+ et renvoyer $\mathbf{R}_2(\mathscr{T}')$ ;
\item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence
- par autre chose que $aa$ ou $aba$), terminer avec une erreur
+ par autre chose que $aa$ ou $aba$), abandonner avec une erreur
d'analyse.
\end{itemize}
-\vskip-\baselineskip\strut
+(L'algorithme termine en temps fini parce que les appels récursifs se
+font sur des mots de longueur strictement plus courte. Il s'agit d'un
+algorithme par « descente récursive », qui se transforme facilement,
+quitte à remplacer la pile des appels récursifs en une pile en tant
+que structure de données, en un analyseur LL.)
\end{corrige}
@@ -530,11 +605,11 @@ semi-décidable ? On justifiera soigneusement les réponses.
\begin{corrige}
Le langage proposé n'est pas rationnel car il n'est pas algébrique.
-Il est décidable car il est évident qu'on peut algorithmiquement
-vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+Il est décidable car il est évident qu'on peut algorithmiquement d'une
+part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
-par automate fini) puis vérifier qu'il a autant de $a$ que de $b$ que
-de $c$.
+par automate fini) et d'autre part vérifier qu'il a autant de $a$ que
+de $b$ que de $c$.
Étant décidable, il est notamment semi-décidable.
\end{corrige}
@@ -561,28 +636,33 @@ L'ensemble $J$ est-il décidable ? Semi-décidable ? On justifiera
soigneusement.
\begin{corrige}
-L'ensemble $J$ n'est pas semi-décidable. En effet, supposons par
-l'absurde qu'on dispose d'un algorithme $T$ qui semi-décide $J$ (où
-« semi-décider » un ensemble $Z$ signifie : terminer en renvoyant $1$
-(=vrai) si l'entrée $z$ fournie appartient à $Z$, et ne pas terminer
-sinon). Fixons une fois pour toutes $f$ (le code d')un programme qui,
-donnée une entrée $x$, termine immédiatement (en ignorant $x$). Alors
-trivialement $(f,x) \in H$ quel que soit $x$ ; donc, par définition
-de $J$, on a $(f,e,x) \in J$ si et seulement si $(e,h) \not \in H$.
-On dispose alors d'un algorithme $T'$ qui semi-décide le
-complémentaire de $H$, défini de la manière suivante : donnés $(e,x)$,
-on applique l'algorithme $T$ (qu'on a supposé exister) au triplet
-$(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in J$), on
-renvoie $1$ (sinon, bien sûr, on ne termine jamais) ; par
+L'ensemble $J$ n'est pas semi-décidable.
+
+Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme
+$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$
+signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie
+appartient à $Z$, et ne pas terminer sinon). Fixons une fois pour
+toutes (le code d')un programme $f$ qui, donnée une entrée $x$,
+termine immédiatement (en ignorant $x$). Alors trivialement $(f,x)
+\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x)
+\in J$ si et seulement si $(e,h) \not \in H$.
+
+On considère alors l'algorithme $T'$, défini de la manière suivante :
+donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister)
+au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in
+J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais). Par
construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
$(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
-termine pas ; ceci signifie justement que $T'$ semi-décide le
-complémentaire de $H$. Or le complémentaire de $H$ n'est pas
-semi-décidable (car si le complémentaire de $H$ était semi-décidable,
-on aurait à la fois $H$ et son complémentaire semi-décidables, donc
-$H$ serait décidable, et on sait qu'il ne l'est pas). C'est une
-contradiction : $J$ n'est donc pas semi-décidable. \textit{A
- fortiori}, $J$ n'est pas décidable.
+termine pas. Ceci signifie que $T'$ semi-décide le complémentaire
+de $H$.
+
+Or le complémentaire de $H$ n'est pas semi-décidable (car si le
+complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et
+son complémentaire semi-décidables, donc $H$ serait décidable, et on
+sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas
+exister. C'est une contradiction : $J$ n'est donc pas semi-décidable.
+
+\textit{A fortiori}, $J$ n'est pas décidable.
\end{corrige}
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 86a9d53..b56b958 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1229,7 +1229,7 @@ servent à ancrer l'expression au début et à la fin de la chaîne
respectivement : c'est-à-dire que rechercher « \texttt{a} » recherche
un \texttt{a} quelconque à l'intérieur de la chaîne donnée, rechercher
« \texttt{\char"5E\relax a} » demande que le \texttt{a} soit au début
-de la chaîne donnée rechercher « \texttt{a\char"24} » demande que le
+de la chaîne donnée, rechercher « \texttt{a\char"24} » demande que le
\texttt{a} soit à la fin de la chaîne donnée, et rechercher
« \texttt{\char"5E\relax a\char"24} » demande que la chaîne donnée
soit exactement \texttt{a} (cet exemple n'est donc pas très utile,
@@ -3641,27 +3641,35 @@ Symboliquement :
\end{tikzpicture}
\end{center}
-Cette transformation doit être effectuée \emph{simultanément pour
- toute paire}\footnote{Plutôt qu'examiner toutes les paires, on peut
- se contenter d'examiner les cas où \emph{soit} il existe une
- transition de $q_1$ vers $q_2$ \emph{soit} il existe à la fois une
- transition de $q_1$ vers $q$ et une transition de $q$ vers $q_2$.
- En revanche, insistons bien sur le fait que le cas où $q_1$ et $q_2$
- coïncide doit être traité comme les autres.} $(q_1,q_2)$ d'états
-de $A$ pour laquelle $q_1\not\in\{q,q_\infty\}$ et
-$q_2\not\in\{q,q_0\}$ : pour chaque telle paire, on remplace
-l'étiquette de la transition $r_{12}$ entre eux par
-$(r_{12}|r_1(s){*}r_2)$. Ceci ne change pas le fonctionnement de
-l'automate, car tout chemin dans $A$ peut être remplacé par un chemin
-dans $A'$ en effaçant simplement les $q$ (si on considère $q_1$ et
-$q_2$ les états avant un bloc de $q$ dans le chemin, on voit que le
-chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se transformer
-en $q_1 \to q_2$ en consommant un mot qui vérifie l'expression
-rationnelle $(r_{12}|r_1(s){*}r_2)$).
-
-En éliminant (dans n'importe quel ordre) tous les états autres que
-$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
-transition $(q_0,r,q_\infty)$, qui est donc essentiellement
+Pour éliminer l'état $q$, cette transformation doit être effectuée
+\emph{simultanément pour toute paire} $(q_1,q_2)$ d'états de $A$ (avec
+$q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$) pour laquelle il
+existe une transition de $q_1$ vers $q$ et une transition de
+$q$ vers $q_2$, \emph{y compris} s'il n'y avait pas déjà une
+transition de $q_1$ vers $q_2$, et \emph{y compris} si $q_1=q_2$ :
+pour \emph{chaque} telle paire, on remplace l'étiquette de la
+transition $r_{12}$ entre eux par $(r_{12}|r_1(s){*}r_2)$. (On
+prendra garde aux cas particuliers suivants : si la transition de $q$
+vers lui-même n'existait pas, ce qui revient à prendre $s=\bot$, alors
+on remplace la transition $r_{12}$ par $(r_{12}|r_1 r_2)$ en vertu du
+fait que $(\bot){*}$ est équivalente à $\underline{\varepsilon}$ ; et
+si la transition de $q_1$ vers $q_2$ n'existait pas, ce qui revient à
+prendre $r_{12}=\bot$, alors on la crée avec l'étiquette
+$r_1(s){*}r_2$ ; et bien sûr, en combinant ces deux cas particuliers,
+s'il n'y avait ni transition de $q$ vers lui-même ni de
+$q_1$ vers $q_2$, on crée cette dernière avec l'étiquette $r_1 r_2$.)
+
+La transformation qui vient d'être décrite ne change pas le
+fonctionnement de l'automate, car tout chemin dans $A$ peut être
+remplacé par un chemin dans $A'$ en effaçant simplement les $q$ (si on
+considère $q_1$ et $q_2$ les états avant un bloc de $q$ dans le
+chemin, on voit que le chemin $q_1 \to q \to q \to \cdots \to q \to
+q_2$ peut se transformer en $q_1 \to q_2$ en consommant un mot qui
+vérifie l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
+
+En éliminant (successivement dans n'importe quel ordre) tous les états
+autres que $q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant
+une unique transition $(q_0,r,q_\infty)$, qui est donc essentiellement
l'expression rationnelle $r$.
\end{proof}
diff --git a/quiz-20220428.tex b/quiz-20220428.tex
new file mode 100644
index 0000000..faec769
--- /dev/null
+++ b/quiz-20220428.tex
@@ -0,0 +1,238 @@
+%% 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}
+%
+\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})}~}
+\newcommand\rightanswer{%
+\stepcounter{answcnt}\smallskip\leavevmode\llap{$\rightarrow$}\textbf{(\Alph{answcnt})}~}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+%
+\begin{document}
+
+\textbf{Questions pour INF105 pour le QCM du 2022-04-28.}
+
+Chaque question comporte \emph{une et une seule réponse correcte}.
+Elle a été indiquée par une flèche ci-dessous :
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants est un facteur de $abcabcabc$ sur
+l'alphabet $\Sigma := \{a,b,c\}$ ?
+
+\answer
+$abab$
+
+\answer
+$aaac$
+
+\answer
+$bcbc$
+
+\rightanswer
+$cabc$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants est un sous-mot de $abcabcabc$ sur
+l'alphabet $\Sigma := \{a,b,c\}$ ?
+
+\answer
+$abacbab$
+
+\rightanswer
+$acbbc$
+
+\answer
+$aabbcc$
+
+\answer
+$acbacb$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$aabbab$
+
+\answer
+$bababa$
+
+\rightanswer
+$ababab$
+
+\answer
+$aaabbb$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Lequel des mots suivants appartient au langage dénoté par l'expression
+rationnelle $a{*}b{*}a{*}b{*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\rightanswer
+$aaabbb$
+
+\answer
+$ababab$
+
+\answer
+$babbba$
+
+\answer
+$baaaba$
+
+\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}
+
+
+%
+%
+%
+
+\begin{question}
+
+Quel langage dénote l'expression rationnelle $a{*}(ba{*}ba{*}){*}$ sur
+l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+l'ensemble $\Sigma^*$ de tous les mots
+
+\rightanswer
+l'ensemble des mots dont le nombre total de $b$ est pair
+
+\answer
+l'ensemble des mots dont le nombre total de $b$ est $\geq 2$
+
+\answer
+l'ensemble des mots commençant et finissant à la fois par un $a$
+
+\answer
+l'ensemble des mots commençant par un $a$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Laquelle des expressions rationnelles suivantes est équivalente à
+l'expression $(aa\,|\,aba)$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$ab{*}a$
+
+\answer
+$a{*}ba{*}$
+
+\rightanswer
+$a(\underline{\varepsilon}|b)a$
+
+\answer
+$(a|ab)(ab|a)$
+
+\end{question}
+
+
+%
+%
+%
+
+\begin{question}
+
+Laquelle des expressions rationnelles suivantes est équivalente à
+l'expression $(ab){*}$ sur l'alphabet $\Sigma := \{a,b\}$ ?
+
+\answer
+$(a|b){*}$
+
+\answer
+$ab(ab){*}$
+
+\answer
+$(ba){*}$
+
+\rightanswer
+$\underline{\varepsilon} \,|\, a(ba){*}b$
+
+\end{question}
+
+
+%
+%
+%
+\end{document}