Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Stack Automata: Définition formelle

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 (30)

Automate déterministe de pushdown

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

Turing Machines: Langues récursives

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

Complexité computationnelle

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

Grammaires sans contexte

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

Complexité computationnelle: Théorie et applications

Explore la complexité computationnelle, l'exhaustivité du NP et les réductions polynômes de l'informatique théorique.

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