Automates finis et expressions régulières

Les automates finis et les expressions régulières décrivent exactement la même famille de langages : c'est un des résultats fondateurs de l'informatique théorique (le théorème de Kleene). Concrètement, pour tout automate fini déterministe, il existe une expression régulière qui reconnaît exactement le même ensemble de mots, et réciproquement.

Reprenons notre exemple : l'automate qui accepte les mots se terminant par «ab» sur l'alphabet {a, b}. L'expression régulière équivalente s'écrit :

Automate (mots finissant par «ab»)          <-->     Expression reguliere equivalente

  --> (q0) --a--> (q1) --b--> (( q2 ))                     (a|b)*ab
        ^ boucle «b»   ^ boucle «a»
        |______________|

  (a|b)*   = n'importe quel prefixe fait de «a» et de «b»   (correspond à la boucle q0/q1)
  ab       = obligatoirement termine par «a» puis «b»       (correspond au chemin final vers q2)

Cette expression se lit : "n'importe quelle suite de a et de b (éventuellement vide), suivie obligatoirement de a puis de b". La partie «(a|b)*» correspond exactement à la boucle entre q0 et q1 qui absorbe n'importe quel préfixe, et le «ab» final correspond au chemin q0 -> q1 -> q2 qui déclenche l'acceptation.

Cette équivalence n'est pas qu'une curiosité théorique : c'est la base des moteurs de recherche de motifs (grep, les validateurs de formulaires, les analyseurs lexicaux de compilateurs). Quand tu écris une expression régulière dans un langage de programmation, elle est en général compilée en un automate fini avant d'être exécutée sur le texte, précisément parce qu'un automate s'exécute en temps linéaire, lettre par lettre, sans jamais revenir en arrière.

Piège classique : croire que toute expression régulière "moderne" (avec lookaheads, retour en arrière...) correspond à un automate fini simple. Les vraies expressions régulières théoriques (celles du théorème de Kleene) sont plus restreintes que les "regex" étendues de certains langages de programmation, qui ajoutent des fonctionnalités dépassant les automates finis classiques.