summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-06-17 18:56:09 +0200
committerDavid A. Madore <david+git@madore.org>2021-06-17 18:56:09 +0200
commit928749936af9b1e6459419498864300c570613b7 (patch)
treefe706952b7578a7c15ffd5b7ef745a99bf310d81
parent54986174f0303bf568bb10ec45a7498e76dec3cf (diff)
downloadinf105-928749936af9b1e6459419498864300c570613b7.tar.gz
inf105-928749936af9b1e6459419498864300c570613b7.tar.bz2
inf105-928749936af9b1e6459419498864300c570613b7.zip
Write answers to first exercise.
-rw-r--r--controle-20210618.tex147
1 files changed, 147 insertions, 0 deletions
diff --git a/controle-20210618.tex b/controle-20210618.tex
index a2bf362..ea91ea0 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -135,6 +135,11 @@ immédiatement suivis par la lettre $a$, puis n'importe quoi).
$a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$. On ne demande pas
de justifier les réponses.
+\begin{corrige}
+Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas
+à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$.
+\end{corrige}
+
\emph{Il est fortement conseillé, dans toutes les questions suivantes,
d'utiliser les mots qui viennent d'être listés pour vérifier les
automates successifs qu'on calculera.} (Par exemple, pour un
@@ -155,22 +160,164 @@ l'automate ainsi obtenu.
À défaut de donner l'automate de Glushkov ou de Thompson, donner un
NFA reconnaissant $L$ pourra apporter une partie des points.)
+\begin{corrige}
+L'automate $\mathscr{A}_1$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
(2) Déterminiser l'automate $\mathscr{A}_1$. On appellera
$\mathscr{A}_2$ l'automate en question. On rappelle qu'on attend ici
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$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
(3) Minimiser l'automate $\mathscr{A}_2$. On appellera
$\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
langage $L$).
+\begin{corrige}
+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 :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
(4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet
$\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$
complémentaire de $L$.
+\begin{corrige}
+Il suffit d'échanger les états finaux et non-finaux
+dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state] {$3$};
+\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
+\end{tikzpicture}
+\end{center}
+(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur
+ce nouvel automate, en revanche $3$ en est un. Ces nom sont, bien
+sûr, sans aucun impact sur le fonctionnement de l'automate.)
+\end{corrige}
+
(5) En appliquant l'algorithme d'élimination des états, déduire
de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le
langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne
vérifient pas $r$).
+\begin{corrige}
+Pour procéder à l'algorithme d'élimination des états, on commence par
+donner à l'automate un unique état final sans aucune transition qui en
+part, appelons-le $\infty$. On peut aussi d'ores et déjà éliminer
+l'état $3$ qui est maintenant inutile :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$};
+\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
+\draw[->] (q0) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final);
+\end{tikzpicture}
+\end{center}
+L'élimination de l'état $1$ conduit à remplacer la transition
+$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et
+l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$.
+Finalement, on a affaire à un automate ayant les seuls états $0$
+(initial) et $\infty$ (final) avec la seule transition $0\to\infty$
+étiquetée par l'expression rationnelle $s$ recherchée :
+\[
+\varepsilon \,|\, bb{*} \,|\, a(a|b){*}
+\]
+qui dénote le langage $M$ complémentaire de $L$. (Autrement dit : un
+mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$
+suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit
+formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de
+n'importe quoi.)
+\end{corrige}
%