Studio e proposta di utlizzo della struttura dati OBDD in alcuni ambiti dell'Informatica

Una macchina a stati niti (FSM) è un modello rappresentabile mediante uno schema composto da un insieme di stati e due funzioni, chiamate funzione di stato futuro e funzione di uscita. L'insieme degli stati corrisponde a tutti i possibili valori degli elementi della memoria interna, perciò in presenza di n bit di memoria vi saranno 2n stati. La funzione di stato futuro, in base al valore dell'ingresso e dello stato presente, calcola il valore del prossimo stato assunto dal sistema. La funzione di uscita invece produce gli output a partire dallo stato presente e dagli ingressi. In particolare, si parla di macchina di Moore quando la funzione di uscita viene limitata in modo da dipendere solo dallo stato presente; si parla invece di macchina di Mealy se la funzione d'uscita dipende sia dallo stato presente che dall'ingresso corrente. Le macchine di Moore sono in genere più veloci, mentre le macchine di Mealy sono più piccole in quanto richiedono un numero minore di stati. È sempre possibile, comunque, convertire l'una nell'altra grazie ad un procedimento automatizzato.