Animador de Autômato Finito

Um autômato finito tem memória fixa — seu conjunto de estados. Não importa quão longa seja a cadeia de entrada, a máquina nunca usa mais memória do que seu número de estados. É por isso que os AFDs não conseguem contar indefinidamente: não existe um estado que 'memorize' um número inteiro arbitrário. O lema do bombeamento formaliza isso: qualquer cadeia suficientemente longa aceita por um AFD pode ter uma seção intermediária repetida um número arbitrário de vezes e ainda ser aceita. Linguagens que não podem ser bombeadas (como aⁿbⁿ, com quantidades iguais de a e b) exigem um autômato de pilha ou uma máquina de Turing. O teorema de Myhill-Nerode fornece o mínimo exato: o número de estados é igual ao número de classes de equivalência distinguíveis dos prefixos de entrada.

Um autômato finito determinístico é apenas um diagrama rotulado de estados ligados por setas. Para cada estado e cada símbolo de entrada existe exatamente uma seta a seguir, portanto nunca há escolha: a máquina lê a cadeia uma única vez, da esquerda para a direita, e para em um único estado. Se esse estado final estiver marcado como de aceitação, a entrada pertence à linguagem. Segui-lo é tão simples quanto deslizar uma ficha pelas setas — exatamente o que esta ferramenta mostra.

Os autômatos finitos não surgiram na computação. Em 1943, Warren McCulloch e Walter Pitts descreveram os neurônios como simples unidades liga/desliga conectadas entre si, e isso se tornou o primeiro modelo matemático de uma máquina de estados finitos. Em 1951, Stephen Kleene analisou quais padrões essas 'redes nervosas' podiam reconhecer e os chamou de eventos regulares — a origem das expressões regulares de hoje. Então o autômato que você percorre aqui descende diretamente de uma tentativa de explicar como o cérebro calcula.