#Automates & regexCopier le lien

Vous utilisez des regex pour chercher, extraire, valider. Que peuvent-elles vraiment exprimer? Les automates finis donnent la réponse, et un cadre pour concevoir et raisonner: un calcul vu comme une machine à nombre fini d'états. Ce cours relie l'outil quotidien au modèle théorique, sans formalisme gratuit.

Prérequis: bases de la manipulation de chaînes (Python ou équivalent), vocabulaire des ensembles (union, complémentaire, ensemble des parties), premières notions de complexité.

Ce que vous saurez faire: formaliser un automate (AFD, AFN, ε-transitions), le construire depuis une regex et inversement, le déterminiser et le minimiser, et justifier ce qu'une regex ne pourra jamais exprimer.

#De la regex à la machine, et retourCopier le lien

Une expression régulière construit un langage à coups d'union (|), de concaténation et d'étoile de Kleene (*). L'idée clé du chapitre: tout langage décrit par une regex peut être reconnu par un automate fini, et réciproquement. La chaîne de compilation classique:

1. Thompson traduit la regex en AFN à ε-transitions, de taille linéaire en la taille du motif.
2. La construction par sous-ensembles transforme l'AFN en AFD: chaque état du nouvel automate est un ensemble d'états de l'AFN (au plus 2^n).
3. Hopcroft ou Moore minimisent l'AFD: l'automate équivalent le plus petit, unique à renommage près.

Exemple d'identifiant simple (lettre puis lettres/chiffres/underscore):

1[A-Za-z][A-Za-z0-9_]*

Savoir que ce langage est rationnel explique pourquoi trois états suffisent à un lexer pour le reconnaître, et donc pourquoi un lexer est rapide. En revanche, les parenthèses équilibrées en général ne sont pas rationnelles: les reconnaître exige une pile, ce qui motive les automates à pile puis les parseurs.

#Limites utiles à connaîtreCopier le lien

Les langages rationnels s'arrêtent à la structure plate. Trois limites à retenir:

• Comptage non borné: le langage a^n b^n (autant de a que de b) n'est pas rationnel. Un automate fini n'a pas assez de mémoire pour comparer deux moitiés de longueur arbitraire.
• Imbrication arbitraire: parenthèses équilibrées, HTML bien formé, expressions arborescentes. Même raison: la profondeur n'est pas bornée.
• Répétition exacte d'un mot inconnu: « w w » n'est pas rationnel non plus, alors que la rétro-référence \1 des moteurs réels le capture: preuve que ces moteurs dépassent le cadre purement rationnel.

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-atelierCopier le lien

Prenez une regex métier (email simplifié, identifiant, numéro de version). Trois étapes:

1. Dessinez l'automate correspondant à la main, en nommant chaque état par ce qu'il « sait » du préfixe lu (rien d'utile, un a en attente, suffixe ab trouvé...).
2. Appliquez mentalement la minimisation: regroupez les états indiscernables, ceux d'où partent les mêmes comportements futurs.
3. Vérifiez avec des mots tests: le mot vide, un mot minimal accepté, un mot presque valide, un mot long. Les verdicts de l'automate et de la regex doivent coïncider.

Cette gymnastique clarifie les cas limites bien plus sûrement qu'un moteur qui « semble marcher ».