De eindige automaat ( FSM ) is een belangrijke abstractie op die de werking van digitale computers berust . Een FSM bestaat uit een reeks van toestanden , is slechts een daarvan kan zijn "bezet " op een moment , en een aantal regels bepalen welke staat zal bezetten vervolgens worden gebaseerd op die momenteel bezet en een ingang . In een deterministische FSM , elke staat leidt slechts tot een andere staat ( of zelf ) voor elke mogelijke ingang . Ze zijn gemakkelijk op te stellen en te analyseren op papier met cirkels en pijlen . Wat je nodig hebt Potlood Briefpapier Toon Meer Aanwijzingen 1 Teken een cirkel ongeveer 1 cm over op papier om te beginnen staat de FSM vertegenwoordigen . Geven aan dat het de beginsituatie door het tekenen van een pijl ongeveer een centimeter lang naar te wijzen . Schrijf een unieke naam voor de staat binnen de cirkel , een gemeenschappelijke regeling is elke staat een label met " S " en een onderschrift ( bijv. " S0 , S1 , S2 ", enzovoort ) , maar gebruik meer beschrijvende namen voor uw staten als het maakt de FSM makkelijker te begrijpen . kopen van 2 Teken nog een cirkel om een tweede staat te vertegenwoordigen . Schrijf een label voor de tweede staat binnen zijn cirkel . Elke staat moet een "reactie " voor elke mogelijke ingang het zou kunnen ontvangen gedefinieerd . Trekken zo veel pijlen leiden uit de start staat als er mogelijke ingangen , labelen elke pijl met de input het overeenkomt met . Elke pijl moet weer leiden tot de start staat of naar de tweede toestand . Als voorbeeld , stel de machine die toegang hebben tot een mandje van bananen , appels en sinaasappels die het zal halen door een stuk in een tijd totdat het winkelmandje is leeg. Teken een pijl aangeduid met de input " banaan " van de beginsituatie van de tweede staat . Teken nog twee pijlen , die overeenkomt met "apple " en " oranje ", leidt uit de start staat, maar een lus terug naar het. Indien twee of meer pijlen start op dezelfde plaats en eindigen op dezelfde plek als deze , ze combineren om de tekening minder rommelig te maken ; label de enkele pijl met alle ingangen het correspondeert met 3 . Trek meer staten en geef hun pijlen totdat uw machine een toestand waar het de ingangen of de volgorde van de ingangen het is ontworpen om te identificeren heeft ondervonden heeft bereikt . Voor het huidige voorbeeld , opneming van een derde staat en labelen . Teken een " banaan " pijl leidt uit van de tweede staat in de derde , en een " appel /orange " pijl leidt uit van de tweede staat terug in zichzelf . Teken een pijl uit de derde staat die leidt terug naar zichzelf , gelabeld met alle drie soorten fruit . 4 Teken een iets kleinere concentrische cirkel in de derde staat om aan te geven dat het een " accepteren " state . Uw FSM is voltooid , maar wat doet het? Simuleren wat er zou gebeuren voor een paar voorbeeld fruitmanden je make-up , en je zult al snel beseffen dat dit FSM manden die geen 2 bananen ( een mand wordt " geweigerd " wanneer de vrucht opraken zullen afwijzen wanneer de aanvaarding van state isn ' t bezet ) . Deterministische FSM kan veel meer complexe functies hebben dan deze , met meerdere aanvaarden staten en complexe mogelijke wegen .
|