summaryrefslogtreecommitdiffstats
path: root/notes-inf105.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-12-08 15:17:04 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-12-08 15:17:04 (GMT)
commit3fd2bc5bd4fe4f6ae7e7e3b03d70d7458c17ea18 (patch)
treec66110479b7b91cb7c961ffef92a4936125144b7 /notes-inf105.tex
parent0b45c1b9c0ba5a6543951358036a7ff562073e47 (diff)
downloadinf105-3fd2bc5bd4fe4f6ae7e7e3b03d70d7458c17ea18.zip
inf105-3fd2bc5bd4fe4f6ae7e7e3b03d70d7458c17ea18.tar.gz
inf105-3fd2bc5bd4fe4f6ae7e7e3b03d70d7458c17ea18.tar.bz2
Clarify decidability of equivalence of automata or regexps.
Diffstat (limited to 'notes-inf105.tex')
-rw-r--r--notes-inf105.tex60
1 files changed, 52 insertions, 8 deletions
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}
+
%