Un automate à pile est une machine abstraite utilisée en informatique théorique et, plus précisément, en théorie des automates.
Un automate à pile est une généralisation des automates finis : il dispose en plus d'une mémoire infinie organisée en pile (last-in/first-out ou LIFO). Un automate à pile prend en entrée un mot et réalise une série de transitions. Il effectue pour chaque lettre du mot une transition, dont le choix dépend de la lettre, de l'état de l'automate et du sommet de la pile ; il peut aussi modifier le contenu de la pile. Selon l'état de l'automate et de la pile à la fin du calcul, le mot est accepté ou refusé.
Les langages reconnus par les automates à piles sont exactement les langages algébriques, c'est-à-dire ceux engendrés par une grammaire algébrique.
- Enseignant: Keltoum Benlaharche (Enseignante)
Supports de cours Théorie des Langages
- Enseignant: Keltoum Benlaharche (Enseignante)
What is the Theory of Computation?
The Theory of Computation is a branch of computer science and mathematics that focuses on determining problems that can be solved mechanically, using an algorithm or a set of programming rules. It is also concerned with the efficiency at which the algorithm can perform the solution.
In simple terms, the Theory of Computation answers these questions:
- What problems can the machine solve? What problems can’t it solve?
- How fast can a machine solve a problem?
- How much memory space does a machine need to solve a problem?
To answer these questions, computer scientists use a model of computation, which is a computer simulation for the algorithm being developed. The Turing machine is among the most used models of computation.
- Enseignant: Keltoum Benlaharche (Enseignante)