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.

Esempio di ASFD

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 fra stati
• $s_{0}\in S$ stato iniziale
• $F\subseteq S$ insieme di stati finali o terminali

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'$

Una stringa $x\in \Sigma ^{*}$ è accettata dall'ASFD ${\mathcal {A}}$ se, partendo dalla configurazione iniziale con la stringa ed applicando iterativamente le relazioni di transizione, si perviene ad una configurazione accettante. L'insieme delle stringhe accettate dall'automa forma un linguaggio formale chiamato linguaggio riconosciuto 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 è composto da tutte le stringhe sull'alfabeto dato per cui l'automa termina in uno stato finale.

Il teorema di Kleene dimostra che la collezione dei linguaggi riconosciuti 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 )={\delta }({\bar {\delta }}(q,x),a)={\delta }(p,a)=r$, con $\omega =xa$ (dove $a\in \Sigma$ e $x\in \Sigma ^{*}$).

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.
• (EN) finite state machine (FSM), in Hargrave's Communications Dictionary, Hoboken, Wiley, 2001.
• (EN) Sequential machine, in Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
• (EN) John E. Hopcroft, Rajeev Motwani; Jeffrey D. Ullman, Finite Automata, in Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 15 luglio 2006, ISBN 978-0-321-46225-1.
• (EN) Martin Davis, Ron Sigal; Elaine J. Weyuker, Finite Automata, in Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Morgan Kaufmann, 17 febbraio 1994, ISBN 978-0-12-206382-4.

Voci correlate

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