Animador de Autômato Finito

percorra as transições de um AFD em um diagrama de estados ao vivo

Exemplo resolvido — Animador de Autômato Finito

Próximo símbolo	'1'

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

memória finita, cadeias infinitas 🖖

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.

uma ficha, um caminho 🖖

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.

nascido de um modelo de neurônios 🖖

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.

Problema resolvido na íntegra

Por que razão nenhuma máquina finita consegue emparelhar 0s e 1s, independentemente do número de estados que lhe atribua 8 passos
A máquina de paridade nesta página tem dois estados e lê 101101, seis símbolos, sem nunca necessitar de um terceiro. Forneça-lhe seis milhões de símbolos e continuará a precisar de dois. Afinal, o que é que uma máquina com um número fixo de estados não consegue fazer? E como se prova que uma máquina não existe, em vez de simplesmente não se conseguir encontrar uma?
1. Observe a máquina que tem. A paridade começa em e, e cada 1 inverte-a. Seis símbolos mais tarde está de volta a e e a entrada é aceite. Nada se acumulou ao longo do caminho: no símbolo seis, a máquina está exatamente na mesma condição em que poderia ter estado no símbolo um.
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. Esse é todo o recurso disponível. A memória de um DFA é o estado em que se encontra e nada mais. Sem contador, sem pilha, sem fita onde possa escrever. Após ler qualquer prefixo, tudo o que a máquina sabe sobre esse prefixo é qual dos seus k estados ocupa agora.
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. Procure então algo que necessite claramente de mais. Considere as cadeias formadas por um determinado número de zeros seguidos de exatamente o mesmo número de uns. 01 é uma delas, 0011 é outra, 001 não é, nem 0110.
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. Suponha que um DFA com k estados a reconhece. Não pergunte como é a máquina — isso nunca lhe será dito. Basta fornecer-lhe os k+1 prefixos compostos por 0 a k zeros, e registar onde cada um a deixa.
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. Princípio do pombal. Existem mais prefixos do que estados, pelo que dois deles vão parar ao mesmo local. Chame-lhes 0ⁱ e 0ʲ com i menor do que j. A partir desse momento a máquina não consegue distingui-los, e não por estar mal concebida. O estado é tudo o que ela tem, e as duas cadeias conduziram-na ao mesmo.
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. Agora forneça a ambas as continuações a mesma coisa: i uns. Mesmo estado inicial, mesmos símbolos, logo mesmo estado final, logo o mesmo veredito. Não há margem para a máquina fazer qualquer outra coisa.
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. E os dois vereditos têm de ser diferentes. 0ⁱ1ⁱ tem contagens iguais e pertence à linguagem; 0ʲ1ⁱ não, porque j não é i. Uma tem de ser aceite e a outra recusada, mas a máquina dá-lhes a mesma resposta. O que falha é a suposição de que ela existia.
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. Leia novamente o argumento e note o que nunca nele apareceu: um valor de k. Dois, a própria dimensão da máquina de paridade, ou dois mil milhões: k+1 prefixos superam k estados de qualquer das formas. Imponha contudo um limite a n, e a linguagem passa imediatamente a ser de estados finitos: emparelhar até N requer 2N+2 estados, ou seja, 22 para N = 10 e 202 para N = 100.
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
Resposta

Nenhum autómato finito a reconhece, para qualquer dimensão. A prova não precisa de saber como a máquina é construída, apenas que k+1 coisas não podem ocupar k lugares sem que duas delas partilhem um lugar, e que partilhar um estado é esquecer. A máquina de paridade mostra a mesma coisa em miniatura: forneça-lhe 0, depois 00, depois 000, e as três deixam-na em e, porque ela nem sequer analisa os zeros.

O limite máximo é onde reside toda a dificuldade. Emparelhar até N é fácil, com 2N+2 estados, mais um par por cada símbolo que se pretenda alcançar, e essa contagem cresce sem parar, pelo que cada N específico tem uma máquina e nenhuma máquina serve para todos os N. Essa lacuna é o significado de “memória finita”, e é por isso que o passo seguinte após um DFA é definido ao dotá-lo de uma pilha: um armazenamento ilimitado, reintroduzido precisamente porque é esse o custo da sua ausência.

Referências (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

Pela equipa 42Math · Atualizado 2026-06-03

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

termina em 01 - O reconhecedor de sufixo aceita strings que terminam em 01.
rejeitada (termina em 10) - Avance até o fim e a máquina termina em q1 e rejeita, tendo passado pelo estado de aceitação q2 no meio do caminho. Ler um 01 em alguma parte do percurso não é o mesmo que terminar em um. A resposta inteira de um AFD é o estado após o último símbolo, e ele não tem qualquer forma de lembrar que já esteve em um lugar melhor.
quantidade par de uns ✓ - O autômato de paridade aceita strings binárias com um número par de uns.
quantidade ímpar de uns ✗ - Três 1s na entrada, e a máquina de paridade inverte a cada um deles: e, o, o, e, o. Ela termina em o e rejeita. Nada está sendo contado aqui. Dois estados são tudo o que ela possui e tudo de que necessita, pois saber se a contagem até agora é ímpar é a única informação que vale a pena lembrar sobre uma cadeia de qualquer tamanho.
contém 101 ✓ - A máquina chega a s3 no quarto símbolo e então não consegue mais sair: s3 leva a s3 tanto em um 0 quanto em um 1. Passam-se mais três símbolos e o veredito já estava selado para todos eles. Um estado absorvente é a forma como um AFD se compromete com o sim antes que a entrada termine, sem memorizar nada sobre o momento em que isso ocorreu.
sem 101 ✗ - Rejeitado em s2, que a legenda chama de “leu 10 — a um símbolo de distância”. Um 1 a mais no final teria completado o padrão e trancado a máquina definitivamente em s3. O estado em que paramos diz o quão perto chegamos, algo que o bit de aceitar ou rejeitar jamais conseguiria sozinho.