Séance de cours

Stack Automata: Définition formelle

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours présente les automates de pile, en mettant l'accent sur leur définition formelle et leurs propriétés. L'instructeur explique le concept d'automate de pile, leurs composants, et comment ils fonctionnent. La séance de cours couvre la définition formelle des automates de pile, y compris la fonction de transition et les critères d'acceptation.

Source officielle

Concepts associés (14)

Automate à pile

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.

Théorie des automates

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.

Deterministic pushdown automaton

In automata theory, a deterministic pushdown automaton (DPDA or DPA) is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages. Machine transitions are based on the current state and input symbol, and also the current topmost symbol of the stack. Symbols lower in the stack are not visible and have no immediate effect. Machine actions include pushing, popping, or replacing the stack top.

Système de transition d'états

En informatique théorique, un système de transition d'états est une forme de machine abstraite utilisée pour modéliser un ou des calcul(s). Un système de transition d'états est constitué d'un ensemble d'états et d'un ensemble de transitions d'un état à un autre, qui peuvent être étiquetées ; une même étiquette peut apparaître sur plusieurs transitions. Si l'ensemble des étiquettes est un singleton, on peut omettre l'étiquetage. Les systèmes d'états-transitions sont des graphes orientés.

Couleur

vignette|Peinture de Claude Monet. La couleur est la perception visuelle de l'aspect d'une surface ou d'une lumière, basée, sans lui être rigoureusement liée, sur la répartition spectrale de la lumière, qui stimule des cellules nerveuses spécialisées situées sur la rétine nommées cônes. Le système nerveux transmet et traite l'influx jusqu'au cortex visuel.

Afficher plus

Séances de cours associées (63)

Turing Machines: Langues récursives

Explore les machines Turing, les langages récursifs, l'indécidabilité et l'élimination des symboles.

Automate déterministe de pushdown

Couvre les automates de poussée déterministes et leur utilisation dans la reconnaissance des langues.

Complexité computationnelle

Couvre les bases de la complexité computationnelle, y compris les grandes classes de notation O et de complexité.

Machines de Turing: Basics

Couvre les bases des machines de Turing, y compris les états, la manipulation de bandes et les capacités de résolution de problèmes.

Grammaires sans contexte

Couvre les grammaires sans contexte, leur équivalence avec les automates pushdown et la hiérarchie des types de grammaire.

Afficher plus

Concepts associés (14)

Automate à pile

Théorie des automates

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.

Deterministic pushdown automaton

Système de transition d'états

Couleur

Afficher plus