La macchina a stati finiti ( FSM ) è una astrazione chiave su cui si basa il funzionamento dei computer digitali . Un FSM consiste di un insieme di stati , uno solo dei quali può essere "occupato" alla volta , e un insieme di regole che determinano quale stato sarà occupato prossimo basa su cui è attualmente occupato e un ingresso. In una FSM deterministico , ogni stato porta solo a un altro stato ( o se stesso) per ogni ingresso possibile. Sono facili da disegnare e analizzare su carta utilizzando cerchi e frecce . Cose che ti serviranno Matita

Carta
Mostra più istruzioni
1

disegnare un cerchio di circa 1 cm di diametro sulla carta per rappresentare lo stato di partenza del FSM . Indicare che è lo stato di partenza per disegnare una freccia circa un pollice di lunghezza che punta ad esso . Scrivi un nome univoco per lo stato all'interno del cerchio , uno schema comune è quello di etichettare ogni stato con "S" e un pedice (ad esempio , " S0 , S1 , S2 " e così via ) , ma utilizzare nomi più descrittivi per i vostri stati , se rende più facile il FSM di capire .
2

Disegnare un altro cerchio a rappresentare un secondo stato . Scrivi una etichetta per il secondo stato all'interno della sua cerchia . Ogni stato deve avere una "risposta ", definito per ogni possibile ingresso potrebbe ricevere. Disegna come molte frecce verso l'esterno dello stato di partenza , come ci sono possibili ingressi , l'etichettatura ogni freccia con l'ingresso corrisponde. Ogni freccia deve portare allo stato di partenza o al secondo stato . Per fare un esempio , immaginate la macchina avendo accesso a un paniere di banane , mele e arance che si riprenderà attraverso un pezzo alla volta fino a quando il carrello è vuoto. Disegnare una freccia etichettata con l'ingresso "banana" dallo stato di partenza per il secondo stato . Disegnare altri due frecce , corrispondenti a " mela " e " arancione ", che porta fuori dallo stato di partenza, ma di tornare a essa. Se due o più frecce che partono nello stesso luogo e alla fine nello stesso posto come questo , combinarli per rendere il disegno meno ingombrante ; etichetta la freccia singola con tutti gli input che corrisponde a
3 .

attirare più stati e specificare le loro frecce fino a quando la macchina ha raggiunto uno stato in cui ha incontrato gli ingressi o sequenza di input è stato progettato per identificare . Per l'esempio corrente , disegnare un terzo stato ed etichettarlo . Disegnare una freccia "banana" che porta fuori il secondo stato nel terzo , e una freccia " mela /arancia " che porta fuori il secondo torna stato in se stesso . Disegna una singola freccia dal terzo stato che porta a se stessa , etichettato con tutti e tre i tipi di frutta .
4

Disegnare un cerchio concentrico leggermente più piccolo nel terzo stato per indicare che si tratta di uno stato di " accettare " . Il tuo FSM è completa, ma che cosa fa? Simulare cosa accadrebbe per esempio alcuni cesti di frutta che si fanno , e vi renderete conto rapidamente che questo FSM rifiuterà cesti che non dispongono di 2 banane ( un paniere viene " respinto " se il frutto esaurito quando l' isn stato accettante 't occupato ) . FSM deterministici possono avere funzioni molto più complesse di così , con più stati accettando e complesse possibili percorsi .