|
La machine à états finis (FSM ) est une abstraction qui touche le fonctionnement des ordinateurs numériques est basé . Un FSM est constitué d'un ensemble d'états , dont une seule peut être «occupé» à la fois, et un ensemble de règles qui déterminent quel état sera occupé prochaine basé sur qui est actuellement occupé et une entrée . Dans un FSM déterministe , chaque Etat ne mène à un autre Etat ( ou elle-même ) pour chaque entrée possible. Ils sont faciles à dessiner et à analyser sur du papier en utilisant des cercles et des flèches. Choses que vous devez
Crayon
papier
Voir Plus Instructions
1 dessiner un cercle d'environ 1 pouce de diamètre sur le papier pour représenter l'état de départ de la FSM . Indiquent que c'est l'état de départ en tirant une flèche d'environ un pouce pointant longtemps pour elle . Donnez un nom unique pour l'état à l'intérieur du cercle, un schéma commun est d'étiqueter chaque état en utilisant "S" et un indice ( par exemple, « S0 , S1, S2 " et ainsi de suite ), mais utiliser des noms plus descriptifs pour vos états si il rend le FSM facile à comprendre.
2 Dessinez un autre cercle pour représenter un deuxième état . Écrire un label pour le deuxième état à l'intérieur de son cercle . Chaque Etat doit avoir une «réponse» défini pour chaque entrée possible qu'il pourrait recevoir . Tirer autant de flèches menant de l'état de départ car il ya des entrées possibles , l'étiquetage chaque flèche avec l'entrée elle correspond. Chaque flèche doit ramener à l'état initial ou au deuxième état . À titre d'exemple , imaginez la machine ayant accès à un panier de bananes , les pommes et les oranges qui il va chercher à travers un morceau à la fois jusqu'à ce que le panier est vide. Dessiner une flèche marquée par l'entrée "banane" à partir de l'état initial à l'état second . Dessinez deux autres flèches , correspondant à «pomme» et "orange ", menant de l'état de départ, mais le bouclage revenir. Si deux ou plusieurs flèches commencent au même endroit et à la fin dans le même endroit comme celui-ci , de les combiner pour faire le dessin moins encombré ; étiquette sur la flèche simple avec toutes les entrées Il correspond à
3. Dessinez plusieurs Etats et préciser leurs flèches jusqu'à ce que votre machine a atteint un état où il a rencontré les entrées ou une séquence d' entrées , il est conçu pour identifier . Pour notre exemple, dessiner un Etat tiers et l'étiqueter. Dessiner une flèche "banane" qui sort de l'état second dans le troisième , et une flèche " pomme /orange" qui sort de la deuxième retour de l'Etat en lui-même. Dessinez une seule flèche du troisième état ramenant à lui-même , marqué avec les trois types de fruits.
4 Tracez un cercle concentrique légèrement plus petit dans le troisième état pour indiquer qu'il s'agit d'un état " d'accepter " . Votre FSM est terminée, mais que fait-il ? Simuler ce qui se passerait pour un exemple quelques paniers de fruits que vous faites , et vous vous rendrez vite compte que ce FSM va rejeter paniers qui n'ont pas 2 bananes ( un panier est «rejeté» si le fruit de fonctionner quand l'ISN de l'Etat d'accepter 't occupé ) . FSMs déterministes peuvent avoir des fonctions bien plus complexes que cela, avec plusieurs états acceptent et les voies complexes possibles.
|
