summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-28 21:41:19 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-10-28 21:41:19 (GMT)
commit00f13e46073417e6fe23c841846dea18abec9bdc (patch)
tree50cd26c69600c80e27806ff2911a16e54a232a22
parent185bae82bcf3ddd5f782edabd8a15f5c310e2257 (diff)
downloadinf105-00f13e46073417e6fe23c841846dea18abec9bdc.zip
inf105-00f13e46073417e6fe23c841846dea18abec9bdc.tar.gz
inf105-00f13e46073417e6fe23c841846dea18abec9bdc.tar.bz2
Add example illustrating Glushkov's construction.
-rw-r--r--figs/example8a.dot9
-rw-r--r--figs/example8b.dot11
-rw-r--r--figs/example8c.dot15
-rw-r--r--figs/example8d.dot19
-rw-r--r--notes-inf105.tex106
5 files changed, 159 insertions, 1 deletions
diff --git a/figs/example8a.dot b/figs/example8a.dot
new file mode 100644
index 0000000..b90b713
--- /dev/null
+++ b/figs/example8a.dot
@@ -0,0 +1,9 @@
+digraph example8a {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial,final,accepting below",label="0"];
+ q1 [style="state,final",label="1"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="a"];
+ q1 -> q1 [label="a",topath="loop above"];
+}
diff --git a/figs/example8b.dot b/figs/example8b.dot
new file mode 100644
index 0000000..9730f93
--- /dev/null
+++ b/figs/example8b.dot
@@ -0,0 +1,11 @@
+digraph example8b {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial,final,accepting below",label="0"];
+ q1 [style="state,final",label="1"];
+ q2 [style="state,final",label="2"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="a"];
+ q1 -> q1 [label="a",topath="loop above"];
+ q0 -> q2 [label="b"];
+}
diff --git a/figs/example8c.dot b/figs/example8c.dot
new file mode 100644
index 0000000..d915597
--- /dev/null
+++ b/figs/example8c.dot
@@ -0,0 +1,15 @@
+digraph example8b {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q1 [style="state",label="1"];
+ q2 [style="state",label="2"];
+ q3 [style="state,final",label="3"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="a"];
+ q1 -> q1 [label="a",topath="loop above"];
+ q0 -> q2 [label="b"];
+ q0 -> q3 [label="c"];
+ q1 -> q3 [label="c"];
+ q2 -> q3 [label="c"];
+}
diff --git a/figs/example8d.dot b/figs/example8d.dot
new file mode 100644
index 0000000..761a781
--- /dev/null
+++ b/figs/example8d.dot
@@ -0,0 +1,19 @@
+digraph example8b {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial,final,accepting below",label="0"];
+ q1 [style="state",label="1"];
+ q2 [style="state",label="2"];
+ q3 [style="state,final",label="3"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q1 [label="a"];
+ q1 -> q1 [label="a",topath="loop above"];
+ q0 -> q2 [label="b"];
+ { rank="same"; q1; q2; }
+ q0 -> q3 [label="c",lblstyle="auto,below,near start"];
+ q1 -> q3 [label="c",lblstyle="auto,above"];
+ q2 -> q3 [label="c"];
+ q3 -> q1 [label="a"];
+ q3 -> q2 [label="b"];
+ q3 -> q3 [label="c",topath="loop above"];
+}
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)}