Automate à piles intégrées
type d'automate théorique / De Wikipedia, l'encyclopédie encyclopedia
Cher Wikiwand IA, Faisons court en répondant simplement à ces questions clés :
Pouvez-vous énumérer les principaux faits et statistiques sur Automate à piles intégrées?
Résumez cet article pour un enfant de 10 ans
En linguistique et en théorie des automates, un automate à piles intégrées en anglais « embedded pushdown automaton » ou EPDA est une automate pour la reconnaissance d'un langages engendré par une grammaire d'arbres adjoints (en anglais « tree-adjoining grammar » ou TAG).
Un tel automate ressemble à un automate à pile utilisé pour l’analyse des langages algébriques, mais à la place d'une pile simple contenant des symboles, il possède une pile composée de piles. Ainsi, la pile d'un EPDA est une constituée d'une suite de piles (ordinaires) juxtaposées. Ceci donne aux grammaires correspondantes une capacité générative plus importante et les situe entre les grammaires algébriques et les grammaires contextuelles ; ces grammaires forment un sous-ensemble des grammaires regroupées sous le terme de grammaires faiblement contextuelles (en).
Les automates à piles intégrées ne doivent pas être confondues avec les automates à piles emboîtées dont la puissance de reconnaissance est encore plus importante puisque ces derniers reconnaissent les langages indexés.