A máquina de estados finitos (FSM ) é uma abstração chave em que a operação de computadores digitais se baseia. Uma FSM é constituído por um conjunto de estados , dos quais apenas um pode ser "ocupado " em um momento, e um conjunto de regras que determinam qual estado será ocupada próxima com base no qual é atualmente ocupado e uma entrada . Em um FSM determinista, cada Estado só leva a um outro Estado ( ou o próprio ) para cada entrada possível. Elas são fáceis de desenhar e analisar em papel, utilizando círculos e flechas. Coisas que você precisa Lápis
Papel
Show Mais instruções
1
Desenhe um círculo de cerca de 1 polegada de diâmetro em seu papel de representar estado inicial do FSM . Indicar que é o estado inicial , desenhando uma seta sobre uma longa apontando polegadas a ele. Escreva um nome exclusivo para o Estado dentro do círculo ; um regime comum é rotular cada estado usando o " S " e um índice (por exemplo, " S0, S1 , S2 " e assim por diante ), mas usar nomes mais descritivos para seus estados se faz o FSM mais fácil de entender .
2
Desenhe outro círculo para representar um segundo estado . Escrever um rótulo para o segundo estado dentro de seu círculo. Cada estado deve ter uma "resposta ", definida para cada entrada possível que possa receber . Desenhe como muitas setas que levam para fora do estado inicial , pois há possíveis entradas , rotulando cada seta com a entrada corresponde. Cada seta deve levar de volta para o estado inicial ou para o segundo estado . Como exemplo , imagine a máquina ter acesso a uma cesta de bananas , maçãs e laranjas que ele vai escolher através de uma peça de cada vez até que o carro está vazio. Desenhe uma seta rotulada com a entrada de "banana " a partir do estado inicial para o segundo estado . Desenhe mais duas setas , correspondente a " maçã " e " laranja ", levando para fora do estado inicial , mas looping de volta a ele. Se duas ou mais setas começam no mesmo lugar e terminar no mesmo lugar como este , combiná-los para fazer o desenho menos confuso ; rotular a seta única com todos os insumos que corresponde a
3.
Desenhe mais estados e especificar suas flechas até sua máquina atingiu um estado em que encontrou as entradas ou seqüência de entradas que se destina a identificar . Para o exemplo atual , desenhe um terceiro estado e rotulá-la . Desenhe uma seta "banana" que levam para fora do segundo para o terceiro estado , e um " maçã /laranja" arrow que levam para fora do segundo estado de volta para si mesmo. Desenhe uma única flecha do terceiro estado levando de volta para si mesma, rotulados com os três tipos de frutas.
4
Desenhe um pouco menor círculo concêntrico no terceiro estado para indicar que é um estado de " aceitar " . O FSM é completo , mas o que ele faz? Simule o que aconteceria por algumas cestas exemplo frutas que você faz , e você vai logo perceber que este FSM rejeita cestas que não têm 2 bananas ( uma cesta é " rejeitado ", se o fruto esgotar quando o isn estado de aceitação ' t ocupada ) . FSMs determinísticas pode ter muito mais complexas funções do que este , com vários estados de aceitação e caminhos complexos possíveis .
