diff options
| -rw-r--r-- | controle-20200123.tex | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/controle-20200123.tex b/controle-20200123.tex index 58e82d7..7042a81 100644 --- a/controle-20200123.tex +++ b/controle-20200123.tex @@ -151,6 +151,46 @@ Soit $\mathscr{A}$ l'automate suivant sur l'alphabet $\Sigma := d'élimination des états, déterminer une expression rationnelle dénotant le langage qu'il reconnaît. +\begin{corrige} +L'élimination de l'état $1$ conduit à l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (S2) at (70bp,0bp) [draw,circle,state] {$2$}; +\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (S0) -- node[auto,below] {$\varepsilon|a$} (S2); +\draw [->] (S2) to[loop below] node[auto] {$c|ba$} (S2); +\draw [->] (S2) -- node[auto,below] {$\varepsilon|b$} (S3); +\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$\varepsilon$} (80bp,35bp) to[out=0,in=90] (S3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-.5ex\noindent — et l'élimination de +l'état $2$ conduit alors à l'expression rationnelle suivante : +$\varepsilon\;|\;(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$ (il se +trouve que le premier terme est inutile et que cette expression +rationnelle est équivalente à +simplement $(\varepsilon|a)\,(c|ba){*}\,(\varepsilon|b)$, mais la +méthode d'élimination conduit à ce qui a été dit). + +Si on élimine d'abord l'état $2$, on aboutit à l'automate suivant : +\begin{center} +\begin{tikzpicture}[>=latex,line join=bevel,automaton] +\node (S0) at (0bp,0bp) [draw,circle,state,initial] {$0$}; +\node (S1) at (70bp,0bp) [draw,circle,state] {$1$}; +\node (S3) at (140bp,0bp) [draw,circle,state,final] {$3$}; +\draw [->] (S0) -- node[auto,below] {$\varepsilon|c{*}b$} (S1); +\draw [->] (S1) to[loop below] node[auto] {$ac{*}b$} (S1); +\draw [->] (S1) -- node[auto,below] {$\varepsilon|ac{*}$} (S3); +\draw [->] (S0) to[out=90,in=180] (60bp,35bp) -- node[auto] {$c{*}$} (80bp,35bp) to[out=0,in=90] (S3); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip\vskip-.5ex\noindent — et à l'expression +rationnelle suivante : +$c{*}\;|\;(\varepsilon|c{*}b)\,(ac{*}b){*}\,(\varepsilon|ac{*})$. +Elle est, bien sûr, équivalente à celle obtenue avec l'autre ordre +d'élimination. +\end{corrige} + % % |