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

Finite Automata: Bases

Description

Cette séance de cours couvre les bases des automates finis, y compris les automates finis déterministes et non déterministes, les expressions régulières, les définitions formelles, les critères d'acceptation et la dérivabilité. L'instructeur explique les concepts étape par étape, en fournissant des exemples et des clarifications.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie des automates

Concepts associés (28)

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é.

Automate fini

thumb|upright=2|Fig. 1 : Une hiérarchie d'automates. Un automate fini ou automate avec un nombre fini d'états (en anglais finite-state automaton ou finite state machine ou FSM) est un modèle mathématique de calcul, utilisé dans de nombreuses circonstances, allant de la conception de programmes informatiques et de circuits en logique séquentielle aux applications dans des protocoles de communication, en passant par le contrôle des processus, la linguistique et même la biologie.

Automate fini non déterministe

Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation.

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 quantique

En informatique quantique et en informatique théorique, un automate fini quantique est une généralisation des automates finis où un mot est accepté selon le résultat d'une certaine mesure. Il existe plusieurs modèles des automates finis quantiques ; le plus restrictif est celui des automates dits « measure-once » de ; un autre est celui des automates « measure-many » de . Ces deux modèles sont très différents l'un de l’autre ; le modèle « measure-once » se rapproche plus de la théorie classique des automates finis.

Afficher plus

Séances de cours associées (33)

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.

Des expressions régulières aux automatismes

Explore la transition des expressions régulières aux automates finis, couvrant la création de lexers, les différents types d'automates et les processus de conversion.

Théorie Automata: Bases et Théorèmes

Introduit les bases de la théorie des automates et explore les théorèmes des langues régulières.

Grammaires sans contexte

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

Finite Automata: Récapitulation

Couvre les fondamentaux des automates finis et des langues formelles.

Afficher plus

Concepts associés (28)

Automate fini déterministe

Automate fini

Automate fini non déterministe

Automate fini déterministe bidirectionnel

Automate quantique

Afficher plus