Automa a stati finiti
left|WikiLettera
Questo articolo è solo un abbozzo (stub). Se puoi contribuisci adesso a migliorarlo secondo le convenzioni di Wikipedia.
Per l'elenco completo degli stub, vedi la relativa categoria
Un automa a stati finiti è un sistema dinamico, invariante, discreto nell'avanzamento e nelle interazioni.
- dinamico: evolve nel tempo passando da uno stato all'altro in funzione dei segnali d'ingresso e dello stato precedente;
- invariante: a parità di condizioni iniziali il comportamento del sistema è sempre lo stesso;
- discreto: le variabili d'ingresso, di stato, d'uscita, possono assumere solo valori discreti.
Definizione formale
Un automa a stati finiti si definisce come un sistema A = {I, U, S, f, g}, dove
- I = {i1, i2, ... in} è l'insieme finito dei possibili simboli in ingresso
- U = {u1, u2, ..., um} insieme finito dei possibili simboli in uscita
- S = {s1, s2, ..., sh} insieme finito degli stati
- f = I × S → 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))
- g = I ×S → S funzione di transizione degli stati interni successivi (eventualmente parziale), che collega lo stato nell'istante successivo al valore attuale dell'ingresso e dello stato, S(t+1)=g(S(t), I(t))