Definizione formale

Un automa a stati finiti deterministico (DFA, Deterministic Finite Automaton) è una quintuopla $A = \lang Q, \Sigma, \delta, q_0, F\rang$ in cui:

• $Q$ è l’insieme finito e non vuoto degli stati
• $\Sigma$ è l’alfabeto (insieme finito di simboli) di input
• $\delta:Q \times \Sigma \rarr Q$ è la funzione di transizione, che a ogni possibile coppia $(q, a)$ di uno stato $q$ e un simbolo in input $a$ associa uno stato $q'$ (informalmente, essa descrive come l’automa evolve quando, trovandosi in un certo stato, vede un certo simbolo in input);
• $q_0 \in Q$ è lo stato iniziale (che informalmente rappresenta il punto da cui “partono” le computazioni dell’automa, la usa “configurazione di default”);
• $F \subseteq Q$ è l’insieme degli stati finali o accettanti, che può essere un qualunque sottoinsieme di $Q$ (compresi i casi limite $F=\empty$ e $F=Q$).

Notazione: per indicare che $\delta(q, a)=q'$ si può scrivere $q \xrightarrow a q'$.

Osservazioni

La definizione appena data descrive le componenti necessarie a definire un DFA. Per specificare un particolare DFA, bisogna fornire istanze di ciascuna di queste componenti, indicando:

• quali sono gli elementi di $Q$
• quali sono i simboli dell’alfabeto $\Sigma$
• come è fatta la funzione di transizione $\delta$, cioè in particolare qual è l’elemento del codominio $Q$ che essa associa a ciascun elemento $(q, a) \in Q \times \Sigma$ del suo dominio
• quale elemento di $Q$ è lo stato iniziale
• come è fatto l’insieme degli stati final $F$

In particolare, per quanto riguarda la funzione di transizione, è importante ricordare che, secondo la definizione di funzione, essa deve associare un valore a ogni elemento del dominio (una funzione che invece associa valori solo a un sottoinsieme del dominio è detta funzione parziale)

Siccome gli insiemi $Q$ e $\Sigma$ sono insiemi finiti, anche il dominio $Q \times \Sigma$ della funzione di transizione è finito, quindi è possibile descrivere tale funzione in forma tabellare. Se $Q=\{q_0, q_1, ..., q_n\}$ e $\Sigma = \{a_0, a_1,...,a_m\}$, allora questa tabella ha la forma:

• gli stati sono elencati sulle righe