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

Automate déterministe de pushdown

Description

Cette séance de cours couvre le concept d'automates de poussée déterministes, y compris les définitions formelles, le théorème de l'inflation et l'utilisation du théorème de l'inflation dans la reconnaissance linguistique. Il explore également l'utilisation d'automates déterministes pour la reconnaissance des langues.

Source officielle

Concepts associés (20)

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.

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.

Langage algébrique déterministe

En informatique théorique et en théorie des langages, un langage algébrique déterministe est un langage algébrique reconnu (par états finals) par un automate à pile déterministe. L'intérêt des langages déterministes est que leur analyse syntaxique se fait en temps linéaire en la longueur du mot, alors que dans un langage algébrique quelconque, la complexité est cubique, ou en tout cas se ramène à la complexité du produit matriciel, donc est en O(n2,37) où n est la longueur du mot par l'algorithme de Valiant.

Automate fini déterministe bidirectionnel

En informatique théorique, et notamment en théorie des automates, un automate fini déterministe bidirectionnel (en anglais ) souvent abrégé en 2AFD (en anglais 2DFA), est un automate fini déterministe qui peut relire des symboles d'entrée déjà vus. Comme pour les automates finis déterministes usuels, un 2AFD possède un nombre fini d'états, et le passage d'un état à un autre est régi par des transitions en fonction du symbole lu. De plus, une transition porte une information sur la direction de déplacement de la lecture, soit vers la droite soit vers la gauche.

Automate fini déterministe

Un automate fini déterministe, parfois abrégé en AFD (en anglais deterministic finite automaton, abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.

Afficher plus

Séances de cours associées (32)

Finite Automata: Bases

Introduit les bases des automates finis, y compris les types déterministes et non déterministes, les expressions régulières et les critères d'acceptation.

Grammaires sans contexte

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

Expressions régulières (Récapitulatif)

Couvre les principes fondamentaux des expressions régulières et comprend des exercices sur la définition des langues.

Stack Automata: Définition formelle

Couvre la définition formelle et les propriétés des automates de pile.

Expressions régulières : Fondements et applications

Introduit des expressions régulières, couvrant les ensembles de langage, la syntaxe, la sémantique et les limitations.

Afficher plus

Concepts associés (20)

Deterministic pushdown automaton

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.

Langage algébrique déterministe

Automate fini déterministe bidirectionnel

Automate fini déterministe

Afficher plus