summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex106
1 files changed, 105 insertions, 1 deletions
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)}