Automa a stati finiti

Un automa a stati finiti (ASF) è un sistema dinamico, invariante e discreto nell'avanzamento e nelle interazioni, nel quale gli insiemi dei possibili valori di ingresso, uscita e stato sono insiemi finiti.

• Dinamico significa che il sistema evolve nel tempo passando da uno stato all'altro in funzione dei segnali d'ingresso e dello stato precedente.
• Invariante: a parità di condizioni iniziali il comportamento del sistema è sempre lo stesso.
• Discreto: le variabili d'ingresso, di stato, d'uscita, possono assumere solo valori discreti.

L'automa a stati finiti è un modello di calcolo semplice rappresentabile come un piccolo dispositivo che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per l'elaborazione di quei linguaggi che nelle Grammatiche di Chomsky sono definiti di Tipo 3 o Regolari. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici ASFND.

Definizione formale

Gli automi finiti, o anche automi a numero di stati finito, vengono spesso chiamati in modo errato "automi a stati finiti" a causa della traduzione inglese - italiano di FSA (Finite State Automation), ma non è lo stato ad essere finito, bensì il numero degli stati. Il concetto di stato finito ricorre in meccanica quantistica (spazi di Hilbert) e non ha nulla a che vedere con la nozione di automa finito.

Automa a stati finiti deterministico

Per approfondire, vedi la voce automa a stati finiti deterministico.

Un ASF deterministico si definisce come un sistema $M = (I, U, S, f, g)$, dove

• $I = \{i_1, i_2, \ldots, i_n\}$ insieme finito dei possibili simboli in ingresso
• $U = \{u_1, u_2, \ldots, u_m\}$ insieme finito dei possibili simboli in uscita
• $S = \{s_1, s_2, \ldots, s_h\}$ insieme finito degli stati
• $f: I \times S \rightarrow S$ funzione di transizione degli stati interni successivi, che collega lo stato nell'istante successivo al valore attuale dell'ingresso e dello stato, $S(t+1) = g(S(t), I(t)) \,\!$
• $g: I \times S \rightarrow U$ funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, $U(t) = f(I(t), S(t)) \,\!$

Automa a stati finiti non deterministico

Per approfondire, vedi la voce automa a stati finiti non deterministico.

Un ASF non deterministico si definisce come un sistema $M = (I, U, S, f, g)$, dove

• $I = \{i_1, i_2, \ldots, i_n\}$ insieme finito dei possibili simboli in ingresso
• $U = \{u_1, u_2, \ldots, u_m\}$ insieme finito dei possibili simboli in uscita
• $S = \{s_1, s_2, \ldots, s_h\}$ insieme finito degli stati
• $f: I \times S \rightarrow \mathcal{P} (S)$ funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dell'ingresso e dello stato un sottoinsieme di S (quindi ad un sottoinsieme di possibili stati in S).
• $g: I \times S \rightarrow U$ funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, $U(t) = f(S(t), I(t)) \,\!$

Differenza tra ASFD ed ASFND

La differenza tra i due tipi di automi (già espressa dalle definizioni formali) consiste nel fatto che nei primi, in qualunque stato ci si trovi, per qualsiasi input, esisterà una ed una sola transizione, mentre nei secondi almeno uno stato presenta più di una possibile computazione per determinati caratteri in ingresso. Da notare che il determinismo è un caso particolare di non determinismo; tuttavia, nel caso degli automi a stati finiti, è possibile passare agevolmente dall'uno all'altro. L'idea è quella di unire in un unico stato collettivo [s₁,s₂,...,s_k] gli stati s₁,s₂,...,s_k raggiungibili con lo stesso ingresso, ovvero quelli che causano l'indeterminatezza dell'automa.

Rappresentazione della funzione di transizione di un ASFD

Diagramma di stato di una macchina di Mealy

Diagramma di stato di una macchina di Moore

Possiamo rappresentare gli automi a stati finiti con una tabella (tabella di transizione) o equivalentemente con una matrice (matrice di transizione). Alle righe associamo gli stati e alle colonne i simboli in input. Gli elementi della matrice rappresentano il risultato dell'applicazione della funzione di transizione.

g	a	b
s0	s0	s1
s1	s2	s2
s2	s2	s2

Un'altra rappresentazione molto usata è costituita dal diagramma degli stati, o grafo di transizione, che consiste nel rappresentare l'automa mediante un grafo orientato: i nodi rappresentano gli stati e gli archi le transizioni, etichettati col simbolo di input che genera la transizione. Si può marcare lo stato iniziale con un arco entrante dal nulla e gli stati finali con un doppio circolo.

A queste rappresentazioni va aggiunta la funzione di uscita corrispondente. I diagrammi di stato saranno così modificati, come si può vedere per le macchine di Mealy e di Moore.

Relazioni con altri tipi di macchine

Reti di Petri

Un ASF può essere considerato un tipo particolare di rete di Petri.

Automa di Mealy e Automa di Moore

Nell'automa di Moore, la funzione f dipende solo dallo stato: f = S → U e dunque U(t) = f(S(t)). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove l'uscita dipende dallo stato e dagli ingressi. Quest'ultimo tipo di automa è detto automa di Mealy.

Voci correlate

• Automa a stati finiti probabilistico
• Automa a stati finiti quantistico
• Gioco della vita
• Formica di Langton

Applicazioni Software

• SMCube - un tool gratuito per modellare, simulare e generare codice per macchine a stati finiti.

Altri progetti

• Commons

• Commons contiene file multimediali su Automa a stati finiti

Collegamenti esterni

• DFA Implementazione, in linguaggio C (open source), di un automa a stati finiti deterministico per il riconoscimento di numeri reali.
• Software SEQ per la minimizzazione degli stati delle macchine sequenziali (di Dario Mazzeo)
• SMCube Un tool free per la creazione, la simulazione, e la generazione automatica di codice per Macchine a stati finiti discrete.

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.