#Slides — Automates & regex

Regex: union, concaténation, étoile (les trois briques), précédence
Syntaxe pratique: classes, quantificateurs, ancrages, groupes et capture
Sémantique du moteur: plus à gauche, gourmand vs paresseux
AFN vs AFD, ε-transitions, formalisme (Q, Σ, δ, q0, F)
Construction de Thompson (regex → AFN)
Construction par sous-ensembles (AFN → AFD), borne 2^n
Minimisation par partitions (Moore, Hopcroft), unicité de l'AFD minimal
Équivalence regex/automates (théorème de Kleene)
Limites: a^n b^n, imbrication, pourquoi les parseurs à pile
Backtracking des moteurs réels: pire cas exponentiel, défenses, moteurs DFA