Automates finis et expressions régulières : résumé du cours
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 pi. Cela s'applique à tous les états et pour tous les symboles.
Automates finis et expressions régulières
ER
...