Automa a stati finiti deterministico

Nella teoria del calcolo, un automa a stati finiti deterministico (ASFD) o deterministic finite automaton (DFA) è un automa a stati finiti dove per ogni coppia di stato e simbolo in ingresso c'è una ed una sola transizione allo stato successivo.

Definizione formale

Un ASFD è una quintupla $\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ con:

• $\Sigma = \{a_0, a_1, \ldots, a_n\}$ insieme finito di simboli chiamato alfabeto
• $S = \{s_0, s_1, \ldots, s_m\}$ insieme finito di stati
• $\delta : S \times \Sigma \to S$ funzione di transizione
• $s_0 \in S$ stato iniziale
• $F \subseteq S$ insieme di stati finali

Dato un ASFD $\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$, una configurazione di $\mathcal{A}$ è una coppia $(s, x)$, dove $s$ è uno stato e $x$ una stringa dell'alfabeto.

Una configurazione $(s, x)$ è detta:

• iniziale se s è lo stato iniziale, $s = s_0$;
• finale se la stringa in input è vuota, $x = \varepsilon$;
• accettante se la stringa in input è vuota e l'automa si trova in uno stato finale, $x = \varepsilon$ e $s \in F$.

La funzione di transizione induce una relazione di transizione $\vdash$ tra due configurazioni, che associa ad una configurazione dell'automa la configurazione successiva.
Dato un ASFD $\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ e due configurazioni $(s, x)$ e $(s', y)$ di $\mathcal{A}$, avremo tra loro una relazione di transizione $(s, x) \vdash_\mathcal{A} (s', y)$ se valgono:

• esiste un simbolo $a \in \Sigma$ tale che $x = ay$
• $\delta(s, a) = s'$

L'insieme delle stringhe riconosciute dall'automa $\mathcal{A}$ forma un linguaggio formale chiamato linguaggio riconosciuto o linguaggio accettato dall'automa. Possiamo quindi dire che $L(\mathcal{A}) = \{x \in \Sigma^{*} | (s_0, x) \vdash_\mathcal{A}^* (s, \varepsilon), s \in F\}$, ovvero che il linguaggio riconosciuto dall'ASFD A è composto da tutte le stringhe x sull'alfabeto dato tali che, partendo dalla configurazione iniziale con la stringa x ed applicando iterativamente le relazioni di transizione, pervengono ad una configurazione accettante.

Il teorema di Kleene dimostra che la collezione dei linguaggi accettati da automi a stati finiti deterministici coincide sia con la collezione dei linguaggi regolari che con i linguaggi definiti da espressioni regolari.

Le espressioni regolari sono chiamate anche espressioni razionali e di conseguenza i linguaggi che esse forniscono sono detti linguaggi razionali; questi termini sono giustificati dal fatto che questi oggetti si possono studiare con metodi algebrici, più precisamente mediante semigruppi finiti.

Funzione delta estesa

Un modo alternativo per descrivere il comportamento dell'automa è quello di definire la funzione di transizione estesa che estende la funzione di transizione dai simboli alle stringhe. Indichiamo la nuova funzione come $\bar{\delta} : (S \times \Sigma^{*} ) \to S$.

La sua definizione viene data induttivamente sulla lunghezza della stringa.

• Base: $\bar{\delta} (q, \varepsilon) = q$.
• Ipotesi induttiva: $\bar{\delta} (q, x) = p$.
• Passo induttivo: $\bar{\delta} (q, \omega) = \bar{\delta} (\bar{\delta} (q, x), a) = \bar{\delta} (p, a) = r$, con $\omega = xa$.

Sfruttando la funzione delta estesa è possibile ridefinire il linguaggio accettato dall'automa come:

$L(\mathcal{A}) = \{x \in \Sigma^* | \bar{\delta} (s_0, x) \in F \}$

Esempio

Il seguente esempio è una ASFD $\mathcal{A}$, con un alfabeto binario, che determina se l'input contiene un numero pari di zeri.

$\mathcal{A} = \left \langle \Sigma, S, \delta, s_0, F \right \rangle$ con:

• $\Sigma = \{0, 1\}$ alfabeto binario
• $S = \{S_1, S_2\}$ stati
• $s_0 = S_1$ stato iniziale
• $F = \{S_1\}$ stati finali

Automa a stati finiti dell'esempio

• $\delta = \left\{\begin{matrix} \delta (S_1, 0) = S_2 \\ \delta (S_1, 1) = S_1 \\ \delta (S_2, 0) = S_1 \\ \delta (S_2, 1) = S_2\end{matrix}\right.$

La tabella di transizione è la seguente:

	0	1
S1	S2	S1
S2	S1	S2

Semplicemente, lo stato $S_1$ rappresenta lo stato in cui abbiamo sempre un numero pari di zeri nell'input, mentre $S_2$ indica un numero dispari di zeri. Un 1 in input non cambia lo stato dell'automa. Quando l'input termina, lo stato mostrerà se l'input conteneva un numero pari di zeri, o no.

Da questo ASFD possiamo ricavare la grammatica regolare che genera il linguaggio regolare riconosciuto dall'ASFD:

$S_1 \to 0S_2\; |\; 1S_1\; |\; 1\; |\; \varepsilon$

$S_2 \to 0S_1\; |\; 1S_2\; |\; 0$

Il linguaggio riconosciuto da $\mathcal{A}$ può essere descritto dal linguaggio regolare dato dalla seguente espressione regolare:

$1^*(01^*01^*)^*$

Bibliografia

• Giorgio Ausiello; Fabrizio d’Amore; Giorgio Gambosi, Linguaggi, Modelli, Complessità, Franco Angeli Editore, 2003. ISBN 88-464-4470-1
• finite state machine (FSM) in Hargrave's Communications Dictionary (in inglese), Hoboken, Wiley, 2001.
• Sequential machine in Encyclopedia of Computer Science (in inglese), Hoboken, Wiley, 2003.
• John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman, Finite Automata in Introduction to Automata Theory, Languages, and Computation (in inglese), Addison Wesley, 15 luglio 2006. 978-0321462251
• Martin Davis; Ron Sigal; Elaine J. Weyuker, Finite Automata in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (in inglese), Morgan Kaufmann, 17 febbraio 1994. 978-0122063824

Voci correlate

• Automa a stati finiti non deterministico
• Automa a stati finiti
• Macchina di Moore
• Macchina di Mealy
• Linguaggio regolare
• Grammatica regolare
• Espressione regolare

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica	Linguaggio	Automa minimo
Tipo-0	(illimitato)	Ricorsivamente enumerabile	Macchina di Turing
	(illimitato)	Ricorsivo	Decider
Tipo-1	Dipendente dal contesto	Dipendente dal contesto	Automa lineare
Tipo-2	Libera dal contesto	Libero dal contesto	Automa a pila ND
Tipo-3	Regolare	Regolare	A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.

Portale Informatica: accedi alle voci di Wikipedia che trattano di Informatica