summaryrefslogtreecommitdiffstats
path: root/exercices1.tex
diff options
context:
space:
mode:
Diffstat (limited to 'exercices1.tex')
-rw-r--r--exercices1.tex68
1 files changed, 68 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}