Automate Fini Déterministe (AFD)

Qu'est-ce qu'un AFD ?

Un Automate Fini Déterministe (AFD) est un modèle mathématique qui lit un mot symbole par symbole afin de déterminer s'il appartient à un langage.

Définition

Un AFD est défini par :

AFD = (Q, Σ, δ, q₀, F)

Élément	Description
Q	Ensemble des états
Σ	Alphabet
δ	Fonction de transition
q₀	État initial
F	Ensemble des états finaux

Diagramme

stateDiagram-v2
[*] --> q0
q0 --> q1 : a
q0 --> q0 : b
q1 --> q1 : a
q1 --> q2 : b
q2 --> q1 : a
q2 --> q0 : b
state q2 <<accept>>

Cet automate accepte les mots qui se terminent par ab.

Simulation

Lettre	État
Début	q0
a	q1
b	q2 ✅

Exemple Python

class DFA:
    def __init__(self, states, alphabet, transitions, start, accept):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start = start
        self.accept = accept

    def run(self, word):
        state = self.start
        for symbol in word:
            if (state, symbol) not in self.transitions:
                return False
            state = self.transitions[(state, symbol)]
        return state in self.accept

dfa = DFA(
    {"q0","q1","q2"},
    {"a","b"},
    {
        ("q0","a"):"q1",
        ("q0","b"):"q0",
        ("q1","a"):"q1",
        ("q1","b"):"q2",
        ("q2","a"):"q1",
        ("q2","b"):"q0",
    },
    "q0",
    {"q2"},
)

for word in ["ab", "aab", "abb", "abab"]:
    print(word, dfa.run(word))

Exercices

1. Construire un AFD acceptant les mots contenant au moins un a.
2. Construire un AFD acceptant les mots commençant par bb.
3. Construire un AFD acceptant un nombre pair de 1.

Résumé

[!TIP]

• Un seul état initial.
• Une transition unique par symbole.
• Un mot est accepté si l'état atteint appartient à F.