Modèle mathématique de calcul composé d'un ensemble fini d'états, d'un alphabet d'entrée, de relations de transition, d'un état initial et d'un ou plusieurs états acceptants ; utilisé pour reconnaître les langages réguliers. Variantes : automate fini déterministe (DFA) et non déterministe (NFA).

Principe

Le calcul progresse en lisant un symbole d'entrée et en changeant d'état selon les règles de transition ; l'acceptation dépend de l'atteinte d'un état acceptant après consommation de l'entrée. La non-déterminisme permet plusieurs transitions possibles ; le déterminisme n'en permet qu'une par paire état-symbole.

Démonstration

Un analyseur lexical compilé à partir d'expressions régulières est implémenté par un DFA qui parcourt le texte source de gauche à droite ; les transitions d'état encodent les motifs réguliers pour mots-clés, identifiants et littéraux, reconnaissant les tokens en temps linéaire avec mémoire bornée.

Mauvaise application

Tenter d'utiliser un automate fini pour analyser des structures imbriquées ou context-free (par ex. parenthèses appariées à profondeur arbitraire) qui exigent une mémoire non bornée (p. ex. une pile) ; cela conduit à une reconnaissance incorrecte ou incomplète.

Conséquence

Reconnaissance efficace en temps linéaire de motifs réguliers avec un faible coût mémoire fixe ; permet de compiler des expressions régulières en tables de transition compactes et sous-tend de nombreuses applications de traitement de texte et de contrôle matériel.

Inversion

Un automate à pile ou une machine de Turing qui augmentent l'état par une mémoire non bornée (pile ou bande) pour reconnaître des langages hors réguliers ou Turing-complètes, au prix d'un contrôle et d'une utilisation des ressources plus complexes.

Limite

Caractérise exactement les langages réguliers ; ne peut pas reconnaître les langages non réguliers nécessitant une mémoire non bornée. DFA et NFA sont équivalents en pouvoir d'expression bien qu'ils diffèrent en succincticité et en compromis d'implémentation.

Tension sémantique

Automate fini versus expression régulière : les deux définissent la même classe de langages mais diffèrent entre vue opérationnelle par machine à états et description déclarative de motifs ; cette différence compte pour la construction et l'optimisation.

Synthèse

Un contrôleur à états finis qui traite des symboles d'entrée via des transitions d'état, fournissant un mécanisme compact et efficace pour reconnaître exactement les langages réguliers ; sa mémoire limitée (états finis) est à la fois sa contrainte et ce qui le rend utile.