Automates finis et expressions régulières : résumé du cours

Résumé

Ce document présente les notions essentielles sur les automates finis et les expressions régulières : transitions, conversion d'un automate avec ε-transitions, passage des expressions régulières aux automates et réciproquement. Il expose aussi le théorème de Kleene, le lemme d'Arden, les propriétés des langages réguliers, le lemme de pompage et la construction du complément d'un langage régulier.

Points clés

Pour un état q et un symbole a, δ(q, a) est l'ensemble des états accessibles directement depuis q par une transition marquée a.
Pour supprimer les ε-transitions, on calcule la ε-fermeture de chaque état puis δ'(q, a) = ε-fermeture(δ(ε-fermeture(q), a)).
Théorème de Kleene : un langage est régulier si et seulement s'il est accepté par un automate fini.
Lemme d'Arden : la solution unique de X = AX ∪ B est X = A*B.
Un langage régulier est fermé par union, concaténation et étoile de Kleene.
Le lemme de pompage sert à montrer qu'un langage n'est pas régulier, en trouvant un contre-exemple, et ne prouve pas qu'un langage est régulier.
Pour obtenir le complément d'un langage régulier, on construit l'AFD correspondant et on inverse les états finaux et non finaux.

Testez-vous

Définition et transitions des automates

Pour un état q et un symbole a, la transition est définie par : δ(q, a) = {p | p est un état accessible par une transition marquée a}. δ(q, a) représente l'ensemble des états accessibles directement via la transition marquée a.

Conversion d'un automate avec ε-transitions

Pour transformer un automate avec ε-transitions en un automate sans ε-transitions :

1) Calculer la ε-fermeture pour tous les états.
2) Dessiner l'automate sans ε-transitions.
3) Assurer les transitions : δ'(q, a) = ε-fermeture(δ(ε-fermeture(q), a)).

Tracez des flèches avec le symbole a de q vers tous les états p_i. Cela s'applique à tous les états et pour tous les symboles.

Automates finis et expressions régulières

ER vers AF :

Cas de base : Définition pour les symboles de base et ε.
Cas récursif : Construction basée sur l'union, la concaténation et l'étoile de Kleene.

AF vers ER :

Tout langage régulier est accepté par un automate fini. Cet ensemble est fermé par rapport à l'union, la concaténation et l'étoile de Kleene.

Théorème de Kleene : Tout langage régulier est accepté par un automate fini, et réciproquement.

Lemme d'Arden : Pour une équation de la forme X = AX ∪ B, la solution unique est X = A*B.

Propriétés des langages réguliers

Un langage L est régulier si :

L est fini.
Il existe une expression régulière r telle que L(r) = L.
Il existe un automate fini M tel que L(M) = L.

Le lemme de pompage

Le lemme de pompage permet de prouver qu'un langage n'est pas régulier. Si L est un langage régulier infini, il existe une constante k telle que toute chaîne w (avec |w| ≥ k) peut être décomposée en w = uvx, avec :

|v| ≥ 1
|uv| ≤ k
Pour tout i ≥ 0, uvⁱx ∈ L.

Note : Le lemme de pompage ne prouve pas qu'un langage est régulier, il sert à trouver un contre-exemple.

Complément d'un langage régulier

Pour trouver le complément d'un langage régulier, construisez l'AFD correspondant et inversez les états finaux et non finaux.

Questions fréquentes

Comment supprimer les ε-transitions d'un automate ?

On calcule d'abord la ε-fermeture de tous les états, puis on dessine l'automate sans ε-transitions en appliquant δ'(q, a) = ε-fermeture(δ(ε-fermeture(q), a)).

Que dit le lemme d'Arden ?

Pour une équation de la forme X = AX ∪ B, la solution unique est X = A*B.

Comment trouver le complément d'un langage régulier ?

Il faut construire l'AFD correspondant puis inverser les états finaux et non finaux.