I. Expressions régulières (rappels)

On se donne un alphabet .

On appelle langage régulier un langage dénoté par une expression régulière.

II. Automates

a) Automates déterministes

Par exemple, sur , l'automate suivant reconnaît les mots qui contiennent un nombre pair de : l'état 0 signifie "on a lu un nombre pair de ", l'état 1 "un nombre impair". L'état initial est indiqué par une flèche entrante, et les états acceptants par un double cercle.

Modifiez le mot pour voir l'automate le lire, lettre par lettre :

b) Automates non déterministes

Les différences avec les automates déterministes sont indiquées en rouge.

Par exemple, l'automate non déterministe suivant reconnaît les mots qui se terminent par : depuis l'état 0, en lisant un , on peut rester en 0 ou "parier" que ce est l'avant-dernière lettre, en allant en 1. Pendant la lecture, on suit l'ensemble des états où l'on peut se trouver :

c) Transitions instantanées (ε-transitions)

On s'autorise maintenant des transitions étiquetées par (le mot vide) : ce sont des transitions instantanées, que l'automate peut emprunter sans lire de lettre.

Pendant la lecture d'un mot, dès qu'on est dans un état, on est donc aussi, "gratuitement", dans tous les états qu'on peut atteindre depuis lui en suivant uniquement des -transitions. Un mot est accepté s'il existe un chemin qui lit ses lettres (en intercalant autant de -transitions qu'on veut) et qui arrive dans un état acceptant.

Par exemple, l'automate suivant reconnaît : on lit des dans l'état 0, puis on "passe" instantanément dans l'état 1 pour lire des . Dès le début de la lecture, les états courants sont 0 et 1.

Essayez avec aba : après le , l'automate est dans l'état 1, qui ne lit plus de : le mot est refusé.

Les -transitions ne permettent pas de reconnaître plus de langages : on peut toujours les supprimer. L'idée : si on peut aller de à par des -transitions, on recopie sur les transitions qui partent de , et devient acceptant si l'est. Elles sont en revanche très pratiques pour assembler des automates, comme on va le voir.

d) Propriétés

Par exemple, pour l'automate non déterministe précédent (mots se terminant par ), on obtient l'automate des parties suivant, en ne gardant que les parties accessibles depuis l'état initial :

Ses états courants sont exactement les ensembles d'états courants de l'automate non déterministe.

Avec des -transitions. La construction est la même, à une différence près : chaque ensemble d'états est remplacé par sa clôture, c'est-à-dire qu'on lui ajoute tous les états accessibles par des -transitions.

• L'état initial est la clôture de l'ensemble des états initiaux.
• Depuis un ensemble , en lisant , on va dans la clôture de .

Par exemple, l'automate suivant reconnaît :

• La clôture de l'état initial est : c'est l'état initial de l'automate des parties.
• Depuis : en lisant , on atteint , dont la clôture est ; en lisant , on atteint , de clôture .
• Depuis : mène à , et à , de clôture .
• Depuis : mène à , et il n'y a pas de transition par .
• Les trois ensembles contiennent l'état final 2 : ils sont tous acceptants.

On obtient un automate déterministe, sans -transition : l'état correspond à "on lit encore les premiers ", à "on lit les ", et à "on lit les derniers " (un est alors interdit).

On le montre en construisant les automates correspondants. Prenons comme exemples, sur , l'automate des mots qui contiennent un nombre pair de , et l'automate des mots qui se terminent par :

Union. On place les deux automates côte à côte : les états initiaux sont ceux de et de , les états acceptants aussi. Un mot est accepté s'il est accepté par l'un des deux (l'automate obtenu est non déterministe).

Intersection. On fait avancer les deux automates "en même temps" : c'est l'automate produit, dont les états sont les couples , avec . Un couple est acceptant si ses deux composantes le sont. Ici, on reconnaît les mots avec un nombre pair de qui se terminent par :

Complémentaire et différence. Si est déterministe et complet (une transition pour chaque état et chaque lettre), il suffit d'échanger états acceptants et non acceptants pour reconnaître . Puis .

Concaténation. Prenons maintenant l'automate qui reconnaît le seul mot :

Pour reconnaître , on place les deux automates l'un après l'autre, et on les relie par des -transitions : de chaque état acceptant de vers chaque état initial de . Les états initiaux sont ceux de , les états acceptants ceux de . Une fois un mot de lu, on "saute" instantanément au début de :

Les -transitions servent à isoler les deux automates : on ne fusionne aucun état, donc aucun chemin ne peut "revenir" de dans , ni mélanger les transitions des deux automates.

Étoile. Prenons l'automate qui reconnaît :

Pour reconnaître , il faut accepter le mot vide, et pouvoir "recommencer" un nouveau mot de à la fin de chaque mot. Une idée naïve serait de rendre l'état initial 0 acceptant, et d'ajouter une -transition de 1 vers 0... mais alors le mot serait accepté (on reste dans l'état 0, devenu acceptant), alors que ! Le problème : l'état 0 a une boucle, qu'on emprunte sans avoir fini un mot.

On ajoute donc un nouvel état , isolé du reste : il est initial et acceptant (pour le mot vide), relié par une -transition à l'ancien état initial ; et chaque état acceptant est relié à par une -transition, pour recommencer :

Essayez le mot a : il est bien refusé.

III. Lien entre les deux

a) Passage automate → expression régulière

On étiquette les transitions par des expressions régulières plutôt que par des lettres, et on supprime les sommets un à un.

Par exemple, sur l'automate des mots qui se terminent par (partie II.b), après l'étape 1 :

• On supprime 1 : le chemin devient .
• On supprime 2 : le chemin devient .
• On supprime 0, qui a une boucle : le chemin devient .

On retrouve bien l'expression régulière .

b) Passage expression régulière → automate

Prenons par exemple l'expression . On construit l'automate de Glushkov :

1. On linéarise l'expression régulière, c'est-à-dire qu'on numérote chaque lettre. On note le nouvel alphabet :
2. On trouve l'ensemble des préfixes et suffixes de 1 lettre, et des facteurs de 2 lettres, possibles :
   • premiers : ;
   • derniers : ;
   • facteurs : .
3. On construit l'automate correspondant au langage linéarisé , où :
   • ;
   • ;
   • n'est pas définie sinon.
4. On supprime la numérotation dans les transitions du graphe pour avoir l'automate final.

Automate de l'étape 3 :

Automate de l'étape 4, sur lequel vous pouvez lire des mots :

À noter qu'on obtient un automate non déterministe, qui contient autant d'états que de lettres dans l'expression régulière source, plus un (l'état initial ).

IV. Le lemme de l'étoile

Tous les langages ne sont pas rationnels. Pour le montrer, on utilise le fait qu'un automate a un nombre fini d'états : il ne peut retenir qu'une quantité limitée d'information.

Application : le langage n'est pas rationnel.

Intuitivement, pour reconnaître , il faudrait "compter" les , sans limite : un automate fini ne le peut pas.

Exercices