Automate à pile - Définition
La liste des auteurs de cet article est disponible ici.
Applications
La plupart des langages de programmation sont décrits par une grammaire non contextuelle. L'analyse syntaxique d'un programme, qui est une des premières opérations effectuée par un compilateur, peut donc être effectuée par un automate à pile.
Il existe des outils automatiques pour construire l'automate à pile à partir d'une description de la grammaire du langage (par exemple Lex et Yacc en C).
Généralisation
Un automate à deux piles ou plus a la même puissance de calcul qu'une machine de Turing. En effet, les automates à deux piles sont une généralisation des machines à deux compteurs, elles mêmes équivalentes aux machines de Turing. On peut aussi le démontrer de manière plus directe : un automate à deux piles peut simuler une machine de Turing, en faisant en sorte que la partie du ruban située à gauche de la tête de lecture soit enregistrée dans la première pile, et la partie du ruban située à droite de la tête de lecture soit enregistrée sur la seconde.
