From 3fd2bc5bd4fe4f6ae7e7e3b03d70d7458c17ea18 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 8 Dec 2016 16:17:04 +0100
Subject: Clarify decidability of equivalence of automata or regexps.

---
 notes-inf105.tex | 60 ++++++++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 52 insertions(+), 8 deletions(-)

(limited to 'notes-inf105.tex')

diff --git a/notes-inf105.tex b/notes-inf105.tex
index 356afd6..57a9267 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -1659,7 +1659,7 @@ $q_n \in C(q_{j_m}) \cap F$).  Le mot $w$ supposé accepté par $A$ est
 donc accepté par $A^\S$.  La réciproque est analogue.
 \end{proof}
 
-\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{supprimant les
+\thingy On dit que le NFA $A^\S$ est obtenu en \textbf{éliminant 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^\S$ auxquels
@@ -1670,7 +1670,7 @@ 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$
+\thingy À titre d'exemple, éliminons les ε-transitions du εNFA $A$
 présenté en \ref{discussion-example5} : comme $C(0) = \{0,1,2\}$, on
 fait partir de $0$ toutes les transitions partant d'un des états
 $0,1,2$ et étiquetées par une lettre, et de même, comme $C(1) =
@@ -1986,11 +1986,12 @@ initial de $A$ en question et suivi d'une ε-transition de l'état final
 de $A$ en question vers $q_0$.  On a donc bien $L_{A'} = L^*$.
 \end{proof}
 
-\begin{prop}\label{rational-languages-are-recognizable}
+\begin{cor}\label{rational-languages-are-recognizable}
 Tout langage rationnel est reconnaissable ; de plus, un εNFA le
 reconnaissant se déduit algorithmiquement d'une expression rationnelle
-le dénotant.
-\end{prop}
+le dénotant.  (Et en particulier, il est possible de décider
+algorithmiquement si un mot vérifie une expression rationnelle.)
+\end{cor}
 \begin{proof}
 Cela résulte de façon évidente de la définition des langages
 rationnels (cf. §\ref{subsection-rational-languages}), du fait que les
@@ -1998,6 +1999,15 @@ langages $\varnothing$, $\{\varepsilon\}$ et $\{x\}$ (pour
 chaque $x\in\Sigma$) sont reconnaissables par automates finis, et des
 propositions \ref{nfa-union}, \ref{nfa-concatenation}
 et \ref{nfa-star}.
+
+Pour décider si un mot vérifie une expression rationnelle, on peut
+commencer par transformer cette expression rationnelle en εNFA (i.e.,
+construire un εNFA reconnaissant le langage qu'elle dénote) comme on
+vient de l'expliquer, et transformer ensuite cet automate en DFA
+quitte à éliminer les ε-transitions
+(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser
+(cf. \ref{determinization-of-nfa}), après quoi il est facile de tester
+si l'automate accepte le mot.
 \end{proof}
 
 \textcolor{red}{TODO: Standardiser la construction des automates.  Par
@@ -2165,7 +2175,7 @@ pas l'état final) et $q_2$ peut être l'état final (mais pas l'état
 initial).  On a vu en \ref{give-rnfa-single-transitions} qu'on pouvait
 supposer qu'il existait une unique transition $(q_1,r_{12},q_2)$ et de
 même $(q_1,r_1,q)$ et $(q,r_2,q_2)$ et $(q,s,q)$ (transition de $q$
-vers lui-même).  En même temps qu'on supprime $q$, on met dans $A'$ la
+vers lui-même).  En même temps qu'on élimine $q$, on met dans $A'$ la
 transition $(r_{12}|r_1(s){*}r_2)$ entre $q_1$ et $q_2$.
 Symboliquement :
 
@@ -2193,13 +2203,13 @@ $q_1\not\in\{q,q_\infty\}$ et $q_2\not\in\{q,q_0\}$ : pour chaque
 telle paire, on remplace l'étiquette de la transition $r_{12}$ entre
 eux par $(r_{12}|r_1(s){*}r_2)$.  Ceci ne change pas le fonctionnement
 de l'automate, car tout chemin dans $A$ peut être remplacé par un
-chemin dans $A'$ en supprimant simplement les $q$ (si on considère
+chemin dans $A'$ en effaçant simplement les $q$ (si on considère
 $q_1$ et $q_2$ les états avant un bloc de de $q$ dans le chemin, on
 voit que le chemin $q_1 \to q \to q \to \cdots \to q \to q_2$ peut se
 transformer en $q_1 \to q_2$ en consommant un mot qui vérifie
 l'expression rationnelle $(r_{12}|r_1(s){*}r_2)$).
 
-En supprimant (dans n'importe quel ordre) tous les états autres que
+En éliminant (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$.
@@ -2789,6 +2799,40 @@ En revanche, si on change l'automate pour rendre l'état $4$ non-final
 aboutit sur la partition triviale en six états, c'est-à-dire que
 l'automate est, en fait, déjà minimal.
 
+\begin{cor}
+On peut décider algorithmiquement si deux automates finis (de
+n'importe quelle sorte), ou deux expressions rationnelles, ou un
+automate et une expression rationnelle, sont équivalents (au sens de
+dénoter le même langage).
+\end{cor}
+\begin{proof}
+D'après ce qu'on a déjà vu, et quitte à transformer une expression
+rationnelle en εNFA (cf. \ref{rational-languages-are-recognizable}),
+et quitte à éliminer les ε-transitions
+(cf. \ref{removal-of-epsilon-transitions}) et à déterminiser
+(cf. \ref{determinization-of-nfa}), on peut construire
+algorithmiquement un DFA reconnaissant le même langage que chacune des
+deux données.  La question devient donc de savoir si deux DFA
+reconnaissent le même langage.  Or d'après \ref{dfa-minimization}, on
+sait transformer un DFA en DFA minimal reconnaissant le même langage,
+et d'après \ref{myhill-nerode} on sait que ce DFA est unique à
+renumérotation près des états.  On est donc ramené au problème
+suivant : donnés deux DFA $A$ et $A'$ (complets et sans états
+inaccessibles), trouver s'ils sont le même à renumérotation près
+(i.e., s'ils sont isomorphes).
+
+La correspondance entre états de $A$ et de $A'$ peut se construire
+état par état : on fait correspondre l'état initial de $A$ à celui
+de $A'$, puis pour chaque état $q$ de $A$ mis en correspondance avec
+un état $q'$ de $A'$, on fait correspondre chacun des états
+$\delta(q,x)$ avec chacun des états $\delta'(q',x)$ où $x$ parcourt
+les lettres de l'alphabet.  Si on aboutit ainsi à une contradiction
+(deux états de l'un des automates veulent être mis en correspondance
+avec le même état de l'autre), on renvoie un échec ; sinon, tous les
+états de $A$ et ceux de $A'$ seront mis en correspondance bijective,
+et les langages reconnus sont les mêmes.
+\end{proof}
+
 
 
 %
-- 
cgit v1.2.3

