Come fare un deterministico macchina a stati finiti

January 4

La macchina a stati finiti (FSM) è un'astrazione chiave su cui si basa il funzionamento del 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 prossima basato su attualmente occupati e un ingresso. In un FSM deterministico, ogni stato porta solo a un altro stato (o se stesso) per ogni possibile ingresso. Sono facili da tracciare e analizzare su carta utilizzando cerchi e frecce.

istruzione

1 Disegnare un cerchio di circa 1 pollice attraverso il vostro giornale per rappresentare lo stato di partenza del FSM. Indicare che è lo stato di partenza disegnando una freccia su 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 il FSM più facile da capire.

2 Disegnare un altro cerchio di rappresentare un secondo stato. Scrivi una etichetta per il secondo stato all'interno del suo cerchio. Ogni stato deve avere una "risposta" definito per ogni possibile ingresso potrebbe ricevere. Disegnare il maggior numero di frecce che conducono fuori dallo stato di partenza in quanto vi sono possibili ingressi, etichettando ogni freccia con l'ingresso corrisponde. Ogni freccia deve portare allo stato di partenza o al secondo stato. A titolo di esempio, immaginare la macchina di avere accesso a un cesto di banane, mele e arance, che si prenderà attraverso un pezzo alla volta fino a quando il carrello è vuoto. Disegnare una freccia etichettato con la "banana" input dallo stato iniziale al secondo stato. Disegnare altri due frecce, corrispondente a "mela" e "arancione", che porta fuori dallo stato di partenza, ma di tornare a esso. Se due o più frecce iniziano nello stesso posto e terminano nello stesso posto come questo, combinarle per rendere il disegno meno ingombrante; etichettare la freccia singola con tutti gli ingressi corrisponde.

3 Disegnare 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 ingressi è stato progettato per identificare. Per l'esempio attuale, disegnare un terzo stato ed etichettarlo. Disegnare una freccia "banana" che porta fuori il secondo stato nel terzo, e un "mela / arancio" freccia che conduce fuori del secondo stato di nuovo in sé. Disegnare una freccia singola dal terzo stato che riporta a se stesso, 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 sarebbe successo per un paio di cesti di frutta esempio si fanno, e vi renderete conto rapidamente che questo FSM rifiuterà cesti che non dispongono di 2 banane (un cesto è "rifiutato" se il frutto esaurito quando il isn stato accettando 't occupato). FSM deterministici possono avere funzioni molto più complessa di questa, con più stati accettando e percorsi possibili complessi.

Consigli e avvertenze

  • Provate a fare un FSM che raggiungerà il suo stato accettato solo quando riceve più ingressi in un ordine specifico (suggerimento: utilizzare le frecce che conducono allo stato di iniziare a "resettare" il FSM dopo una sequenza parzialmente completato).

Articoli Correlati