diff options
Diffstat (limited to 'exercices1.tex')
| -rw-r--r-- | exercices1.tex | 68 |
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} |