Hvordan lage en deterministisk endelig tilstandsmaskin
Den endelig tilstandsmaskin (FSM) er en nøkkel abstraksjon på hvilken driften av digitale datamaskiner er basert på. En FSM består av et sett av stater, bare en av dem kan bli "okkupert" av gangen, og et sett med regler som bestemmer hvilken stat vil bli okkupert neste basert på som er for tiden opptatt og en inngang. I en deterministisk FSM, hver stat bare fører til en annen stat (eller seg selv) for hver mulig inngang. De er enkle å tegne og analysere på papir ved hjelp av sirkler og piler.
Bruksanvisning
1 Tegn en sirkel ca 1 tomme over på papir til å representere FSM begynner tilstand. Tyder på at det er starttilstanden ved å tegne en pil omtrent en tomme lang peke på den. Skriv inn et unikt navn for staten inne i sirkelen; en felles ordning er å merke hver stat med "S" og senket (f.eks "S0, S1, S2" og så videre), men bruker mer beskrivende navn for din stater hvis det gjør FSM lettere å forstå.
2 Tegn en sirkel for å representere en annen stat. Skriv en etikett for den andre staten inne i sin sirkel. Hver stat må ha et "svar" er definert for alle mulige innspill det kan få. Tegn så mange piler som fører ut av starttilstanden som det er mulige innganger, merking hver pil med innspill det tilsvarer. Hver pil må føre tilbake til utgangstilstand eller til den andre tilstanden. Som et eksempel, tenk at maskinen har tilgang til en kurv av bananer, epler og appelsiner som det vil plukke gjennom en brikke om gangen til kurven er tom. Tegn en pil merket med input "banana" fra starttilstanden til den andre staten. Tegn to piler, tilsvarende "eple" og "oransje", som fører ut av starttilstanden, men looping tilbake til det. Hvis to eller flere piler starter på samme sted, og ender på samme sted som dette, kombinere dem for å gjøre tegningen mindre rotete; merke én pil med alle innganger det tilsvarer.
3 Tegn flere stater og spesifisere sine piler inntil maskinen har nådd en tilstand der det har oppstått inn- eller sekvens av innganger det er utformet for å identifisere. For inneværende eksempel tegne en tredje stat og merk den. Tegn en "banan" pil som fører ut av den andre tilstanden til den tredje, og en "apple / orange" pil som fører ut av den annen tilstand tilbake inn i seg selv. Trekke en enkelt pil fra den tredje tilstand som fører tilbake til seg selv, merket med alle tre typer frukt.
4 Tegn en litt mindre konsentrisk sirkel i tredje stat for å indikere at det er en "godta" tilstand. Din FSM er ferdig, men hva gjør det? Simulere hva som ville skje for et par eksempel fruktkurver du gjør opp, og du vil raskt innse at dette FSM vil avvise kurver som ikke har 2 bananer (en kurv er "avvist" hvis frukten renne ut når akseptere staten isn 't okkupert). Determinis FSMs kan ha langt mer komplekse funksjoner enn dette, med flere akseptere stater og komplekse mulige veier.
Hint
- Prøv å lage en FSM som vil nå sitt akseptere staten bare når den mottar flere innganger i en bestemt rekkefølge (hint: bruk pilene som fører tilbake til start staten til å "nullstille" FSM etter en delvis ferdig sekvens).