#Automates & regex
Vous utilisez des regex pour chercher/valider. Que peuvent‑elles vraiment exprimer ? Les automates donnent la réponse et un cadre pour concevoir et raisonner. Ce cours fait le pont entre “outil pratique” et “fondement théorique” sans formalisme gratuit.
#De la regex à la machine, et retour
Une regex construit un langage à coups d’union (|), de concaténation et d’étoile de Kleene (*). L’idée clé: tout langage régulier reconnu par une regex peut l’être par un automate fini (AFN ou AFD). L’algorithme de Thompson traduit la regex en AFN; la construction par sous‑ensembles transforme l’AFN en AFD; Hopcroft minimise l’AFD pour accélérer l’exécution.
Exemple: des identifiants “simples” (lettre puis lettres/chiffres/underscore)
1[A-Za-z][A-Za-z0-9_]*Savoir que c’est régulier explique pourquoi un simple automate suffit à un lexer; la parenthèse équilibrée générale, en revanche, ne l’est pas (on sort du régulier), d’où les parseurs à pile.
#Limites utiles à connaître
Les regex ne gèrent pas les structures imbriquées arbitraires. Si vous vous battez pour “valider du HTML” en une seule regex, le modèle vous dit pourquoi ça casse, et vous oriente vers un parseur.
#Mini‑atelier
Prenez une regex métier (email simplifié, identifiant, numéro de version). Dessinez l’automate correspondant à la main, puis appliquez mentalement l’algorithme de minimisation (regrouper des états indiscernables). Cette gymnastique clarifie les cas limites.