Cosa sono gli automi a stati finiti?

129 Views 0 Comment

Un automa a stati finiti (ASF) o macchina a stati finiti o FSA (dall’inglese Finite State Automata) è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi.

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.

automi

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:

  • Automi a stati finiti deterministici (ASFD);
  • Automi a stati finiti non deterministici (ASFND).

Automa a stati finiti deterministico

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

  • I = {i1, i2, i3….in} insieme finito dei possibili simboli in ingresso;
  • U = {u1, u2, u3….un} insieme finito dei possibili simboli in uscita;
  • S = {s1, s2, s3….sn} insieme finito degli stati;
  • f : I x S -> S funzione di transizione degli stati interni successivi, che collega lo stato nell’ istante successivo al valore attuale dell’ ingresso e dello stato;
  • g : I x S -> U funzione delle uscite, che collega l’ uscita al valore attuale dell’ ingresso dello stato.

Differenza tra ASFD ed ASFND

La differenza tra i due tipi di automi 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.

 

Nel prossimo articolo spiegheremo passo passo come costruire un automa.

Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Automi.

Alla prossima!


Continua a seguirci su:

Facebook Instagram Telegram Rss