From 6d822f738fa288008bca407dc10d4ed3e1012863 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 30 Nov 2016 20:57:59 +0100 Subject: The Myhill-Nerode theorem. --- notes-inf105.tex | 87 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 87 insertions(+) diff --git a/notes-inf105.tex b/notes-inf105.tex index 7b31806..077fb5d 100644 --- a/notes-inf105.tex +++ b/notes-inf105.tex @@ -2367,6 +2367,93 @@ suffit donc de prendre $i=0$ pour avoir une contradiction. \end{proof} +\subsection{L'automate canonique, et la minimisation} + +\begin{thm}[Myhill-Nerode] +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 +peut concaténer à $w$ pour obtenir un mot de $L$). Considérons la +relation d'équivalence $\equiv$ sur $\Sigma^*$ définie par $u \equiv +v$ si et seulement si $u^{-1}L = v^{-1}L$ (ce qui signifie, si on +préfère, que $\forall t\in \Sigma^* ((ut\in L) \liff (vt \in L))$). + +Alors : +\begin{itemize} +\item le langage $L$ est rationnel si et seulement si la relation + d'équivalence $\equiv$ possède un nombre \emph{fini} $k$ de classes + d'équivalence, +\item lorsque c'est le cas, il existe un DFA ayant $k$ états qui + reconnaît $L$, il est unique à renommage des + états\footnote{C'est-à-dire, si on préfère ce terme, isomorphisme + d'automates.} près, et il n'existe pas de DFA ayant $