summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2020-01-21 12:53:13 +0100
committerDavid A. Madore <david+git@madore.org>2020-01-21 12:53:13 +0100
commitde989e56485767a771bbf81525cc3434b95ae894 (patch)
treeedfdd13729729872d01009b9644b86152dd2932f
parentf669859b9c136935001415911cfbe98427fac801 (diff)
downloadinf105-de989e56485767a771bbf81525cc3434b95ae894.zip
inf105-de989e56485767a771bbf81525cc3434b95ae894.tar.gz
inf105-de989e56485767a771bbf81525cc3434b95ae894.tar.bz2
Write answer to first exercise.
-rw-r--r--controle-20200123.tex40
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}
+
%
%