From b144fa0fb8f49c6a808976a907a91e6c8ab2d53a Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 30 Jan 2017 11:43:56 +0100
Subject: An exercise on Kleene's algorithm.

---
 exercices3.tex | 88 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 88 insertions(+)

(limited to 'exercices3.tex')

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}
+
+
 
 %
 %
-- 
cgit v1.2.3

