summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-08 15:48:31 +0100
committerDavid A. Madore <david+git@madore.org>2016-12-08 15:48:31 +0100
commita8438fe2758bb3294ae53b777c4396776f10f01e (patch)
treebb87b2db9d875552d7b7c2557a1b4d5ea381eb44 /notes-inf105.tex
parent9c41119f64f2931c92a756f10d64e8228968a55d (diff)
downloadinf105-a8438fe2758bb3294ae53b777c4396776f10f01e.zip
inf105-a8438fe2758bb3294ae53b777c4396776f10f01e.tar.gz
inf105-a8438fe2758bb3294ae53b777c4396776f10f01e.tar.bz2
Remark on elimination of spontaneous transitions and automaton transpose.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex117
1 files changed, 84 insertions, 33 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index df65faa..da90f2d 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1618,28 +1618,29 @@ des sommets accessibles depuis $q$ dans ce graphe).
\begin{prop}\label{removal-of-epsilon-transitions}
Soit $A = (Q,I,F,\delta)$ un εNFA sur un alphabet $\Sigma$. Alors il
-existe un NFA $A' = (Q,I',F',\delta')$ (sur le même alphabet $\Sigma$)
-ayant le même ensemble d'états $Q$ que $A$ et qui soit équivalent
-à $A$ au sens où il reconnaît le même langage $L_{A'} = L_A$. De
-plus, $A'$ se déduit algorithmiquement de $A$.
+existe un NFA $A^\S = (Q,I^\S,F^\S,\delta^\S)$ (sur le même
+alphabet $\Sigma$) ayant le même ensemble d'états $Q$ que $A$ et qui
+soit équivalent à $A$ au sens où il reconnaît le même langage
+$L_{A^\S} = L_A$. De plus, $A^\S$ se déduit algorithmiquement de $A$.
\end{prop}
\begin{proof}
-On pose $I' = I$ (mêmes états initiaux). L'idée est maintenant de
-faire une transition $(q,x,q') \in \delta'$ à chaque fois qu'on peut
+On pose $I^\S = I$ (mêmes états initiaux). L'idée est maintenant de
+faire une transition $(q,x,q') \in \delta^\S$ à chaque fois qu'on peut
atteindre $q'$ à partir de $q$ dans $A$ par une suite quelconque de
ε-transitions suivie d'une unique transition étiquetée par $x$,
autrement dit, $(q,\varepsilon,q^\sharp) \in \delta^*$ (c'est-à-dire
$q^\sharp \in C(q)$) et $(q^\sharp,x,q') \in \delta$.
-On définit donc $\delta' \subseteq Q\times\Sigma\times Q'$ par
-$(q,x,q') \in \delta'$ lorsqu'il existe $q^\sharp \in C(q)$ tel que
+On définit donc $\delta^\S \subseteq Q\times\Sigma\times Q$ par
+$(q,x,q') \in \delta^\S$ lorsqu'il existe $q^\sharp \in C(q)$ tel que
$(q^\sharp,x,q') \in \delta$ : autrement dit, pour créer les
-transitions $q\to q'$ dans $A'$, on parcourt tous les $q^\sharp \in
-C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$ dans $A'$
-lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée par ce $x$
-dans $A$. De même, on définit $F' \subseteq Q$ comme l'ensemble des
-$q\in Q$ tels que $C(q) \cap F \neq \varnothing$, c'est-à-dire, qu'on
-peut atteindre un état final par une succession de ε-transitions.
+transitions $q\to q'$ dans $A^\S$, on parcourt tous les $q^\sharp \in
+C(q)$, et on crée une transition $q\to q'$ étiquetée par $x$
+dans $A^\S$ lorsqu'il existe une transition $q^\sharp\to q'$ étiquetée
+par ce $x$ dans $A$. De même, on définit $F^\S \subseteq Q$ comme
+l'ensemble des $q\in Q$ tels que $C(q) \cap F \neq \varnothing$,
+c'est-à-dire, qu'on peut atteindre un état final par une succession de
+ε-transitions.
Si on a un chemin $q_0 \to q_1 \to \cdots \to q_n$ dans $A$ menant
d'un état initial $q_0 \in I$ à un état final $q_n \in F$ et
@@ -1651,22 +1652,23 @@ posons $j_0 = 0$. Alors on passe de $q_{j_{i-1}}$ à $q_{j_i}$ par une
succession de ε-transitions (de $q_{j_{i-1}}$ à $q_{(j_i)-1}$) suivie
par une unique transition non spontanée : on a $q_{(j_i)-1} \in
C(q_{j_{i-1}})$ et $(q_{(j_i)-1},t_{j_i},q_{j_i}) \in \delta$,
-autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta'$ ; et comme
+autrement dit $(q_{j_{i-1}},t_{j_i},q_{j_i}) \in \delta^\S$ ; et comme
le mot $w = t_1\cdots t_n$ s'écrit aussi $t_{j_1}\cdots t_{j_m}$, on a
-un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F'$ (puisque
+un chemin reliant $q_{j_0} = q_0 \in I$ à $q_{j_m} \in F^\S$ (puisque
$q_n \in C(q_{j_m}) \cap F$). Le mot $w$ supposé accepté par $A$ est
-donc accepté par $A'$. La réciproque est analogue.
+donc accepté par $A^\S$. La réciproque est analogue.
\end{proof}
-\thingy On dit que le NFA $A'$ est obtenu en \textbf{supprimant les
+\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{supprimant les
ε-transitions} dans le εNFA $A$ lorsqu'il est obtenu par la
procédure décrite dans la démonstration de cette proposition, et en
-supprimant tous les états non-initiaux de $A'$ auxquels n'aboutissent
-dans $A$ que des ε-transitions (ces états sont devenus inaccessibles
-dans $A'$). Algorithmiquement, il s'agit donc, pour chaque état $q\in
-Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$ de $q$, de créer
-une transition $q\to q'$ étiquetée par $x$ dans $A'$ pour chaque
-transition $q^\sharp\to q'$ étiquetée par $x$ dans $A$.
+supprimant tous les états non-initiaux de $A^\S$ auxquels
+n'aboutissent dans $A$ que des ε-transitions (ces états sont devenus
+inaccessibles dans $A^\S$). Algorithmiquement, il s'agit donc, pour
+chaque état $q\in Q$ et chaque $q^\sharp$ dans la ε-femerture $C(q)$
+de $q$, de créer une transition $q\to q'$ étiquetée par $x$
+dans $A^\S$ pour chaque transition $q^\sharp\to q'$ étiquetée par $x$
+dans $A$.
\thingy À titre d'exemple, supprimons les ε-transitions du εNFA $A$
présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
@@ -1700,6 +1702,45 @@ l'automate suivant :
incomplet, mais ce n'est pas un phénomène général : en général il faut
s'attendre à obtenir un NFA.)
+{\footnotesize
+
+\thingy\textbf{Remarque :} La manière dont on a éliminé les
+ε-transitions ci-dessus consiste à remplacer \emph{une succession de
+ ε-transitions suivie d'une unique transition étiquetée $x$} par une
+transition étiquetée $x$ (et de même, on modifie les états finaux,
+mais pas les états initiaux). Il existait un moyen « dual »
+d'éliminer les ε-transitions, à savoir remplacer \emph{une unique
+ transition étiquetée $x$ suivie d'une succession de ε-transitions}
+par une transition étiquetée $x$ (et de même, on modifie les états
+initiaux, mais pas les états finaux). Autrement dit, la construction
+$A \mapsto A^\S$ décrite en \ref{removal-of-epsilon-transitions}
+définit $(q,x,q') \in \delta^\S$ lorsqu'il existe $q^\sharp \in C(q)$
+tel que $(q^\sharp,x,q') \in \delta$, et $I^\S=I$ et $F^\S$ comme
+l'ensemble des états $q$ tels que $C(q) \cap F \neq \varnothing$ ; la
+construction « duale » $A \mapsto A^\P$ consiste à poser $(q,x,q') \in
+\delta^\P$ lorsqu'il existe $q^{\flat\prime} \in C(q)$ tel que
+$(q,x,q^{\flat\prime}) \in \delta$, et $F^\P=F$ et $I^\P$ comme la
+réunion des $C(q)$ pour tout $q\in I$.
+
+Ces deux manières d'éliminer les ε-transitions donnent des NFA
+équivalents. En fait, on peut passer de l'une à l'autre en utilisant
+la définition de l'automate transposé $A^{\mathsf{R}}$ présentée
+en \ref{nfa-mirror} plus bas (et qui consiste simplement à inverser le
+sens de toutes les flèches de l'automate) : si on inverse les flèches,
+qu'on élimine les ε-transitions à la manière décrite
+en \ref{removal-of-epsilon-transitions}, et qu'on inverse de nouveau
+les flèches, on obtient l'élimination « duale », autrement dit, $A^\P
+= ((A^{\mathsf{R}})^\S)^{\mathsf{R}}$.
+
+L'une ou l'autre manière d'éliminer les ε-transitions était possible,
+mais il vaut mieux ne pas les mélanger. C'est pour cette raison qu'on
+a fait un choix en \ref{removal-of-epsilon-transitions} ; la présente
+remarque a principalement pour objectif d'expliquer la raison d'une
+perte de symétrie (notamment entre états initiaux et finaux) dans ce
+choix.
+
+\par}
+
\section{Langages reconnaissables et langages rationnels}
@@ -1798,17 +1839,27 @@ Si $L$ est un langage reconnaissable sur un alphabet $\Sigma$, alors
le langage miroir (cf. \ref{definition-mirror-language})
$L^{\mathsf{R}}$ de $L$ est reconnaissable ; de plus, un NFA ou εNFA
reconnaissant l'un se déduit algorithmiquement d'un NFA ou εNFA
-reconnaissant l'autre.
+reconnaissant l'autre : il s'agit simplement d'inverser le sens de
+toutes les flèches (y compris celles qui marquent les états initiaux
+et finaux).
\end{prop}
+
+L'automate ainsi construit en inversant toutes les flèches d'un
+automate $A$ (la définition précise est donnée dans la démonstration
+qui suit) et qui reconnaît le langage miroir de celui reconnu par $A$
+peut s'appeller automate \textbf{transposé} $A^{\mathsf{R}}$ de $A$.
+
\begin{proof}
Par hypothèse, il existe un εNFA ou un NFA $A = (Q,I,F,\delta)$ tel
-que $L = L_A$. Considérons l'automate $A'$ de même type défini par
-l'ensemble d'états $Q' = Q$ et inversant toutes les flèches de $A$,
-c'est-à-dire $I' = F$ et $F' = I$ et $(q,t,q') \in \delta'$ si et
-seulement si $(q',t,q) \in \delta$. Un chemin existe dans $A'$ si et
-seulement si le même chemin inversé existe dans $A$, ce qui montre
-qu'un mot appartient à $L_{A'}$ si et seulement si son miroir
-appartient à $L_A$.
+que $L = L_A$. Considérons l'automate $A^{\mathsf{R}}$ de même type
+défini par l'ensemble d'états $Q^{\mathsf{R}} = Q$ et inversant toutes
+les flèches de $A$, c'est-à-dire $I^{\mathsf{R}} = F$ et
+$F^{\mathsf{R}} = I$ et $(q,t,q') \in \delta^{\mathsf{R}}$ si et
+seulement si $(q^{\mathsf{R}},t,q) \in \delta$. Un chemin existe dans
+$A^{\mathsf{R}}$ si et seulement si le même chemin inversé existe
+dans $A$, ce qui montre qu'un mot appartient à $L_{A^{\mathsf{R}}}$ si
+et seulement si son miroir appartient à $L_A$. On a donc bien
+$L_{A^{\mathsf{R}}}=L^{\mathsf{R}}$, langage miroir de $L$.
\end{proof}
\thingy Alors que les constructions du complémentaire et de
@@ -1817,7 +1868,7 @@ langage miroir s'effectue naturellement sur les NFA. (On peut, bien
sûr, considérer un DFA comme un NFA particulier, et effectuer dessus
l'opération d'inversion des flèches qu'on vient de décrire, mais en
général on n'obtiendra pas un DFA, seulement un NFA ; les NFA dont
-l'inversion des flèches est déterministe — c'est-à-dire tels que, pour
+l'automate transposé est déterministe — c'est-à-dire tels que, pour
chaque état $q$ et chaque lettre $x$, il existe une unique arête
aboutissant à $q$ et étiquetée par $x$ — sont parfois dits
« co-déterministes ».)