Tem falado muito sobre Finite State Machines hoje em dia em terra JavaScript.
Há uma biblioteca popular chamada XState, com mais de 11000 estrelas em GitHub, que encontrei ultimamente, e continuo a ler sobre ela no Twitter e noutros locais. É um projecto muito fixe.
Conheci as máquinas Finite State e Automata no liceu, há 20 anos atrás, depois conheci-as novamente no meu curso de Design Digital na Universidade.
Este curso de Design Digital tratava de codificação de informação, álgebra booleana, redes combinatórias, circuitos sequenciais, máquinas de estado sequencial, circuitos aritméticos, VHDL, e muito mais.
Encontrei o tópico de Máquinas de Estado Finito aplicadas à Engenharia de Frontend bastante surpreendente, e voltei aos meus livros antigos para ver se conseguia encontrar uma boa explicação sobre eles.
Encontrei muita informação, e claro que, sendo livros de texto, as coisas tornaram-se mais complexas do que o necessário (IMHO). Gosto de simplificar as coisas, e decidi escrever uma pequena explicação para os seres humanos normais, não teórica ou qualquer coisa feita para passar um exame. Coisas que se podem aplicar ao mundo real.
Máquinas de Estado
Antes de analisar o que é uma Máquina de Estado Finita, quero primeiro introduzir o que é uma Máquina de Estado.
O mundo está cheio de máquinas de Estado. Podem ser vistas em todo o lado, mas talvez não as tenha pensado como tal. Depois de ler este tutorial, tenho a certeza que apontará objectos no mundo real dizendo aos seus amigos “isso é uma máquina de estado” (dependendo do nível nerd dos seus amigos).
O exemplo mais popular e comummente encontrado é semáforos.
Em qualquer altura, um semáforo de trânsito tem um estado definido. Tipicamente, também não tem:
- tem a luz verde ligada, e as outras 2 luzes apagadas
- tem a luz vermelha ligada, e as outras 2 luzes apagadas
- como a luz amarela ligada, e as outras 2 luzes apagadas
(Alguns semáforos são ligeiramente diferentes, mas não nos importamos com este exemplo)
Na terminologia das Máquinas do Estado, as luzes acesas ou apagadas são chamadas de saída.
Cada um desses 3 cenários é chamado de estado. O semáforo de trânsito muda de estado quando recebe uma entrada, normalmente apenas um temporizador fixo que decide quanto tempo os semáforos devem ser verdes, amarelos e vermelhos.
O temporizador, neste caso, é a entrada do sistema. Alguns semáforos têm um botão que os peões podem premir para fazer com que o vermelho seja exibido aos carros, e isso seria outra entrada.
Numa máquina de estado, o estado só pode mudar (e nós temos uma transição) em resposta a uma entrada.
Máquinas de estado finito
A nossa máquina de estado de semáforos é dita finita porque temos um número finito de estados.
alguns sistemas podem ter um número infinito de estados.
Como o modelo do ecossistema mundial, ou a vida de um inseto. Não o podemos definir num número finito de estados.
Mas semáforos? Isso é uma coisa simples, e tem 3 estados, como dissemos acima.
Existem muitos mais exemplos de máquinas de estados finitos que poderíamos utilizar:
- uma máquina de venda automática
- um torniquete de entrada do metro
- um sistema de aquecimento
- um sistema automatizado de metro
- um sistema de auto-automático de automóveis
- um elevador
Mas vamos cingir-nos ao nosso exemplo de semáforos, que é muito simples e que podemos raciocinar facilmente.
Modelar uma máquina estatal
De certeza que os semáforos não existem isoladamente. Essa é outra máquina de estado finito, que contém várias máquinas de estado finito diferentes para cada dispositivo de semáforos instalado para cada lado de cada estrada de um cruzamento, que funcionam em sincronia.
Não penses nisso agora. Vamos concentrar-nos em 1 semáforo de tráfego único.
Como dissemos acima, temos 3 estados, que podem chamar verde, vermelho, amarelo.
Temos um estado inicial. Digamos que os nossos semáforos começam, quando os reiniciamos, no green state.
Temos um temporizador que, após 50 segundos de estado verde, move o semáforo para o yellow state. Temos 8 segundos de yellow estado, depois passamos para o estado red, e ficamos ali sentados durante 32 segundos, porque essa estrada é secundária e merece menos tempo de verde. Depois disto, o semáforo volta ao estado verde e o ciclo continua indefinidamente, até a electricidade parar e o semáforo reiniciar quando voltar a receber a energia.
No total, temos um ciclo de 90 segundos.
É assim que podemos modelá-lo:
Podemos também modelá-lo com uma tabela de transição de estados, que mostra o estado em que a máquina se encontra actualmente, qual é a entrada que recebe, qual é o estado seguinte, e a saída:
| State | |||
|---|---|---|---|
| Green | Timer 50s | Yellow | Green light on, outros desligados |
| Yellow | Timer 8s | Red | Yellow light on, others off |
| Red | Timer 32s | Green | Red light on, others off |
No nosso caso simples, dado qualquer estado da máquina temos apenas um estado lógico para ir, por isso a tabela e o gráfico que fiz são muito, muito simples.
Mas quando o seu sistema começa a ficar mais complexo, é muito útil ter tais diagramas e análises no lugar porque pode raciocinar sobre a sua aplicação muito mais facilmente do que simplesmente mantendo tudo na sua cabeça.
Uma Máquina de Estado Finito com Transições de Estado mais complexas
O exemplo acima é muito simples. Vamos agora modelar outra Máquina de Estado Finito.
O nosso cenário do mundo real é este: temos uma casa, com uma porta, 2 botões e 3 luzes.
No estado padrão as luzes estão todas desligadas.
Ao entrar na casa, pode carregar num dos 2 botões de pressão que tem, p1 ou p2. Ao premir qualquer um desses botões, o l1 acende a luz.
Imagine que esta é a luz de entrada, e pode tirar o seu casaco. Uma vez terminado, decide em que quarto quer entrar (cozinha ou quarto, por exemplo).
Se premir o botão p1l1 desliga e l2 acende. Em vez disso, se premir o botão p2l1 desliga e l3 liga.
Pressing another time any of the 2 buttons, p1 ou p2, a luz que está actualmente acesa apagar-se-á, e voltaremos ao estado inicial do sistema.
Esta Máquina de Estado Finito é ligeiramente mais complexa do que a primeira, porque desta vez podemos ter múltiplas vias, dependendo da entrada.
Vamos modelar isto.
Temos basicamente 4 estados:
- sem luzes ligadas
-
l1ligado -
l2ligado -
l3ligado
Temos 2 entradas:
-
p1 p2
Se partirmos do estado inicial, e tentarmos modelar tudo o que pode acontecer dependendo de como as entradas são accionadas ao longo do tempo, acabamos por ter:
Que pode ser resumido utilizando esta tabela:
| State | Next state | ||
|---|---|---|---|
| sem luzes ligadas | p1 pressionado |
l1 ligado |
|
| sem luzes ligadas | p2 press |
l1 turned on |
|
p1 pressed |
l2 ligado |
||
p2 pressionado |
l3 ligado |
||
p1 pressionado |
sem luzes ligado | ||
p2 pressionado |
sem luzes ligadas | ||
l3 ligado |
p1 pressionado |
sem luzes ligadas | |
l3 ligado |
p2 pressed |
no lights turned on |
É uma explicação breve e simples, mas talvez faça as coisas “clicarem”.
h2>Mais tutoriais de computadores:
- Máquinas de Estado Finito
- O Sistema de Número Decimal
- O Sistema de Número Binário
- Números de Conversão de Decimal para Binário
- Lista de caracteres ASCII imprimíveis
- Não-lista de caracteres ASCII imprimíveis
- Como ligar a um Raspberry Pi usando um Mac
- Como assegurar que o Raspberry Pi tem sempre o mesmo endereço IP
- Uma introdução muito breve a COBOL