##  [Automate Fini](/fr/node/58893) 

 Définition

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

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

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

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

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

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

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

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

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.