Automate fini
Automate fini (en anglais finite automaton ; DFA pour la variante déterministe) : machine composée d'un nombre fini d'états et de transitions, qui lit son entrée symbole par symbole en changeant d'état, et accepte ou refuse selon l'état atteint. Ken Thompson a montré en 1968 qu'une expression régulière au sens strict se traduit en automate ; l'article de Russ Cox Regular Expression Matching Can Be Simple And Fast (2007) en a rappelé l'intérêt face aux moteurs à retour arrière.
L'avantage est une garantie : le temps de recherche est proportionnel à la longueur du texte, quel que soit le motif, sans risque de ReDoS. GNU grep construit son automate à la demande ; une référence arrière, qui ne décrit pas un langage régulier, l'oblige à confier les lignes candidates à un moteur plus lent. RE2 (Go, Rust) et ripgrep reposent sur la même idée.