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

  • q0est l'état initial à partir duquel toute entrée est traitée (q 0 ∈ 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 0 = {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 -