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.
L'importance des automates à pile vient de leur emploi en analyse syntaxique des langages de programmation, et plus généralement dans la transformation de définitions ou d'algorithmes récursifs en leurs analogues itératifs.
vignette|upright=2|Un automate à pile. Une unité de contrôle finie agit en lisant la donnée sur la bande d'entrée (input tape), et en utilisant une mémoire auxiliaire en forme de pile (stack).
Un automate à pile (non déterministe) est un 7-uplet , où :
est l'ensemble détats ;
est lalphabet d'entrée ;
est l'''alphabet de pile ;
est la fonction de transition (la notation désigne l'ensemble des parties) ;
est le symbole de fond de pile ;
est létat initial ;
est l'ensemble des états terminaux.
Au lieu de la fonction , on rencontre fréquemment l'ensemble défini par
Les éléments de sont les règles de transitions. Lorsque , on parle d'une -règle.
Tous les ensembles dans la définition sont finis.
Une configuration interne de l'automate est un couple .
Une configuration de l'automate est un triplet . Un calcul de l'automate sur un mot est une suite de transitions à partir de la configuration initiale . Il y a transition de la configuration , où et vers la configuration et on écrit :
lorsque .
Lorsque , le mot d'entrée ne change pas.
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Le palindrome (adjectif et substantif masculin), du grec / pálin (« en arrière ») et / drómos (« chemin, voie »), aussi appelé palindrome de lettres est une figure de style désignant un mot ou une phrase dont l'ordre des lettres reste le même qu'on les lise de gauche à droite ou de droite à gauche, comme dans la phrase ou encore à un accent près. Le palindrome est un cas particulier d'anacyclique (lequel est lui-même un cas particulier d'anagramme) comme « suce|écus », pour lequel la signification est la même dans les deux sens de lecture.
En informatique théorique, une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur. Ce modèle a été imaginé par Alan Turing en 1936, en vue de donner une définition précise au concept d’algorithme ou de « procédure mécanique ». Il est toujours largement utilisé en informatique théorique, en particulier dans les domaines de la complexité algorithmique et de la calculabilité.
En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul.
Behavioral diversity seen in biological systems is, at the most basic level, driven by interactions between physical materials and their environment. In this context we are interested in falling paper systems, specifically the V-shaped falling paper (VSFP) ...
Fuzzers aware of the input grammar can explore deeper program states using grammar-aware mutations. Existing grammar-aware fuzzers are ineffective at synthesizing complex bug triggers due to: (i) grammars introducing a sampling bias during input generation ...
The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...