From 963ca7a06dab06129c6a2afe06ddf9aa41e0c79f Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 8 Dec 2016 15:59:09 +0100 Subject: A clarification on elimination of states. --- notes-inf105.tex | 57 ++++++++++++++++++++++++++++++++------------------------ 1 file 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 : -- cgit v1.2.3