Fondamenti di Informatica

Automa a stati

Reti di Petri C/E con una sola marca che si conserva sono detti macchine o automi a stati.

Con il termine automa s’intende un qualunque dispositivo, un qualunque oggetto, che esegue da se stesso un particolare compito, sulla base degli stimoli od ordini ricevuti. Sono così esempi di automi una lavatrice, un distributore automatico di bibite..ecc E' possibile studiare un automa da due punti di vista: da un punto di vista tecnico ci s’interessa dei suoi componenti materiali, meccanici o elettronici, e dei suoi principi fisici che ne rendono possibile il funzionamento; da un punto di vista matematico c'interessa invece la "logica" del suo comportamento e l’automa è perciò visto come un oggetto astratto "capace" di eseguire qualche compito. Ad esempio, due automi capaci di eseguire un’addizione sono l’automa uomo e l’automa calcolatrice, molto diversi da un punto di vista tecnico-fisico, ma che si comportano nello stesso modo di fronte a due numeri da addizionare. Il grafo, chiamato diagramma degli stati, ha come nodi gli stati possibili dell’automa; gli archi rappresentano le relazioni di passaggio da uno stato all’altro, secondo il particolare input. La matrice, chiamata tabella di verità o degli stati, è una tabella in cui ogni casella specifica qual è il successivo stato e l’output dell’automa se esso si trova in un determinato stato e riceve un certo input. Per esempio osserviamo un distributore automatico di bevande dà una lattina quando s’inseriscono due monete. Il diagrammi degli stati è il seguente:

Nell’arco che va dallo stato di "in attesa" allo stato di "pronto" la scrittura "moneta/lattina" indica che, in corrispondenza dell’input "moneta" è fornito l’output "lattina". Come si vede, non sempre un automa fornisce un output. La tabella di verità è la seguente:

Gli stati di un automa rappresentano i suoi stati di memoria; un automa, infatti, si trova in uno o in un altro stato secondo ciò che è successo in precedenza. Secondo lo stato in cui si trova e dell’input che riceve, l’automa stabilisce il suo comportamento, passando in un nuovo stato ed eventualmente fornendo un output. Gli automi con memoria limitata, e comunque finita poiché hanno un numero finito di stati: sono chiamati automi a stati finiti. Per saperne di più consulta i seguenti aggiornamenti:






















































Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.