Automate à piles emboîté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 emboîtées?
Résumez cet article pour un enfant de 10 ans
En théorie des automates, un automate à piles emboîtées est un automate fini qui utilise comme mémoire auxiliaire une pile dont les éléments peuvent eux-mêmes être des piles[1]. Mais contrairement à un automate à pile usuel, un automate à piles emboîtées peut se déplacer en avant et en arrière sur la « pile », qui est donc plutôt structurée en liste ; de plus, l'automate peut insérer une nouvelle pile, opérer sur elle, la détruire, et continuer à travailler sur l'ancienne pile. Ce mode opératoire peut être emboîté récursivement à une profondeur arbitraire ; toutefois, l'automate manipule toujours la pile la plus interne.
Un automate à piles emboîtées est capable de reconnaître un langage indexé, et de fait les langages indexés sont exactement les langages reconnus par les automates à piles emboîtées non déterministes[2],[1],[3].
Les automates à piles emboîtées diffèrent des automates à piles embarquées qui sont moins puissants puisque pour ces derniers, la mémoire auxiliaire, toujours organisée récursivement, n'est accessible que par le haut de pile. Les automates à pile embarquée reconnaissent exactement les langages engendrés par les grammaires d'arbres adjoints[4].