From 00f13e46073417e6fe23c841846dea18abec9bdc Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 28 Oct 2017 23:41:19 +0200
Subject: Add example illustrating Glushkov's construction.

---
 notes-inf105.tex | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 105 insertions(+), 1 deletion(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 78191a4..0ac44aa 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2651,7 +2651,111 @@ sont étiquetées par $x$.
 Ces observations sont utiles pour détecter des erreurs lors de la
 construction de l'automate.
 
-\textcolor{red}{TODO: Développer, et donner des exemples.}
+\thingy À titre d'exemple pour illustrer la construction de Glushkov,
+construsions l'automate qu'elle associe à l'expression rationnelle
+$((a{*}|b)c){*}$ sur l'alphabet $\Sigma = \{a,b,c\}$.  On doit obtenir
+un automate ayant $4$ états.
+
+L'automate de Glushkov de $a{*}$ est le suivant, obtenu en appliquant
+la construction de \ref{nfa-star} à l'automate trivial pour le
+langage $\{a\}$ (donné en \ref{trivial-standard-automata}) :
+
+\begin{center}
+%%% begin example8a %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,18bp) [draw,circle,state,final] {$1$};
+  \node (q0) at (18bp,18bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \draw [->] (q0) ..controls (45.659bp,18bp) and (57.817bp,18bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+%
+\end{tikzpicture}
+
+%%% end example8a %%%
+\end{center}
+
+On en déduit au moyen de \ref{nfa-union} l'automate suivant
+pour $a{*}|b$ :
+
+\begin{center}
+%%% begin example8b %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,72bp) [draw,circle,state,final] {$1$};
+  \node (q0) at (18bp,41bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q2) at (97bp,18bp) [draw,circle,state,final] {$2$};
+  \draw [->] (q0) ..controls (45.279bp,51.58bp) and (58.943bp,57.081bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q0) ..controls (40.761bp,31.564bp) and (47.615bp,28.946bp)  .. (54bp,27bp) .. controls (58.828bp,25.529bp) and (64.04bp,24.206bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+%
+\end{tikzpicture}
+
+%%% end example8b %%%
+\end{center}
+
+On en déduit au moyen de \ref{nfa-concatenation} l'automate suivant
+pour $(a{*}|b)c$ :
+
+\begin{center}
+%%% begin example8c %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q1) at (97bp,99.608bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,45.608bp) [draw,circle,state,initial] {$0$};
+  \node (q3) at (176bp,45.608bp) [draw,circle,state,final] {$3$};
+  \node (q2) at (97bp,45.608bp) [draw,circle,state] {$2$};
+  \draw [->] (q0) ..controls (42.871bp,23.135bp) and (60.567bp,9.4181bp)  .. (79bp,3.6077bp) .. controls (94.26bp,-1.2026bp) and (99.74bp,-1.2026bp)  .. (115bp,3.6077bp) .. controls (129.69bp,8.2379bp) and (143.91bp,17.889bp)  .. node[auto] {$c$} (q3);
+  \draw [->] (q2) ..controls (124.66bp,45.608bp) and (136.82bp,45.608bp)  .. node[auto] {$c$} (q3);
+  \draw [->] (q0) ..controls (45.659bp,45.608bp) and (57.817bp,45.608bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q0) ..controls (44.341bp,63.379bp) and (60.249bp,74.535bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q1) ..controls (123.34bp,81.836bp) and (139.25bp,70.68bp)  .. node[auto] {$c$} (q3);
+%
+\end{tikzpicture}
+
+%%% end example8c %%%
+\end{center}
+
+Et enfin, de nouveau par \ref{nfa-star} l'automate suivant
+pour $((a{*}|b)c)*$ :
+
+\begin{center}
+%%% begin example8d %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\begin{scope}
+  \pgfsetstrokecolor{black}
+  \definecolor{strokecol}{rgb}{1.0,1.0,1.0};
+  \pgfsetstrokecolor{strokecol}
+  \definecolor{fillcol}{rgb}{1.0,1.0,1.0};
+  \pgfsetfillcolor{fillcol}
+\end{scope}
+  \node (q1) at (97bp,101.45bp) [draw,circle,state] {$1$};
+  \node (q0) at (18bp,45.453bp) [draw,circle,state,initial,final,accepting below] {$0$};
+  \node (q3) at (176bp,63.453bp) [draw,circle,state,final] {$3$};
+  \node (q2) at (97bp,45.453bp) [draw,circle,state] {$2$};
+  \draw [->] (q0) ..controls (49.576bp,16.777bp) and (84.747bp,-9.0778bp)  .. (115bp,3.4533bp) .. controls (133.15bp,10.97bp) and (148.67bp,26.932bp)  .. node[auto,below,near start] {$c$} (q3);
+  \draw [->] (q2) ..controls (124.6bp,51.671bp) and (137.34bp,54.651bp)  .. node[auto] {$c$} (q3);
+  \draw [->] (q0) ..controls (45.659bp,45.453bp) and (57.817bp,45.453bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q3) ..controls (148.91bp,76.331bp) and (134.76bp,83.311bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q1) to[loop above] node[auto] {$a$} (q1);
+  \draw [->] (q3) ..controls (156.78bp,44.679bp) and (148.66bp,38.493bp)  .. (140bp,35.453bp) .. controls (134.61bp,33.562bp) and (128.7bp,33.684bp)  .. node[auto] {$b$} (q2);
+  \draw [->] (q3) to[loop above] node[auto] {$c$} (q3);
+  \draw [->] (q0) ..controls (44.52bp,64.013bp) and (60.758bp,75.823bp)  .. node[auto] {$a$} (q1);
+  \draw [->] (q1) ..controls (120.07bp,117.96bp) and (130.95bp,122.37bp)  .. (140bp,117.45bp) .. controls (151.16bp,111.39bp) and (159.31bp,100.06bp)  .. node[auto,above] {$c$} (q3);
+%
+\end{tikzpicture}
+
+%%% end example8d %%%
+\end{center}
+
+Toutes les transitions aboutissant à l'état $1$ sont étiquetées $a$,
+toutes celles aboutissant à l'état $2$ sont étiquetées $b$, et toutes
+celles aboutissant à $3$ sont étiquetées $c$.
 
 
 \subsection{Automates à transitions étiquetées par des expressions rationnelles (=RNFA)}
-- 
cgit v1.2.3

