diff options
| -rw-r--r-- | exercices3.tex | 88 | ||||
| -rw-r--r-- | figs/ex3p2.dot | 14 |
2 files changed, 102 insertions, 0 deletions
diff --git a/exercices3.tex b/exercices3.tex index c1a763e..8d5c0ad 100644 --- a/exercices3.tex +++ b/exercices3.tex @@ -266,6 +266,94 @@ description, il est clair que l'automate fait ce qui était demandé. \end{corrige} +% +% +% + +\exercice + +Donner plusieurs (au moins trois) expressions rationnelles +équivalentes dénotant le langage reconnu par l'automate suivant sur +l'alphabet $\Sigma = \{a,b\}$ : + +\begin{center} +%%% begin ex3p2 %%% + +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +%% +\node (q1) at (97bp,20.28bp) [draw,circle,state] {$1$}; + \node (q0) at (18bp,20.28bp) [draw,circle,state,initial,final,initial above,accepting below] {$0$}; + \node (q2) at (176bp,20.28bp) [draw,circle,state] {$2$}; + \draw [->] (q1) ..controls (74.757bp,3.6593bp) and (64.084bp,-1.2803bp) .. (54bp,1.2803bp) .. controls (50.042bp,2.2853bp) and (46.047bp,3.838bp) .. node[auto] {$b$} (q0); + \draw [->] (q2) to[loop right] node[auto] {$b$} (q2); + \draw [->] (q2) ..controls (153.76bp,3.6593bp) and (143.08bp,-1.2803bp) .. (133bp,1.2803bp) .. controls (129.04bp,2.2853bp) and (125.05bp,3.838bp) .. node[auto] {$a$} (q1); + \draw [->] (q0) to[loop left] node[auto] {$a$} (q0); + \draw [->] (q0) ..controls (45.659bp,20.28bp) and (57.817bp,20.28bp) .. node[auto] {$b$} (q1); + \draw [->] (q1) ..controls (124.66bp,20.28bp) and (136.82bp,20.28bp) .. node[auto] {$a$} (q2); +% +\end{tikzpicture} + + +%%% end ex3p2 %%% +\end{center} +(On pourra considérer les ordres suivants d'élimination des états : +$2,1,0$, $1,2,0$ et $0,2,1$.) + +\begin{corrige} +Si on commence par éliminer l'état $2$ (en considérant l'automate +comme un automate à transitions étiquetées par des expressions +rationnelles), l'état $1$ reçoit une transition vers lui-même +étiquetée $ab{*}a$. Si on élimine l'état $1$, l'état $0$ reçoit à la +place une transition vers lui-même étiquetée par $b(ab{*}a){*}b$, +qu'on peut fusionner avec la transition vers lui-même déjà existante +étiquetée par $a$ pour une seule étiquetée par $a|b(ab{*}a){*}b$. +Quitte éventuellement à ajouter un nouvel état initial (conduisant à +$0$ par une transition spontanée) et un nouvel état final (vers lequel +$0$ conduit par une transition spontanée) et à éliminer n'état $0$, on +obtient finalement l'expression rationnelle +\[ +(a|b(ab{*}a){*}b){*} +\] + +Si on commence par éliminer l'état $1$, il apparaît une transition +$0\to 2$ étiquetée $ba$ et une $2\to 0$ étiquetée $ab$ (si on veut +appliquer l'algorithme de façon puremnet mécanique, l'état $1$ n'a pas +de transition vers lui-même, c'est-à-dire qu'on pourrait l'étiqueter +par $\bot$, symbole d'expression rationnelle qui dénote le lagange +vide, et l'expression rationnelle $\bot{*}$ est équivalente +à $\varepsilon$) ; mais il ne faut pas oublier que l'état $2$ reçoit +lui aussi une transition vers lui-même (en passant par $1$) étiquetée +$aa$, qu'on peut fusionner avec la transition vers lui-même déjà +existante étiquetée par $b$ pour obtenir une transition étiquetée +$b|aa$. L'élimination de l'état $2$ fait alors apparaître une +transition de $0$ vers lui-même étiquetée $ba(b|aa){*}ab$, qu'on peut +fusionner avec la transition vers lui-même déjà étiquetée par $a$ pour +une seule étiquetée par $a|b(a(b|aa){*}a){*}b$. On obtient finalement +\[ +(a|b(a(b|aa){*}a){*}b){*} +\] +(en particulier, cette expression est équivalente à celle obtenue +précédemment). + +Si on préfère commencer par éliminer l'état $0$, il faut au préalable +ajouter un nouvel état initial $I$ (conduisant à $0$ par une +transition spontanée) et un nouvel état final $F$ (vers lequel $0$ +conduit par une transition spontanée). L'élimination de l'état $0$ +fait apparaître une transition de $I$ vers $1$ étiquetée $a{*}b$, une +transition $1$ vers $F$ étiquetée $ba{*}$, et une transition de l'état +$1$ vers lui-même étiquetée $ba{*}b$, et enfin une transition de $I$ +vers $F$ étiquetée $a{*}$. L'élimination de l'état $2$ fait +apparaître une transition de $1$ vers lui-même étiquetée $ab{*}a$, +qu'on peut fusionner avec celle déjà existante étiquetée $ba{*}b$ pour +obtenir une transition $(ab{*}a|ba{*}b)$. Finalement, l'élimination +de l'état $1$ done l'expression rationnelle +\[ +a{*}|a{*}b(ab{*}a|ba{*}b){*}ba{*} +\] +(toujours équivalente aux précédentes). +\end{corrige} + + % % diff --git a/figs/ex3p2.dot b/figs/ex3p2.dot new file mode 100644 index 0000000..7b9abdb --- /dev/null +++ b/figs/ex3p2.dot @@ -0,0 +1,14 @@ +digraph ex3p2 { + rankdir="LR"; + node [texmode="math",shape="circle",style="state"]; + q0 [style="state,initial,final,initial above,accepting below",label="0"]; + q1 [style="state",label="1"]; + q2 [style="state",label="2"]; + edge [texmode="math",lblstyle="auto"]; + q0 -> q0 [label="a",topath="loop left"]; + q0 -> q1 [label="b"]; + q1 -> q0 [label="b"]; + q1 -> q2 [label="a"]; + q2 -> q1 [label="a"]; + q2 -> q2 [label="b",topath="loop right"]; +} |