diff options
| -rw-r--r-- | notes-inf105.tex | 24 |
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 |