Add a further question to an exercise.

4 files changed, 103 insertions, 0 deletions

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}
 
 
diff --git a/figs/ex1p2a2.dot b/figs/ex1p2a2.dot
new file mode 100644
index 0000000..1cd6e46
--- /dev/null
+++ b/figs/ex1p2a2.dot
@@ -0,0 +1,11 @@
+digraph ex1p2a2 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q7 [style="state,final",label="7"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a,b",topath="loop below"];
+	q0 -> q7 [label="aa"];
+	q0 -> q7 [label="bb",lblstyle="auto,below"];
+	q7 -> q7 [label="a,b",topath="loop below"];
+}
diff --git a/figs/ex1p2a3.dot b/figs/ex1p2a3.dot
new file mode 100644
index 0000000..5c03856
--- /dev/null
+++ b/figs/ex1p2a3.dot
@@ -0,0 +1,10 @@
+digraph ex1p2a3 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial",label="0"];
+	q7 [style="state,final",label="7"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a|b",topath="loop below"];
+	q0 -> q7 [label="aa|bb"];
+	q7 -> q7 [label="a|b",topath="loop below"];
+}
diff --git a/figs/ex1p2a4.dot b/figs/ex1p2a4.dot
new file mode 100644
index 0000000..56ee8b6
--- /dev/null
+++ b/figs/ex1p2a4.dot
@@ -0,0 +1,14 @@
+digraph ex1p2a4 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	qi [style="state,initial",label="0",texlbl="$\phantom{0}$"];
+	q0 [style="state",label="0"];
+	q7 [style="state",label="7"];
+	qf [style="state,final",label="7",texlbl="$\phantom{7}$"];
+	edge [texmode="math",lblstyle="auto"];
+	qi -> q0 [label="e",texlbl="$\varepsilon$"];
+	q0 -> q0 [label="a|b",topath="loop below"];
+	q0 -> q7 [label="aa|bb"];
+	q7 -> q7 [label="a|b",topath="loop below"];
+	q7 -> qf [label="e",texlbl="$\varepsilon$"];
+}