##  [Automate à Pile](/fr/node/58895) 

 Définition

Automate enrichi d'une mémoire auxiliaire de type pile (LIFO) ; il reconnaît exactement les langages générés par des grammaires context‑free (langages hors-contexte) en combinant transitions d'états et opérations de push/pop sur la pile.

 

 

 

 

 

 





## Principe

Principe

Un contrôle fini associé à une pile LIFO fournit une mémoire structurée et non bornée suffisante pour représenter des dépendances imbriquées et hiérarchiques tout en conservant une structure de transitions à états finis.

 

 

 

 

 





## Démonstration

Démonstration

Un automate à pile non déterministe qui, pour une entrée a^n b^n, empile un symbole pour chaque a puis dépile un symbole par b reconnaît précisément le langage équilibré {a^n b^n | n≥0} par critère de pile vide ou d'état acceptant.

 

 

 

 

## Mauvaise application

Mauvaise application

Considérer qu'un automate à pile suffit pour reconnaître des langages nécessitant deux compteurs indépendants (par exemple a^n b^n c^n) ou supposer que les PDA déterministes (DPDA) peuvent décider tous les langages hors-contexte ; confondre les fonctionnalités pratiques d'analyseur (lookahead, actions sémantiques) avec le modèle formel de PDA.

 

 

 

 

 





## Conséquence

Conséquence

Une utilisation correcte donne des équivalences formelles (avec les grammaires hors-contexte et les PDA non déterministes), fonde les algorithmes d'analyse syntaxique et les frontières de décidabilité (appartenance, vacuité dans la classe CFL), et établit une séparation nette avec les automates réguliers et les modèles de type Turing.

 

 

 

 

## Inversion

Inversion

Un automate fini est dépourvu de pile et ne peut donc imposer de dépendances imbriquées non bornées ; une machine de Turing remplace la pile par une bande non bornée bidirectionnelle, augmentant strictement la puissance d'expression par rapport aux PDA.

 

 

 

 

 





## Limite

Limite

Sont visés les automates à pile à unique pile (distinctions déterministe vs non déterministe applicables) ; sont exclus les systèmes à plusieurs piles ou files, les annotations temporelles ou probabilistes et les piles dont les jetons sont distingués, sauf indication contraire.

 

 

 

 

 





## Tension sémantique

Tension sémantique

Tension entre le PDA théorique (pile unique pure) et les implémentations pratiques d'analyseurs qui ajoutent lookahead, actions sémantiques ou piles multiples ; aussi entre PDA déterministes (classe plus restrictive) et PDA non déterministes (classe CFL complète).

 

 

 

 

 





## Synthèse

Synthèse

Un automate à pile est un contrôleur à états finis muni d'une pile LIFO dont les opérations de push/pop permettent de reconnaître des structures imbriquées et context‑free que les automates finis ne peuvent capter.