Automates finis et expressions régulières : Guide complet

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 :

1. L est fini.
2. Il existe une expression régulière r telle que L(r) = L.
3. 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.