Emanuele Scapin

Un automa a stati finiti può essere rappresentato come una testina che legge da un nastro, spostandosi sempre nella stessa direzione. Il nastro si ritiene di lunghezza illimitata e contenente dei simboli. Ad ogni istante la testina si trova in un determinato stato tra quelli consentiti, a seconda dello stato i cui si trova e del simbolo letto dal nastro, la testina si porta su un altro stato (a meno che non rimanga nello stesso stato) e si sposta per leggere il simbolo successivo.

S₁S₂S₃S₄…
Ý
q

Quando la lettura dei simboli termina, a seconda dello stato raggiunto, l’automa fornisce un risultato.
Si può quindi dire che il comportamento dei un automa è determinato in maniera univoca a partire dallo stato corrente e dal simbolo in lettura.
Come si può ben comprendere il comportamento dell’automa può essere rappresentato da una tabella detta funzione o matrice di transizione degli stati per quanto riguarda il passaggio da uno stato all’altro.