Autômato finito determínisco e não determinístico

Última atualização: 2/4/2011

A idéia desta página não é explicar a teoria toda e sim disponibilizar uma máquina de estados para teste de autômatos, você pode entender a idéia dos autômatos começando a leitura por aquiopen in new window e se achar interessante, ler mais sobre aquiopen in new window, aquiopen in new window e aquiopen in new window.

É um assunto obrigatório para quem um dia pensa em programar circuitos digitais ou para quem vai se aventurar na área de linguagens formais. Aliás, para você que utiliza expressões regulares e não sabe, autômatos são fundamentais na codificação de reconhecedores de expressões regulares.

Na máquina abaixo declare os parâmetros para tentar reconhecer uma palavra. Há também um conversor de autômato não deterministico que pode converter seu autômato para uma versão determística. As máquinas abaixo já estão preenchidas com um exemplo, fique à vontade para testar!

Máquina de estados finita determinística

Autômato finito determinístico AFD = (Σ, S, s0, δ, F)
={}
(estados do autômato separados por vírgula)
={}
(alfabeto separado por vírgula)
={}
(estado inicial)
={}
(estados finais separados por vírgula)
(funções de transição, separadas por linha no formato: estado atual > caractere consumido > próximo estado)
=""
(palavra para teste)

Conversor de autômato finito não determinístico

AFND para AFD
={}
(estados do autômato separados por vírgula)
={}
(alfabeto separado por vírgula)
={}
(estado inicial)
={}
(estados finais separados por vírgula)
(funções de transição, separadas por linha no formato: estado atual > caractere consumido > próximo estado)
Log
Ao testar uma palavra, os passos para reconhecimento serao exibidos aqui