#Ressources — Automates & regexCopier le lien

Pourquoi ces liens: pratiquer des regex solides, comprendre leurs limites, et relier leur usage aux automates. Comment s'en servir: valider un motif sur des entrées adverses, vérifier la complexité, et basculer vers un parseur dès que le comptage ou l'imbrication entre en jeu.

#RéférencesCopier le lien

• Introduction aux automates finis et langages rationnels (supports universitaires libres, cours L3/informatique théorique).
• Regex101 (tester, décomposer et visualiser l'exécution d'une regex): https://regex101.com/
• Documentation du module re de Python (sémantique du moteur, drapeaux, avertissements sur les motifs dangereux).

#ExercicesCopier le lien

• Déterminiser puis minimiser de petits AFN (3 à 5 états) sur {a, b}: mots finissant par ab, mots contenant ab, nombre pair de a.
• Traduire à la main une regex courte en AFN de Thompson, puis déterminiser, puis comparer avec le résultat direct.
• Écrire des regex avec ancrages, classes et groupes nommés, et bâtir le tableau de cas tests avant d'exécuter.

#Annales corrigéesCopier le lien

La page Annales corrigées rassemble onze exercices tirés de sujets d'examen réels, avec corrections détaillées:

• OFI (L2, semestre 3, Enrico Formenti, UCA) — définitions inductives et ambiguïté, expression régulière pour un cahier des charges, dénombrement d'un langage, conjugaison et mots de Lyndon, caractérisation et récurrence de Fibonacci.
• Automates & Langages (L3, semestre 5, Université Nice Sophia Antipolis) — grammaire régulière vers AFN, langage hors contexte et automate à pile, forme normale de Chomsky, algorithme CYK, lemme de l'étoile (rationnel et algébrique), automate fini et machine de Turing, clôture et dénombrabilité.

Un avertissement utile pour la préparation: les dix-huit sujets d'OFI archivés localement ne testent pas la déterminisation ni la minimisation d'automates. Leur dominante est le dénombrement, les récurrences et la logique propositionnelle. Si votre objectif est OFI, ce sont les automates du programme de L3 qui fournissent les exercices de la seconde partie de la page.

#Bonnes pratiquesCopier le lien

• Éviter le backtracking explosif (quantificateurs imbriqués comme (a+)+); préférer des motifs spécifiques et ancrés.
• Mesurer et fixer des timeouts côté serveur pour les validations regex sur entrée publique.
• Choisir un moteur adapté: DFA garanti linéaire (RE2, regex de Rust) quand les références arrière ne servent pas.
• Ne jamais tenter de valider du HTML ou des parenthèses imbriquées en une seule regex: passer au parseur.