summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-12-07 12:21:07 +0100
committerDavid A. Madore <david+git@madore.org>2017-12-07 12:21:07 +0100
commitfea3f1a462dc875532282776afd6022211999ac1 (patch)
tree6ed9713e01e0bf456075b5e911a84e550afc0721
parent10559224d661e323fb4fe10957583339a76ed98a (diff)
downloadinf105-fea3f1a462dc875532282776afd6022211999ac1.tar.gz
inf105-fea3f1a462dc875532282776afd6022211999ac1.tar.bz2
inf105-fea3f1a462dc875532282776afd6022211999ac1.zip
Add a further question to an exercise.
-rw-r--r--exercices1.tex68
-rw-r--r--figs/ex1p2a2.dot11
-rw-r--r--figs/ex1p2a3.dot10
-rw-r--r--figs/ex1p2a4.dot14
4 files changed, 103 insertions, 0 deletions
diff --git a/exercices1.tex b/exercices1.tex
index 95d09de..11f7d69 100644
--- a/exercices1.tex
+++ b/exercices1.tex
@@ -282,6 +282,10 @@ quatre états). Décrire brièvement la signification de ces quatre
états, de façon à vérifier qu'il accepte le même langage que décrit
en (0).
+(3) Éliminer les états de l'automate d'origine de façon à obtenir une
+expression rationnelle dénotant le langage reconnu par le langage
+décrit en (0).
+
\begin{corrige}
(0) L'automate proposé accepte les mots ayant soit deux $a$
consécutifs (en passant par le chemin $0\to 1\to 2\to 3\to 7$) soit
@@ -445,6 +449,70 @@ un $b$, le $A$ signifie qu'il a lu deux $a$ consécutifs ou bien deux
$b$ consécutifs. Sur cette description, il est clair que l'automate
accepte les mots contenant deux $a$ consécutifs ou bien deux $b$
consécutifs.
+
+(3) L'élimination des états $1$ à $6$ peut se faire dans un ordre
+quelconque et conduit à l'automate (à transitions étiquetées par des
+expressions rationnelles) suivant :
+\begin{center}
+%%% begin ex1p2a2 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,20.549bp) [draw,circle,state,initial] {$0$};
+ \node (q7) at (104bp,20.549bp) [draw,circle,state,final] {$7$};
+ \draw [->] (q0) ..controls (47.743bp,20.549bp) and (62.773bp,20.549bp) .. node[auto] {$aa$} (q7);
+ \draw [->] (q0) ..controls (42.511bp,4.2138bp) and (55.796bp,-1.5495bp) .. (68bp,1.5495bp) .. controls (71.958bp,2.5545bp) and (75.953bp,4.1071bp) .. node[auto,below] {$bb$} (q7);
+ \draw [->] (q0) to[loop below] node[auto] {$a,b$} (q0);
+ \draw [->] (q7) to[loop below] node[auto] {$a,b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a2 %%%
+\end{center}
+
+Il y a plusieurs flèches entre les mêmes états : quitte à les
+remplacer par des disjonctions, on obtient :
+\begin{center}
+%%% begin ex1p2a3 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (q0) at (18bp,18bp) [draw,circle,state,initial] {$0$};
+ \node (q7) at (119bp,18bp) [draw,circle,state,final] {$7$};
+ \draw [->] (q0) ..controls (51.292bp,18bp) and (73.384bp,18bp) .. node[auto] {$aa|bb$} (q7);
+ \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+ \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a3 %%%
+\end{center}
+
+Enfin, on doit éliminer les états $0$ et $7$ eux-mêmes : pour cela, on
+ajoute un nouvel état initial qui ne soit la cible d'aucune flèche et
+un nouvel état final d'où ne part aucune flèche,
+\begin{center}
+%%% begin ex1p2a4 %%%
+
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+%%
+\node (qi) at (18bp,18bp) [draw,circle,state,initial] {$\phantom{0}$};
+ \node (q0) at (97bp,18bp) [draw,circle,state] {$0$};
+ \node (q7) at (198bp,18bp) [draw,circle,state] {$7$};
+ \node (qf) at (277bp,18bp) [draw,circle,state,final] {$\phantom{7}$};
+ \draw [->] (qi) ..controls (45.659bp,18bp) and (57.817bp,18bp) .. node[auto] {$\varepsilon$} (q0);
+ \draw [->] (q7) ..controls (225.66bp,18bp) and (237.82bp,18bp) .. node[auto] {$\varepsilon$} (qf);
+ \draw [->] (q0) ..controls (130.29bp,18bp) and (152.38bp,18bp) .. node[auto] {$aa|bb$} (q7);
+ \draw [->] (q0) to[loop below] node[auto] {$a|b$} (q0);
+ \draw [->] (q7) to[loop below] node[auto] {$a|b$} (q7);
+%
+\end{tikzpicture}
+
+%%% end ex1p2a4 %%%
+\end{center}
+
+Et l'élimination des états $0$ et $7$ dans un ordre quelconque conduit
+finalement à l'expression rationnelle $(a|b){*}(aa|bb)(a|b){*}$.
\end{corrige}
diff --git a/figs/ex1p2a2.dot b/figs/ex1p2a2.dot
new file mode 100644
index 0000000..1cd6e46
--- /dev/null
+++ b/figs/ex1p2a2.dot
@@ -0,0 +1,11 @@
+digraph ex1p2a2 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q7 [style="state,final",label="7"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q0 [label="a,b",topath="loop below"];
+ q0 -> q7 [label="aa"];
+ q0 -> q7 [label="bb",lblstyle="auto,below"];
+ q7 -> q7 [label="a,b",topath="loop below"];
+}
diff --git a/figs/ex1p2a3.dot b/figs/ex1p2a3.dot
new file mode 100644
index 0000000..5c03856
--- /dev/null
+++ b/figs/ex1p2a3.dot
@@ -0,0 +1,10 @@
+digraph ex1p2a3 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ q0 [style="state,initial",label="0"];
+ q7 [style="state,final",label="7"];
+ edge [texmode="math",lblstyle="auto"];
+ q0 -> q0 [label="a|b",topath="loop below"];
+ q0 -> q7 [label="aa|bb"];
+ q7 -> q7 [label="a|b",topath="loop below"];
+}
diff --git a/figs/ex1p2a4.dot b/figs/ex1p2a4.dot
new file mode 100644
index 0000000..56ee8b6
--- /dev/null
+++ b/figs/ex1p2a4.dot
@@ -0,0 +1,14 @@
+digraph ex1p2a4 {
+ rankdir="LR";
+ node [texmode="math",shape="circle",style="state"];
+ qi [style="state,initial",label="0",texlbl="$\phantom{0}$"];
+ q0 [style="state",label="0"];
+ q7 [style="state",label="7"];
+ qf [style="state,final",label="7",texlbl="$\phantom{7}$"];
+ edge [texmode="math",lblstyle="auto"];
+ qi -> q0 [label="e",texlbl="$\varepsilon$"];
+ q0 -> q0 [label="a|b",topath="loop below"];
+ q0 -> q7 [label="aa|bb"];
+ q7 -> q7 [label="a|b",topath="loop below"];
+ q7 -> qf [label="e",texlbl="$\varepsilon$"];
+}