Automa a stati finiti

Un automa a stati finiti (ASF o FSA, dall'inglese finite state automaton, al plurale: f. s. automata) o macchina a stati finiti (FSM, dall'inglese finite state machine) è un modello matematico di calcolo: è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo modello è molto diffuso nell'ingegneria e nelle scienze, soprattutto nel campo dell'informatica e della ricerca operativa.

Un automa a stati finiti può essere utilizzato sia per modellare un sistema esistente che per modellare un nuovo sistema formale in grado di risolvere alcuni problemi esistenti. A quest'ultima categoria appartengono i cosiddetti riconoscitori di linguaggi e i traduttori. L'usuale rappresentazione grafica di un automa a stati finiti è il grafo orientato.

Descrizione

Nello specifico, con gli automi a stati finiti, si possono modellare tutti i sistemi che possiedono le seguenti caratteristiche:

• Dinamicità: caratteristica di evolvere nel tempo passando da uno stato ad un altro.
• Discretezza: caratteristica che indica che le variabili d'ingresso e gli stati del sistema da modellare possono essere espressi con valori discreti.
• Simboli finiti: caratteristica che determina che il numero di simboli di ingresso e di stati sia rappresentabile da un numero finito.

Dal punto di vista pratico, il concetto di automa a stati finiti equivale a costruire 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).

Tipologie

Automa a stati finiti deterministico

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

• ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}$ insieme finito dei possibili simboli in ingresso
• ${\displaystyle U=\{u_{1},u_{2},\ldots ,u_{m}\}}$ insieme finito dei possibili simboli in uscita
• ${\displaystyle S=\{s_{1},s_{2},\ldots ,s_{h}\}}$ insieme finito degli stati
• ${\displaystyle f:I\times S\rightarrow S}$ funzione di transizione degli stati interni successivi, che collega lo stato nell'istante successivo al valore attuale all'ingresso e allo stato attuale, ${\displaystyle S(t+1)=f(I(t),S(t))}$
• ${\displaystyle g:I\times S\rightarrow U}$ funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, ${\displaystyle U(t)=g(I(t),S(t))}$

Automa a stati finiti non deterministico

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

• ${\displaystyle I=\{i_{1},i_{2},\ldots ,i_{n}\}}$ insieme finito dei possibili simboli in ingresso
• ${\displaystyle U=\{u_{1},u_{2},\ldots ,u_{m}\}}$ insieme finito dei possibili simboli in uscita
• ${\displaystyle S=\{s_{1},s_{2},\ldots ,s_{h}\}}$ insieme finito degli stati
• ${\displaystyle 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).
• ${\displaystyle g:I\times S\rightarrow U}$ funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, ${\displaystyle 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 da ASFND ad ASFD attraverso il metodo di costruzione per sottoinsiemi. 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.

\	0	1
s0	s2	s1
s1	s2	s1
s2	s2	s1

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.

Varie

• 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 , ma non è lo stato ad essere finito, bensì il numero degli stati. Il concetto di stato finito ricorre in meccanica quantistica e non ha nulla a che vedere con la nozione di automa finito.

Voci correlate

• Automa a stati finiti non deterministico
• Automa a stati finiti probabilistico
• Automa a stati finiti quantistico
• Gioco della vita
• Formica di Langton
• Verifica formale

Altri progetti

Altri progetti

• Wikiversità
• Wikimedia Commons

• Wikiversità contiene risorse sull'automa a stati finiti
• Wikimedia Commons contiene immagini o altri file sull'automa a stati finiti

Collegamenti esterni

• automa a stati finiti, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Denis Howe, Finite State Machine, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky	Grammatica formale	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 proprio della categoria immediatamente sovrastante.