Automate fini déterministe

Finite Automaton peut être classé en deux types -

• Automate fini déterministe (DFA)
• Automate fini non déterministe (NDFA / NFA)

Automate fini déterministe (DFA)

Dans DFA, pour chaque symbole d'entrée, on peut déterminer l'état vers lequel la machine se déplacera. Par conséquent, il est appeléDeterministic Automaton. Comme elle a un nombre fini d'états, la machine est appeléeDeterministic Finite Machine ou Deterministic Finite Automaton.

Définition formelle d'un DFA

Un DFA peut être représenté par un 5-tuple (Q, ∑, δ, q ₀ , F) où -

• Q est un ensemble fini d'états.

• ∑ est un ensemble fini de symboles appelé alphabet.

• δ est la fonction de transition où δ: Q × ∑ → Q

• q₀est l'état initial à partir duquel toute entrée est traitée (q ₀ ∈ Q).

• F est un ensemble d'états finaux de Q (F ⊆ Q).

Représentation graphique d'un DFA

Un DFA est représenté par des digraphes appelés state diagram.

• Les sommets représentent les états.
• Les arcs étiquetés avec un alphabet d'entrée montrent les transitions.
• L'état initial est indiqué par un arc entrant unique vide.
• L'état final est indiqué par des doubles cercles.

Exemple

Soit un automate fini déterministe →

• Q = {a, b, c},
• ∑ = {0, 1},
• q ₀ = {a},
• F = {c}, et

Fonction de transition δ comme indiqué dans le tableau suivant -

État actuel	État suivant pour l'entrée 0	État suivant pour l'entrée 1
a	une	b
b	c	une
c	b	c

Sa représentation graphique serait la suivante -