Automates finis

Une machine qui répond oui ou non

Du langage au programme

Une expression rationnelle décrit un langage. Mais la question pratique est souvent : ce mot-ci est-il dans le langage ? Il faut un accepteur : un programme qui lit un mot et répond oui ou non.

On pourrait écrire un programme à la main pour chaque expression. On va plutôt produire mécaniquement les plans d'une machine très simple, capable de répondre pour n'importe quelle expression :

Cette machine lit les lettres du mot une à une, de gauche à droite, sans jamais revenir en arrière. À chaque instant, elle est dans une situation parmi un nombre fini de situations possibles, qu'on appelle des états. Chaque lettre lue la fait changer d'état. Quand le mot est fini, l'état où elle se trouve donne la réponse.

Un premier exemple

Sur $\Sigma = \{a, b\}$, reconnaissons le langage $\{a\}$ qui contient un seul mot : $a$. Il y a trois situations :

• 0 : on n'a encore rien lu. Si le mot s'arrête là, c'est non ($\varepsilon$ n'est pas $a$).
• 1 : on a lu exactement $a$. Si le mot s'arrête là, c'est oui.
• 2 : on a lu autre chose. Quoi qu'il arrive ensuite, ce sera non.

On dessine chaque état par un cercle et chaque changement d'état par une flèche étiquetée par la lettre lue. La flèche entrante désigne l'état de départ, dit initial. Le double cercle désigne les états où la réponse est oui, dits finals (le pluriel « finals » est l'usage en théorie des langages).

Pour le mot $ab$ : on part de 0, on lit $a$ et on va en 1, on lit $b$ et on va en 2. Le mot est fini, 2 n'est pas final : $ab$ est refusé.

Ne garder que l'utile

Sur les six transitions de cet automate, une seule mène à un oui. L'état 2 ne sert qu'à dire « c'est perdu ». Si on convient qu'une machine bloquée, qui ne trouve pas de flèche pour la lettre lue, refuse le mot, on peut le supprimer :

Cet automate reconnaît le même langage, et il est plus lisible. Les deux dessins ont chacun leur intérêt, et on va apprendre à passer de l'un à l'autre.

Définitions

Automate fini

On donne une seule définition, la plus générale, et on la restreindra ensuite.

On appelle taille de l'automate, notée $|A|$, son nombre d'états.

Rien n'interdit plusieurs états initiaux, plusieurs transitions de même origine et même lettre, ou des transitions spontanées. C'est la forme la plus libre, et on la nomme d'après ce qu'elle permet :

Chemins et langage reconnu

Le chemin de longueur zéro, qui reste dans l'état $q_0$, a pour étiquette $\varepsilon$. Donc $\varepsilon \in L(A)$ dès qu'un état est à la fois initial et final.

Deux automates qui reconnaissent le même langage sont dits équivalents.

Trois exemples

Un DFA. Les mots qui ont un nombre pair de $a$. Deux situations suffisent : « pair jusqu'ici » (P) et « impair jusqu'ici » (I). Lire $a$ change la parité, lire $b$ ne la change pas.

Un NFA. Les mots dont l'avant-dernière lettre est un $a$, c'est-à-dire $(a + b)^* a (a + b)$.

De l'état 0, en lisant $a$, on peut rester en 0 ou aller en 1 : il y a un choix. L'automate « devine » que ce $a$ est l'avant-dernière lettre. Le mot est accepté s'il existe une façon de deviner juste. Pour $aab$, le chemin $0 \xrightarrow{a} 0 \xrightarrow{a} 1 \xrightarrow{b} 2$ est réussi : le mot est accepté. D'autres chemins de même étiquette échouent ($0 \xrightarrow{a} 1 \xrightarrow{a} 2$, puis blocage sur $b$), mais peu importe : il en suffit d'un.

Un $\varepsilon$-NFA. Le langage $a^*b^*c^*$ : des $a$, puis des $b$, puis des $c$, chacun en nombre quelconque.

On boucle sur les $a$ en 0, puis on passe sans rien lire en 1 pour boucler sur les $b$, puis en 2 pour les $c$. Le mot $ac$ est accepté par le chemin $0 \xrightarrow{a} 0 \xrightarrow{\varepsilon} 1 \xrightarrow{\varepsilon} 2 \xrightarrow{c} 2$.

Nondéterministe ne veut pas dire « non déterministe »

Un DFA est un cas particulier de NFA, qui est un cas particulier d'$\varepsilon$-NFA :

L'automate de l'avant-dernière lettre, lui, est un NFA qui n'est pas déterministe. On apprendra au chapitre 4 à le transformer en DFA équivalent.

Exécuter un automate

Un DFA : une seule exécution

Dans un DFA, il n'y a jamais de choix : pour chaque état et chaque lettre, au plus une transition. On note alors $\delta(p, a) = q$ la transition $p \xrightarrow{a} q$, et $\delta$ est une fonction partielle de $Q \times \Sigma$ dans $Q$. L'exécution se programme en quelques lignes :

def accepte_dfa(automate, mot):
    etat = automate.initial
    for lettre in mot:
        if (etat, lettre) not in automate.delta:
            return False              # bloqué : refusé
        etat = automate.delta[(etat, lettre)]
    return etat in automate.finals

Le temps d'exécution est proportionnel à la longueur du mot, et la mémoire utilisée est une variable : l'état courant. C'est pour cela qu'on veut des DFA.

Un NFA : toutes les exécutions à la fois

Dans un NFA, il peut y avoir plusieurs chemins pour un même mot. Essayer tous les chemins un par un coûte, dans le pire cas, un temps exponentiel. Mieux vaut suivre l'ensemble des états où l'on peut se trouver :

def accepte_nfa(automate, mot):
    courants = set(automate.initiaux)
    for lettre in mot:
        courants = {q for p in courants
                      for q in automate.successeurs(p, lettre)}
    return any(q in automate.finals for q in courants)

Pour l'automate de l'avant-dernière lettre et le mot $aab$ : $\{0\} \xrightarrow{a} \{0, 1\} \xrightarrow{a} \{0, 1, 2\} \xrightarrow{b} \{0, 2\}$. L'ensemble final contient 2 : le mot est accepté.

Chaque étape coûte au plus $|Q|^2$ opérations : c'est polynomial, mais la « mémoire » n'est plus un état, c'est un ensemble d'états. Retenez cette idée : c'est exactement celle de la déterminisation, au chapitre suivant.

Le vocabulaire des états

Accessible, co-accessible, utile

Ici, l'état 3 n'est pas accessible : aucun chemin n'y mène depuis 0. L'état 4 n'est pas co-accessible : on y entre, mais on n'en sort jamais vers 2. Les états 0, 1 et 2 sont utiles.

Émonder un automate, c'est supprimer ses états inutiles et les transitions qui les touchent. Cela ne change pas le langage reconnu, puisque ces états ne sont sur aucun chemin réussi. L'algorithme est un parcours de graphe : on marque les états accessibles par un parcours depuis $I$, les états co-accessibles par un parcours depuis $F$ en remontant les flèches, et on garde l'intersection.

Complet

Un DFA complet a exactement une transition par état et par lettre ; sa fonction $\delta$ est alors totale. Pour compléter un automate, on ajoute un état puits, non final, qui boucle sur toutes les lettres, et on y envoie toutes les transitions manquantes.

Les deux automates reconnaissent $ab^*$. Compléter ne change pas le langage : le puits n'est pas co-accessible, donc aucun chemin réussi n'y passe. Émonder et compléter sont deux opérations inverses : émonder l'automate complet retire le puits.

Et maintenant ?

On a deux façons de décrire des langages : les expressions rationnelles, qui définissent $\mathrm{Rat}$, et les automates finis, qui définissent $\mathrm{Rec}$. Le but des deux chapitres suivants est de montrer que ce sont les mêmes langages, et de savoir passer de l'une à l'autre :

• chapitre 4 : d'une expression à un automate, puis à un DFA. Donc $\mathrm{Rat} \subseteq \mathrm{Rec}$ ;
• chapitre 5 : d'un automate à une expression. Donc $\mathrm{Rec} \subseteq \mathrm{Rat}$.