Séance de cours

Finite Automata: Récapitulation et détermination

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 une récapitulation sur les automates finis non déterministes (NFA) et introduit le processus de détermination, expliquant la conversion de NFA en automates finis déterministes (DFA). L'instructeur discute de l'utilisation d'expressions régulières, de l'acceptation des APN et de la transformation des APN en APN. Différents concepts tels que l'équivalence d'état, la construction sous-ensemble et l'ensemble de puissance sont explorés en détail.

Source officielle

Concepts associés (25)

Construction par sous-ensembles

En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel. L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile.

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

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

Minimisation d'un automate fini déterministe

vignette|upright=1.5|Dans cet automate, tous les états sont accessibles, les états c, d et e sont indistinguables, ainsi que les états a et b. vignette|upright=1.5|Automate minimal équivalent. Les états indistinguables sont regroupés en un seul état. En informatique théorique, et plus particulièrement en théorie des automates, la minimisation d'un automate fini déterministe est l'opération qui consiste à transformer un automate fini déterministe donné en un automate fini déterministe ayant le nombre minimal d'états et qui reconnaît le même langage rationnel.

Afficher plus

Séances de cours associées (39)

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.

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.

Digital Systems: Vue d'ensemble des machines à états finis

Couvre les machines à états finis, leurs types, leurs structures et leurs applications pratiques dans les systèmes numériques.

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.

Keylock en VHDL et sur FPGA

Couvre la conception d'un système KeyLock en VHDL, en se concentrant sur l'implémentation FSM pour la validation des clés et l'indication des LED.

Afficher plus

Concepts associés (25)

Construction par sous-ensembles

Automate fini déterministe bidirectionnel

Automate fini non déterministe

Automate fini déterministe

Minimisation d'un automate fini déterministe

Afficher plus