From fea3f1a462dc875532282776afd6022211999ac1 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 7 Dec 2017 12:21:07 +0100
Subject: Add a further question to an exercise.

---
 exercices1.tex | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)

(limited to 'exercices1.tex')

diff --git a/exercices1.tex b/exercices1.tex
index 95d09de..11f7d69 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -282,6 +282,10 @@ quatre états).  Décrire brièvement la signification de ces quatre
 états, de façon à vérifier qu'il accepte le même langage que décrit
 en (0).
 
+(3) Éliminer les états de l'automate d'origine de façon à obtenir une
+expression rationnelle dénotant le langage reconnu par le langage
+décrit en (0).
+
 \begin{corrige}
 (0) L'automate proposé accepte les mots ayant soit deux $a$
   consécutifs (en passant par le chemin $0\to 1\to 2\to 3\to 7$) soit
@@ -445,6 +449,70 @@ un $b$, le $A$ signifie qu'il a lu deux $a$ consécutifs ou bien deux
 $b$ consécutifs.  Sur cette description, il est clair que l'automate
 accepte les mots contenant deux $a$ consécutifs ou bien deux $b$
 consécutifs.
+
+(3) L'élimination des états $1$ à $6$ peut se faire dans un ordre
+quelconque et conduit à l'automate (à transitions étiquetées par des
+expressions rationnelles) suivant :
+\begin{center}
+%%% begin ex1p2a2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,20.549bp) [draw,circle,state,initial] {$0$};
+  \node (q7) at (104bp,20.549bp) [draw,circle,state,final] {$7$};
+  \draw [->] (q0) ..controls (47.743bp,20.549bp) and (62.773bp,20.549bp)  .. node[auto] {$aa$} (q7);
+  \draw [->] (q0) ..controls (42.511bp,4.2138bp) and (55.796bp,-1.5495bp)  .. (68bp,1.5495bp) .. controls (71.958bp,2.5545bp) and (75.953bp,4.1071bp)  .. node[auto,below] {$bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a2 %%%
+\end{center}
+
+Il y a plusieurs flèches entre les mêmes états : quitte à les
+remplacer par des disjonctions, on obtient :
+\begin{center}
+%%% begin ex1p2a3 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+  \node (q7) at (119bp,18bp) [draw,circle,state,final] {$7$};
+  \draw [->] (q0) ..controls (51.292bp,18bp) and (73.384bp,18bp)  .. node[auto] {$aa|bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a3 %%%
+\end{center}
+
+Enfin, on doit éliminer les états $0$ et $7$ eux-mêmes : pour cela, on
+ajoute un nouvel état initial qui ne soit la cible d'aucune flèche et
+un nouvel état final d'où ne part aucune flèche,
+\begin{center}
+%%% begin ex1p2a4 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (qi) at (18bp,18bp) [draw,circle,state,initial] {$\phantom{0}$};
+  \node (q0) at (97bp,18bp) [draw,circle,state] {$0$};
+  \node (q7) at (198bp,18bp) [draw,circle,state] {$7$};
+  \node (qf) at (277bp,18bp) [draw,circle,state,final] {$\phantom{7}$};
+  \draw [->] (qi) ..controls (45.659bp,18bp) and (57.817bp,18bp)  .. node[auto] {$\varepsilon$} (q0);
+  \draw [->] (q7) ..controls (225.66bp,18bp) and (237.82bp,18bp)  .. node[auto] {$\varepsilon$} (qf);
+  \draw [->] (q0) ..controls (130.29bp,18bp) and (152.38bp,18bp)  .. node[auto] {$aa|bb$} (q7);
+  \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+  \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a4 %%%
+\end{center}
+
+Et l'élimination des états $0$ et $7$ dans un ordre quelconque conduit
+finalement à l'expression rationnelle $(a|b){*}(aa|bb)(a|b){*}$.
 \end{corrige}
 
 
-- 
cgit v1.2.3