Numexa logoNumexa

Simulador de Autômato Finito

AFD e AFN com diagrama de estados e execução passo a passo.

Use eps ou ε para transição vazia.

010101q0q1q2

Determinístico (AFD) · alfabeto {0, 1} · círculo duplo = estado final

A palavra “1101” é ACEITA.

O simulador de autômato finito desenha o diagrama de estados a partir das transições e mostra, passo a passo, por quais estados a palavra passa. Funciona para AFD e para AFN, inclusive com transições vazias (ε), como nos exercícios de linguagens formais e teoria da computação.

Definição Formal

Um autômato finito é uma 5-upla M = (Q, Σ, δ, q0, F):

  • Q: conjunto finito de estados.
  • Σ: alfabeto de entrada.
  • δ: função de transição (no AFD, δ: Q × Σ → Q).
  • q0: estado inicial.
  • F: conjunto de estados finais (de aceitação).

Exemplo: Palavras que Terminam em 01

q0 0 q1     # leu 0: pode ser o começo de "01"
q0 1 q0
q1 0 q1
q1 1 q2     # leu "01": estado final
q2 0 q1
q2 1 q0

Com a palavra 1101, o caminho é q0 → q0 → q0 → q1 → q2. Como q2 é final, a palavra é aceita.

De AFN para AFD

Pela construção dos subconjuntos, cada estado do AFD equivalente representa um conjunto de estados do AFN. É exatamente o que o simulador mostra na lista de passos: os conjuntos entre chaves são os estados do AFD que seria construído.

Perguntas Frequentes

O que é um autômato finito?

É uma máquina abstrata com um número finito de estados que lê uma palavra símbolo por símbolo e muda de estado conforme regras de transição. Se terminar a leitura em um estado final, a palavra é aceita. Autômatos finitos reconhecem exatamente as linguagens regulares.

Qual a diferença entre AFD e AFN?

No AFD (determinístico), cada estado tem exatamente uma transição para cada símbolo. No AFN (não determinístico), um estado pode ter várias transições com o mesmo símbolo, nenhuma, ou transições vazias (ε). Apesar disso, os dois reconhecem as mesmas linguagens: todo AFN pode ser convertido em um AFD.

Como o simulador executa um AFN?

Ele acompanha o conjunto de todos os estados em que o autômato pode estar ao mesmo tempo, incluindo os alcançáveis por transições vazias (o fecho-ε). A palavra é aceita se, ao final, algum desses estados for final.

Qual a diferença entre autômato finito e máquina de Turing?

O autômato finito só lê a entrada uma vez, da esquerda para a direita, e não tem memória além do estado atual. A máquina de Turing pode ler e escrever em uma fita infinita e se mover nos dois sentidos, o que a torna capaz de computar qualquer coisa computável.

Ferramentas Relacionadas