Automa a stati finiti deterministico

Un automa a stati finiti deterministico, o DFA (Deterministic Finite Automaton), è un modello di calcolo dove ogni stato del sistema ha una transizione ben definita per ogni possibile input.

In altre parole, dato un particolare stato e un simbolo di input, c'è sempre un unico stato successivo a cui il sistema può passare.

La funzione di transizione mappa ogni coppia di stato e simbolo di input a un singolo stato successivo.

Ogni coppia di stato e simbolo di input ha una transizione ben definita a uno e un solo stato successivo.

Per il resto, come ogni automa a stati finiti, anche l'automa DFA è caratterizzato da uno stato iniziale di partenza e uno o più stati di accettazione (finali).

Esempio pratico

Consideriamo un automa che riconosce stringhe di '0' e '1' che terminano con '01'.

• Stato iniziale: \( q_0 \)
• Stati: \( q_0, q_1, q_2 \)
• Alfabeto: \( \{0, 1 \} \)
• Transizioni:
  - Da \( q_0 \) con '1' rimane a \( q_0 \)
  - Da \( q_0 \) con '0' va a \( q_1 \)
  - Da \( q_1 \) con '0' rimane a \( q_1 \)
  - Da \( q_1 \) con '1' va a \( q_2 \)
  - Da \( q_2 \) con '0' va a \( q_1 \)
  - Da \( q_2 \) con '1' va a \( q_0 \)
• Stato finale: \( q_2 \)

In ogni singolo stato l'automa compie un'azione precisa per ogni simbolo dell'alfabeto.

Inoltre, se si elabora la stessa stringa l'automa ha lo stesso comportamento, ossia compie la stessa sequenza di azioni.

Esempio. La stringa w="001" genera questi passaggi di stato (q₀, q₁, q₁, q₂) e la stringa viene accettata. Viceversa la stringa w="010" genera questra transizioni (q₀, q₁, q₂, q₁) e la stringa viene rifiutata. 

E' quindi possibile prevedere il comportamento dell'automa in modo deterministico.