Teoria degli automi

Premessa

Ciao! Se è la prima volta che capiti su questo sito, ti consiglio di consultare la pagina principale di questo Giardino Digitale per scoprire meglio cos’è e come navigarlo.

Lo stato di questa nota è al momento: 🔴 Bozza.

---

Definizione: automa a stati finiti deterministico (DFA)

Un automa a stati finiti deterministico (DFA, dall’inglese Deterministic Finite-state Automaton) è una quintupla $\mathcal{A}=⟨\Sigma ,S,\delta ,s_0,F⟩$ dove:

• $\Sigma =\{a_0,a_1,\dots ,a_n\}$ è un alfabeto,
• $S=\{s_0,s_1,\dots ,s_m\}$ è un insieme finito di stati,
• $\delta :\Sigma \times S\to S$ è una funzione detta funzione di transizione fra stati,
• $s_0\in S$ è uno stato detto stato iniziale e
• $F\subseteq S$ è un insieme degli stati finali.

Esempio: numero dispari di $\text{a}$

Proviamo a definire un DFA che riconosce solo le stringhe di $\text{a}$ di lunghezza dispari.

Questo automa $\mathcal{A}=⟨\Sigma ,S,\delta ,s_0,F⟩$ sarà così definito:

• $\Sigma =\{\text{a}\}$ perché ci servono solo stringhe contenenti il simbolo $\text{a}$;
• $S=\{s_0,s_1\}$ perché servono solo due stati, uno per quando la stringa sarà di lunghezza pari e uno per quando sarà di lunghezza dispari;
• $\delta :\Sigma \times S\to S$ così definita:
  • $\delta (\text{a},s_0)=s_1$ perché quando la stringa sarà di lunghezza pari ($s_0$) e riceve un $\text{a}$ in input diventa dispari ($s_1$) e, viceversa,
  • $\delta (\text{a},s_1)=s_0$ perché quando la stringa sarà di lunghezza dispari ($s_1$) e riceve un $\text{a}$ in input diventa pari ($s_0$);
• $s_0\in S$ come stato finale e
• $F=\{s_1\}$ perché la stringa sarà accettabile solo quando avrà lunghezza dispari.

---

Fonti

• 🏫 Corso di Laurea in Informatica (L-31 R) presso l’Università di Torino:
  • Corso di Linguaggi Formali e Traduttori (INF0344), A.A. 2026-27 (pagina Moodle):
    • Prof. Jeremy James Sproston, slide del corso:
      • 2.1 - DFA.