Emanuele Scapin - Automi a stati finiti

Definizione 1: Un automa a stati A è una quadrupla A = < Q , S , d , qo >, dove Q è un insieme di stati, S è un alfabeto finito di simboli di ingresso,
d: Sx Q-->Q è la funzione di transizione, che associa ad ogni coppia (x, q), con x Î S e q Î Q, uno stato y Î S , qo?Q è lo stato iniziale.

Se l’insieme Q è finito, l’automa è detto a stati finiti.

All’arrivo di un simbolo di S, l’automa effettua una transizione, cambiando lo stato. All’inizio del funzionamento l’automa si trova nello stato iniziale, ogni volta il nuovo stato è ottenuto applicando la funzione di transizione alla coppia formata dallo stato attuale e dal simbolo appena letto.

La funzione d: SxQ?Q può essere estesa a d: S*xQ?Q : se la parola w?S*, costituita da simboli dell’alfabeto di ingresso, identifica la sequenza di messaggi inviati, d(ws, q) è lo stato in cui si trova il sistema, inizializzato con q, dopo aver ricevuto w. La funzione d: S*xQ?Q è definita induttivamente da:
1. d(e, q) = q
2. d(ws ,q)= d(s,d(w,q),) per ogni w?S*.
Dopo la lettura della stringa w l’automa è quindi nello stato d(w,q).

Gli automi a stati finiti possono essere quindi implicitamente definiti dando la funzione di transizione attraverso una tabella delle transizioni oppure attraverso un diagramma degli stati.

Si può ben capire che molti dei dispositivi utilizzati nella vita quotidiana possono essere schematizzati tramite un automa a stati finiti.
Di più si può certamente affermare che le macchine utensili prodotte da così tante aziende italiane e fiore all’occhiello dell’industria di esportazione veneta e vicentina in particolare possono essere schematizzate con automi a stati finiti e questi possono trovare largo uso nel facilitare la stesura dei programmi software di gestione e controllo di tali macchine.
Vediamo quindi alcuni facili esempi di automi cercando di proporre una soluzione software che lo implementi.

Esempio 1: Si propone di implementare il più intuitivo e facile degli automi, quello del semaforo.
Questa implementazione può essere trasposta, in un itis, anche nella produzione di un circuito elettrico che tramite timer e led colorati riproduca il funzionamento di un semaforo.

Il semaforo italiano ha tre colori, rosso, arancione e verde, questi scattano in successione dopo lo scadere di un intervallo di tempo. Si può intuire quindi che l’alfabeto di stati in ingresso è qui sostituito da lo scadere di un intervallo di tempo.
Se i colori sono tre, e scattano in successione si può ben pensare che ogni stato sia rappresentato da un colore.

Le transizioni degli stati in questo caso avvengono allo scadere di un intervallo di tempo t, questo facilita la stesura del diagramma.

Esempio di implementazione in Pascal

Esempio di implementazione in Delphi

Esempio di implementazione in Delphi con più di 3 stati