Automate fini non-déterministe
On a l’habitude de dessiner un automate fini non-déterministe, en figurant les états par des cercles, en indiquant l’état initial par une flèche entrante, les états acceptants par un double cercle ou une flèche sortante, et la transition de l’état q à l’état q’ en lisant la lettre α par une flèche allant de q vers q’ et étiquetée par α.
Un automate fini non-déterministe A est un triplet (Vt, Q, T) où
- Vt est le vocabulaire de l’automate ;
- Q est l’ensemble fini des états de l’automate ;
- T : Q × Vt → Q, est une application partielle appelée fonction de transition de l’automate.
Notons qu’un automate déterministe est un cas particulier d’automate non-déterministe qui associe à tout élément de Q × Vt une partie de Q possédant zéro ou un élément (exactement un si c’est un automate complet). On pourra dire d’un automate déterministe qu’il est incomplet s’il peut se bloquer, c’est-à-dire s’il existe un état q et une lettre a tels que T(q, a) = ∅. S’il est complet, nous avons la propriété suivante :
Soit A = (Vt, Q, T) un automate fini non-déterministe complet. Alors, pour tout mot u ∈ V∗t et tout état q ∈ Q, il existe un (pas toujours unique) état q’ ∈ Q tel que q(u)→Aq’.
Le non-déterministe a toutefois une conséquence essentielle : il peut y avoir plusieurs dérivations issus de l’état initial i qui lisent un mot w donné, dont certains peuvent se bloquer et d’autres pas, et dans ce dernier cas certains peuvent terminer en état acceptant et d’autres pas. L’acceptation a lieu s’il existe au moins un calcul réussi. Si tous les calculs échouent, il n’y aura pas d’autre moyen de le savoir que de les explorer tous avant de savoir que le mot w n’est pas reconnu. La bonne notion n’est donc pas celle de calcul, mais d’arbre de calcul associé à un mot lu par l’automate :
Étant donné un automate fini non-déterministe A, l’arbre de dérivations de racine q ∈ Q engendré par la lecture du mot u est un arbre doublement étiqueté défini par récurrence sur u :
Si u = ε, alors l’arbre est réduit à sa racine q ;
Si u = av, la racine q possède des transitions sortantes étiquetées par a ∈ Vt vers différents arbres de calcul engendrés par la lecture de v et dont les racines sont étiquetées par les états de T(q, a).
Un arbre de dérivation se construit comme dans le cas d’un automate déterministe. Dans le cas d’un automate fini non-déterministe, il n’est pas linéaire et peut présenter diverses branches qui donneront des dérivations diverses menant ou non à la reconnaissance du mot.
Un mot u est reconnu par un automate non déterministe A ssi l’une des feuilles de son arbre de calcul est étiquetée par un état acceptant.
Non-déterminisme et mots reconnus
On considère l’automate fini non-déterministe A = ({a, b}, {1, 2, 3}, ∆, {1}, {1}) suivant :
Le mot baabab est-il accepté par l’automate A ?
Aucune feuille ne correspond à un état final, notons que toutes les feuilles finissent dans le puits.
Comme l’automate déterministe, il est possible de construire les mots reconnus par l’automate en regardant les lignes d’entrée et colonnes de sortie. Les mots de longueurs n sont alors construit en élevant la matrice de transition à la puissance n.
