#Automates & regex
Bases des langages réguliers: expressions régulières, AFN/AFD et équivalences.
#Objectifs
- Comprendre les langages réguliers et leur pouvoir d’expression.
- Convertir regex ↔ AFN ↔ AFD, minimiser un AFD.
- Utiliser les fermetures (∪, ·, *) pour construire des langages.
#Notions clés
- Regex: union
|, concaténation, étoile de Kleene*, optionnel?, plus+. - AFN/AFD: états, transitions, état initial, états acceptants; ε‑transitions (AFN).
- Algorithmes: Thompson (regex→AFN), subset construction (AFN→AFD), Hopcroft (minimisation).
#Exemple
Langage des identifiants simples: lettre suivie de lettres/chiffres/underscore.
bg-[rgba(var(--code-inline-bg),0.5)] text-[rgb(var(--fg))] px-1 roundedbg-[rgba(var(--code-inline-bg),0.5)] text-[rgb(var(--fg))] px-1 rounded
1regex: [A-Za-z][A-Za-z0-9_]*#Applications
- Recherche/validation (find/replace), lexers de compilateurs, filtrage de logs.