summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-08 14:59:09 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-08 14:59:09 (GMT)
commit963ca7a06dab06129c6a2afe06ddf9aa41e0c79f (patch)
tree933493e6359b529f8ecca29b4063db4043820835 /notes-inf105.tex
parenta8438fe2758bb3294ae53b777c4396776f10f01e (diff)
downloadinf105-963ca7a06dab06129c6a2afe06ddf9aa41e0c79f.zip
inf105-963ca7a06dab06129c6a2afe06ddf9aa41e0c79f.tar.gz
inf105-963ca7a06dab06129c6a2afe06ddf9aa41e0c79f.tar.bz2
A clarification on elimination of states.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex57
1 files changed, 33 insertions, 24 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index da90f2d..91d63c7 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -2145,19 +2145,20 @@ rationnelle en question). On va construire montrer que $A$ est
équivalent à une expression rationnelle.
Remarquons tout d'abord qu'on peut supposer que $A$ a un unique état
-initial $q_0$ sans aucune transition qui y aboutit (si ce n'est pas le
-cas, il suffit de créer un nouvel état $q_0$, d'en faire le seul état
-initial, et de le munir de transitions spontanées — c'est-à-dire
-étiquetées par $\underline{\varepsilon}$ — vers tous les états
-précédemment initiaux). De même (symétriquement), on peut supposer
-que $A$ a un unique état final $q_\infty$ sans aucune transition qui
-en part. On fera l'hypothèse que $A$ a ces propriétés, et on
-s'arrangera pour les préserver dans ce qui suit.
-
-Soient maintenant $q$ un état de $A$ qui n'est ni l'état initial ni
-l'état final. On va montrer qu'on peut \emph{éliminer} $q$,
-c'est-à-dire, quitte à ajouter des transitions, remplacer $A$ par un
-automate équivalent $A'$ qui n'a pas cet état. Pour cela, soient
+initial $q_0$, qui ne soit pas final, et qui n'ait aucune transition
+qui y aboutisse (si ce n'est pas le cas, il suffit de créer un nouvel
+état $q_0$, d'en faire le seul état initial, et de le munir de
+transitions spontanées — c'est-à-dire étiquetées par
+$\underline{\varepsilon}$ — vers tous les états précédemment
+initiaux). De même (symétriquement), on peut supposer que $A$ a un
+unique état final $q_\infty$, qui ne soit pas initial, et sans aucune
+transition qui en part. On fera l'hypothèse que $A$ a ces propriétés,
+et on s'arrangera pour les préserver dans ce qui suit.
+
+Soient maintenant $q$ un état de $A$ qui n'est ni l'état initial $q_0$
+ni l'état final $q_\infty$. On va montrer qu'on peut \emph{éliminer}
+$q$, c'est-à-dire, quitte à ajouter des transitions, remplacer $A$ par
+un automate équivalent $A'$ qui n'a pas cet état. Pour cela, soient
$q_1,q_2$ deux états quelconques de $A$, autres que $q$ mais
possiblement égaux entre eux, où $q_1$ peut être l'état initial (mais
pas l'état final) et $q_2$ peut être l'état final (mais pas l'état
@@ -2201,10 +2202,7 @@ l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
En supprimant (dans n'importe quel ordre) tous les états autres que
$q_0$ et $q_\infty$, on aboutit ainsi à un automate ayant une unique
transition $(q_0,r,q_\infty)$, qui est donc essentiellement
-l'expression rationnelle $r$ (si $q_\infty$ et $q_0$ ne sont pas
-distincts, on peut ajouter un nouvel état initial, un nouvel état
-final, et éliminer l'état commun :
-cf. l'exemple \ref{example-of-state-elimination}).
+l'expression rationnelle $r$.
\end{proof}
\thingy La procédure qu'on a décrite dans la démonstration de cette
@@ -2250,6 +2248,12 @@ du nombre $0$, ce qui est logique) :
%%% end example6 %%%
\end{center}
+On commence par ajouter un état initial $q_0$ et un état
+final $q_\infty$, avec des ε-transitions $q_0 \to 0$ et $0\to
+q_\infty$. Pour gagner de la place, nous ne figurerons pas ces deux
+états sur les dessins qui suivent, mais il faut s'imaginer qu'ils sont
+toujours là.
+
L'élimination de l'état $2$ conduit à l'automate suivant :
\begin{center}
@@ -2269,13 +2273,18 @@ L'élimination de l'état $2$ conduit à l'automate suivant :
%%% end example6b %%%
\end{center}
-Et l'élimination de l'état $1$ conduit alors à l'automate ayant un
-unique état $0$, à la fois initial et final, avec une transition vers
-lui-même étiquetée $0|1(01{*}0){*}1$. Tel quel, cet automate n'est
-pas sous la forme d'une expression rationnelle parce que l'état
-initial et l'état final ne sont pas distincts, mais on peut bien sûr
-les séparer, et on obtient l'expression rationnelle
-$(0|1(01{*}0){*}1){*}$.
+\noindent (Répétons qu'on n'a pas figuré l'état initial $q_0$ ni
+l'état final $q_\infty$ : les flèches vers et depuis l'état $0$
+doivent se comprendre comme des ε-transitions $q_0\to 0$ et $0\to
+q_\infty$.)
+
+L'élimination de l'état $1$ conduit alors à l'automate ayant un unique
+état $0$, avec une transition vers lui-même étiquetée
+$0|1(01{*}0){*}1$. Enfin, en éliminant l'état $0$, il ne reste qu'une
+transition de l'état initial vers l'état final, étiquetée par
+$(0|1(01{*}0){*}1){*}$ : le langage reconnu par l'automate de départ
+est donc celui dénoté par l'expression
+rationnelle $(0|1(01{*}0){*}1){*}$.
On pouvait aussi choisir d'éliminer l'état $1$ en premier, ce qui
conduit à l'automate suivant :