summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-10-29 19:34:18 +0100
committerDavid A. Madore <david+git@madore.org>2017-10-29 19:34:18 +0100
commit16c784b986cf31911f339abed45a9465b62f3807 (patch)
tree96df5470ded1133bece7d431ce45042fc3c4cc5c
parent536f9a4d8db29242e59c84b62f4fb605c0907388 (diff)
downloadinf105-16c784b986cf31911f339abed45a9465b62f3807.tar.gz
inf105-16c784b986cf31911f339abed45a9465b62f3807.tar.bz2
inf105-16c784b986cf31911f339abed45a9465b62f3807.zip
Clarifications on how to decide equivalence of automata.
-rw-r--r--notes-inf105.tex24
1 files changed, 23 insertions, 1 deletions
diff --git a/notes-inf105.tex b/notes-inf105.tex
index 5949a8b..fd86890 100644
--- a/notes-inf105.tex
+++ b/notes-inf105.tex
@@ -3554,6 +3554,28 @@ suffit donc de prendre $i=0$ pour avoir une contradiction.
\subsection{L'automate minimal, et la minimisation}
+\thingy On sait maintenant convertir une expression rationnelle en un
+automate équivalent, et réciproquement convertir un automate en
+expression rationnelle équivalente. Il reste un problème auquel nous
+n'avons pas donné de réponse : comment savoir si deux automates
+\emph{donnés} ou deux expressions rationnelles données (ou un de
+chaque) sont équivalents ?
+
+Pour cela, on va introduire un DFA particulier, \emph{canonique},
+associé à un langage rationnel, qu'on pourra calculer
+algorithmiquement, et qui sera véritablement associé au langage,
+c'est-à-dire que deux descriptions équivalentes du même langage
+donneront exactement le \emph{même} automate canonique ; par
+conséquent, pour tester l'égalité de deux langages, quelle que soit
+leur description, il suffira de calculer leurs automates canoniques et
+de les comparer. En fait, cet automate canonique est simplement le
+DFA ayant le plus petit nombre d'états reconnaissant le langage en
+question ; ce qui est remarquable, et qui n'est pas du tout évident
+\textit{a priori}, c'est qu'il est effectivement canonique
+(c'est-à-dire qu'il n'existe qu'un seul DFA ayant un nombre minimal
+d'états reconnaissant le langage) et qu'on peut le calculer
+algorithmiquement.
+
\begin{thm}[Myhill-Nerode]\label{myhill-nerode}\index{Myhill-Nerode (théorème de)}
Soit $L$ un langage. Pour $w\in \Sigma^*$, notons $w^{-1} L := \{t
\in \Sigma^* : wt \in L\}$ (autrement dit, l'ensemble des mots qu'on
@@ -3896,7 +3918,7 @@ l'automate est, en fait, déjà minimal.
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).
+reconnaître/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