Dans le précédent paragraphe, nous avons à chaque automate, associé un langage : c'est le langage reconnu par cet automate.
Nous nous intéressons à la réciproque. Dans notre contexte, on se limitera au langage rationnel permettant de travailler avec les REGEX.
Définition
On dira qu'un automate \( \A\) est un automate rationnel si \( L(\A)\in LR(\Sigma_\A)\) .
Théorème [Kleene]
Un langage est rationnel si et seulement si il existe un automate rationnel qui le reconnait.
Démonstration
Admise.
Considérons par exemple l'ADEF \( \A\) suivant
\[
\xymatrix{
\ar[r]&A\ar[r]^a\ar@(lu, ru)[]^b&B\ar[r]^a\ar@(lu, ru)[]^b&C\ar[r]\ar@/^1pc/[ll]^a\ar@(lu, ru)[]^b\ar[r]&
}
\]
Nous avons montré, à l'aide du lemme d'Arden, que la REGEX qui reconnait ce langage est \( \left((b^*a)^3\right)^*(b^*a)^2b^*\) .
A présent la problématique est inverse. On dispose d'une REGEX \( r\) qui, par l'intermédiaire de l'application \( L\) (langage associé), donne un langage relationnel \( L(r)\) . D'après le théorème de Kleene, nous devrions trouver un automate (rationnel) permettant de reconnaitre ce langage.
Nous allons prendre chacune des conditions construisant l'application
langage associé et déterminer des algorithmes permettant de construire un automate reconnaissant le langage.
