Automa a stati finiti

Da Wikipedia, l'enciclopedia libera.

Un automa a stati finiti (ASF) o macchina a stati finiti o FSA (dall'inglese Finite State Automata) è un modello che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo tipo di 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. La rappresentazione grafica di un automa a stati finiti è il grafo.

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 che si contraddistinguono per la loro differente potenza espressiva.

Automa a stati finiti deterministico[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi 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) = f(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) = g(I(t), S(t))

Automa a stati finiti non deterministico[modifica | modifica wikitesto]

Exquisite-kfind.png Per approfondire, vedi 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[modifica | modifica wikitesto]

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 [s1,s2,...,sk] gli stati s1,s2,...,sk raggiungibili con lo stesso ingresso, ovvero quelli che causano l'indeterminatezza dell'automa.

Rappresentazione della funzione di transizione di un ASFD[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  • 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 Automaton), 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.

Voci correlate[modifica | modifica wikitesto]

Applicazioni Software[modifica | modifica wikitesto]

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

Altri progetti[modifica | modifica wikitesto]

Collegamenti esterni[modifica | modifica wikitesto]

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 sottostante.