An exercise on Kleene's algorithm.

2 files changed, 102 insertions, 0 deletions

diff --git a/exercices3.tex b/exercices3.tex
index c1a763e..8d5c0ad 100644
--- a/exercices3.tex
+++ b/exercices3.tex
@@ -266,6 +266,94 @@ description, il est clair que l'automate fait ce qui était demandé.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercice
+
+Donner plusieurs (au moins trois) expressions rationnelles
+équivalentes dénotant le langage reconnu par l'automate suivant sur
+l'alphabet $\Sigma = \{a,b\}$ :
+
+\begin{center}
+%%% begin ex3p2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$};
+  \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$};
+  \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp)  .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp)  .. node[auto] {$b$} (q0);
+  \draw [->] (q2) to[loop right] node[auto] {$b$} (q2);
+  \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp)  .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q0) to[loop left] node[auto] {$a$} (q0);
+  \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp)  .. node[auto] {$b$} (q1);
+  \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp)  .. node[auto] {$a$} (q2);
+%
+\end{tikzpicture}
+
+
+%%% end ex3p2 %%%
+\end{center}
+(On pourra considérer les ordres suivants d'élimination des états :
+$2,1,0$, $1,2,0$ et $0,2,1$.)
+
+\begin{corrige}
+Si on commence par éliminer l'état $2$ (en considérant l'automate
+comme un automate à transitions étiquetées par des expressions
+rationnelles), l'état $1$ reçoit une transition vers lui-même
+étiquetée $ab{*}a$.  Si on élimine l'état $1$, l'état $0$ reçoit à la
+place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$,
+qu'on peut fusionner avec la transition vers lui-même déjà existante
+étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$.
+Quitte éventuellement à ajouter un nouvel état initial (conduisant à
+$0$ par une transition spontanée) et un nouvel état final (vers lequel
+$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on
+obtient finalement l'expression rationnelle
+\[
+(a|b(ab{*}a){*}b){*}
+\]
+
+Si on commence par éliminer l'état $1$, il apparaît une transition
+$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut
+appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas
+de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter
+par $\bot$, symbole d'expression rationnelle qui dénote le lagange
+vide, et l'expression rationnelle $\bot{*}$ est équivalente
+à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit
+lui aussi une transition vers lui-même (en passant par $1$) étiquetée
+$aa$, qu'on peut fusionner avec la transition vers lui-même déjà
+existante étiquetée par $b$ pour obtenir une transition étiquetée
+$b|aa$.  L'élimination de l'état $2$ fait alors apparaître une
+transition de $0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut
+fusionner avec la transition vers lui-même déjà étiquetée par $a$ pour
+une seule étiquetée par $a|b(a(b|aa){*}a){*}b$.  On obtient finalement
+\[
+(a|b(a(b|aa){*}a){*}b){*}
+\]
+(en particulier, cette expression est équivalente à celle obtenue
+précédemment).
+
+Si on préfère commencer par éliminer l'état $0$, il faut au préalable
+ajouter un nouvel état initial $I$ (conduisant à $0$ par une
+transition spontanée) et un nouvel état final $F$ (vers lequel $0$
+conduit par une transition spontanée).  L'élimination de l'état $0$
+fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une
+transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état
+$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$
+vers $F$ étiquetée $a{*}$.  L'élimination de l'état $2$ fait
+apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$,
+qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour
+obtenir une transition $(ab{*}a|ba{*}b)$.  Finalement, l'élimination
+de l'état $1$ done l'expression rationnelle
+\[
+a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*}
+\]
+(toujours équivalente aux précédentes).
+\end{corrige}
+
+
 
 %
 %
diff --git a/figs/ex3p2.dot b/figs/ex3p2.dot
new file mode 100644
index 0000000..7b9abdb
--- /dev/null
+++ b/figs/ex3p2.dot
@@ -0,0 +1,14 @@
+digraph ex3p2 {
+	rankdir="LR";
+	node [texmode="math",shape="circle",style="state"];
+	q0 [style="state,initial,final,initial above,accepting below",label="0"];
+	q1 [style="state",label="1"];
+	q2 [style="state",label="2"];
+	edge [texmode="math",lblstyle="auto"];
+	q0 -> q0 [label="a",topath="loop left"];
+	q0 -> q1 [label="b"];
+	q1 -> q0 [label="b"];
+	q1 -> q2 [label="a"];
+	q2 -> q1 [label="a"];
+	q2 -> q2 [label="b",topath="loop right"];
+}