#027 / 100•Space, Chance & Computation•MathTCG #427 / 500•★★★Rare•∀Logique•Concept

Automate fini déterministe

Période historique : 1943

Machine d'états finie lisant séquentiellement une chaîne pour décider si elle appartient à un langage rationnel.

Contenu & Formulation mathématique

Définition rigoureuse

Machine d'états finie lisant séquentiellement une chaîne pour décider si elle appartient à un langage rationnel.

M = (Q, \Sigma, \delta, q_0, F), \quad \delta : Q \times \Sigma \to Q, \quad L(M) = \{ w \mid \delta^*(q_0, w) \in F \}

Genèse & Portée historique

Un automate fini déterministe (DFA) est un quintuplet composé d'un ensemble fini d'états, d'un alphabet, d'une fonction de transition déterministe, d'un état initial et d'un ensemble d'états acceptants. D'après le théorème de Kleene, la classe des langages reconnus par les DFA coïncide exactement avec celle des expressions régulières.

Introduit à l'origine par Warren McCulloch et Walter Pitts en 1943 pour modéliser le fonctionnement des réseaux de neurones biologiques avant d'être formalisé par Michael Rabin et Dana Scott.

« Sans mémoire auxiliaire, il suit le fil des symboles d'état en état vers l'acceptation. »

Filiations & Relations conceptuelles (0)

Cette notice constitue un axiome autonome sans relations directes enregistrées dans le recueil.

Objet de collection MathTCG

#427

★★★Rare

∀

Automate fini déterministe

Logique•CONCEPT

Machine d'états finie lisant séquentiellement une chaîne pour décider si elle appartient à un langage rationnel.

M = (Q, \Sigma, \delta, q_0, F), \quad \delta : Q \times \Sigma \to Q, \quad L(M) = \{ w \mid \delta^*(q_0, w) \in F \}

1943

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#027 / 100)

Numéro global MathTCG : MathTCG #427 / 500

Rareté officielle : Rare (★★★)

Domaine théorique : Logique

Identifiant pérenne : automate-fini-deterministe

Consulter mon classeur Explorer tout le recueil