diff options
| -rw-r--r-- | figs/example8a.dot | 9 | ||||
| -rw-r--r-- | figs/example8b.dot | 11 | ||||
| -rw-r--r-- | figs/example8c.dot | 15 | ||||
| -rw-r--r-- | figs/example8d.dot | 19 | ||||
| -rw-r--r-- | notes-inf105.tex | 106 |
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)} |