Séance de cours

Finite Automata: Expressions régulières et Automaton Finite Déterministe

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 couvre la conversion d'automates finis à des expressions régulières, des exercices sur la construction d'automates finis déterministes, et la conversion d'expressions régulières en NFA et DFA à l'aide d'outils en ligne. Il comprend également des exercices sur la création de NFAs et de DFAs pour des modèles linguistiques spécifiques.

Source officielle

Proximité ontologique

Informatique théorique

Theory of computation: Théorie des automates

Concepts associés (18)

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

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

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.

Afficher plus

Séances de cours associées (48)

Finite Automata: Récapitulation et détermination

Couvre une récapitulation des APN et introduit le processus de détermination.

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.

Finite Automata: Récapitulation

Couvre les fondamentaux des automates finis et des langues formelles.

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.

Machines à états finis: bases et conception

Introduit des machines à états finis, couvrant les bases, la conception et les applications pratiques telles que les décodeurs et les encodeurs.

Afficher plus

Concepts associés (18)

Automate fini déterministe bidirectionnel

Automate fini déterministe

Automate fini non déterministe

Automate quantique

Automate fini

Afficher plus