The tilstandsmaskine ( FSM ), er en vigtig abstraktion , som driften af digitale computere er baseret på. En MFS består af et sæt af stater, er kun én af dem kan være " besat " på et tidspunkt , og et sæt regler om , hvilken stat vil blive beboet siden baseret på som i øjeblikket besat og en indgang . I en deterministisk MFS , kun hver stat fører til en anden stat (eller sig selv) for hver mulig indgang. De er nemme at tegne og analysere på papir ved hjælp cirkler og pile. Ting du skal
Blyant
Paper
Vis Flere Instruktioner
1
Tegn en cirkel omkring 1 tomme på tværs af på dit papir til at repræsentere MFS s start tilstand. Angiv, at det er den begyndende staten ved at tegne en pil omkring en tomme lang pege på den. Skriv et entydigt navn til staten inde i cirklen , en fælles ordning er at mærke hver stat ved hjælp af " S " og en sænket (fx " S0 , S1 , S2 " og så videre ), men bruger mere beskrivende navne til dine tilstande , hvis det gør MFS lettere at forstå.
2
Tegn en anden cirkel for at repræsentere en anden stat. Skriv en etiket til den anden stat inde i sin kreds . Hver stat skal have en "respons " defineret for alle mulige input det måtte modtage . Trække så mange pile der fører ud af udgangs staten som der er mulige indgange , mærkning hver pil med input svarer det til . Hver pil skal føre tilbage til udgangspunktet stat eller til den anden tilstand. Som et eksempel forestille maskinen har adgang til en kurv af bananer , æbler og appelsiner , som den vil vælge gennem ét stykke ad gangen, indtil kurven er tom. Tegn en pil mærket med indgangen " banan " fra start tilstand til den anden tilstand. Tegn to pile, der svarer til "Apple" og "orange ", der fører ud af start stat, men looping tilbage til det. Hvis to eller flere pile start på samme sted og ende på samme sted som dette , kombinere dem til at gøre tegningen mindre rodet , etiketten enkelt pil med alle de inputs det svarer til
3. .
Tegn flere stater og specificere deres pile , indtil maskinen har nået en tilstand , hvor det er stødt på de input eller sekvens af input det er konstrueret til at identificere. For den nuværende eksempel trækker et tredje stat og mærke det . Tegn en " banan " pil fører ud af den anden stat i den tredje , og en " apple /orange " pil fører ud af den anden stat tilbage i sig selv. Tegn en enkelt pil fra det tredje stat fører tilbage til sig selv, er mærket med alle tre typer af frugt.
4
Tegn en lidt mindre koncentrisk cirkel i tredje stat for at indikere , at det er en " accept " tilstand . Dit MFS er komplet , men hvad gør det? Simulere , hvad der ville ske for et par eksempel frugt kurve , du foretager sig, og du vil hurtigt indse, at dette MFS vil afvise kurve , der ikke har 2 bananer ( en kurv er "afvist ", hvis frugten løbe ud, når den accepterende staten isn 't besat) . Deterministiske FSMs kan have langt mere komplekse funktioner end dette, med flere accepterer stater og komplekse mulige veje.