Criador de Máquinas de Estados Finitos

Calculadoras relacionadas

• Calculadora de Diagramas de Hasse
• Simulador de Autômatos Celulares
• Analisador de Grafos de Rede
• Calculadora de Tabela de Cayley

O que é uma máquina de estados finitos?

Uma máquina de estados finitos é um modelo que descreve um sistema como um conjunto limitado de estados conectados por transições rotuladas. A máquina começa em um estado, lê uma cadeia de entrada símbolo por símbolo, segue as regras de transição e então aceita ou rejeita a cadeia dependendo do estado em que termina.

Na teoria dos autômatos, esse tipo de máquina de estados finitos costuma ser chamado de autômato finito. Ele é útil porque transforma uma questão sobre padrões em um modelo preciso baseado em grafos. Em vez de dizer “esta cadeia segue a regra”, você pode criar estados para as situações importantes, transições para cada símbolo de entrada e estados de aceitação para as situações que contam como correspondência.

Por exemplo, um autômato finito pode reconhecer se uma cadeia binária termina em 1, se uma palavra contém determinada substring ou se um token simples de uma linguagem de programação tem uma forma válida. A máquina não memoriza toda a entrada. Ela apenas memoriza seu estado atual, por isso os autômatos finitos são poderosos para padrões regulares, mas limitados em tarefas que exigem memória ilimitada.

---

Por que as máquinas de estados finitos são importantes

As máquinas de estados finitos são um dos primeiros modelos formais que os estudantes conhecem na teoria da computação, pois conectam diagramas, tabelas, algoritmos e demonstrações. Um diagrama de estados é visual, mas também pode ser escrito como um objeto matemático preciso. Isso torna os autômatos finitos úteis tanto para o aprendizado quanto para a implementação.

Eles aparecem em áreas práticas como análise léxica, criação de protocolos simples, validação de entrada, fluxos de interface e correspondência de padrões. Também são a base das linguagens regulares e das expressões regulares, ideias centrais em compiladores, processamento de texto e teoria das linguagens formais.

Uma máquina de estados finitos também ajuda a evitar raciocínios vagos. Quando os estados, o alfabeto, o estado inicial, os estados de aceitação e as transições são explícitos, fica mais fácil testar exemplos, encontrar transições ausentes, identificar estados inalcançáveis e comparar duas máquinas que deveriam reconhecer a mesma linguagem.

---

Termos importantes

• Estado: Uma posição ou situação nomeada na máquina, como q0 ou q1.
• Alfabeto: O conjunto de símbolos de entrada que a máquina pode ler, geralmente escrito como \(\Sigma\).
• Cadeia de entrada: Uma sequência finita de símbolos do alfabeto, geralmente escrita como \(w\).
• Estado inicial: O estado onde a simulação começa, geralmente escrito como \(q_0\).
• Estado de aceitação: Um estado final que faz a entrada ser aceita se a máquina terminar nele.
• Transição: Uma seta rotulada de um estado para outro.
• AFD: Um autômato finito determinístico. Para cada estado atual e símbolo de entrada, há no máximo um próximo estado na estrutura de transição simulada.
• AFN: Um autômato finito não determinístico. Ele pode ter mais de um próximo estado possível para o mesmo estado e símbolo, e pode usar transições epsilon.
• Transição epsilon: Uma transição que não consome nenhum símbolo de entrada, geralmente escrita como \(\epsilon\) ou mostrada como eps.
• Fecho epsilon: O conjunto de estados alcançáveis a partir de um estado ou conjunto de estados usando apenas transições epsilon.
• Estado alcançável: Um estado que pode ser visitado a partir do estado inicial seguindo as transições.
• Estado armadilha: Um estado que retorna a si mesmo para cada símbolo do alfabeto; assim, depois que a máquina entra nele, as regras de transição atuais a mantêm ali.
• Linguagem regular: Um conjunto de cadeias que pode ser reconhecido por um autômato finito.
• Expressão regular: Uma forma simbólica de descrever uma linguagem regular usando operações como união, concatenação e estrela de Kleene.

---

Como funcionam os autômatos finitos

Um autômato finito costuma ser descrito como um objeto de 5 partes:

Em que:

• \(Q\) é o conjunto finito de estados.
• \(\Sigma\) é o alfabeto de entrada.
• \(\delta\) é a regra de transição.
• \(q_0\) é o estado inicial.
• \(F\) é o conjunto de estados de aceitação.

Em um AFD completo, a regra de transição informa exatamente para qual estado a máquina deve ir depois de ler um símbolo a partir de determinado estado. Em um diagrama parcial, uma transição ausente significa que não há próximo estado válido para essa etapa. Se a cadeia de entrada é \(w\), a máquina aceita \(w\) quando o estado alcançado depois de ler toda \(w\) está em \(F\).

Uma forma compacta de escrever essa ideia é:

Aqui, \(\hat{\delta}\) significa a regra de transição estendida de um símbolo para uma cadeia inteira.

Os AFNs funcionam de outra forma. Em vez de acompanhar um único estado atual, uma simulação de AFN acompanha um conjunto de estados atuais possíveis. Se transições epsilon forem permitidas, a simulação começa com o fecho epsilon do estado inicial:

Depois de ler o próximo símbolo de entrada \(c\), o novo conjunto de estados possíveis é:

A entrada é aceita se pelo menos um estado atual possível for de aceitação depois que todos os símbolos forem processados:

Essa é a ideia central da simulação de AFN: não é necessário que todos os caminhos possíveis tenham sucesso. A entrada é aceita se pelo menos um caminho válido alcançar um estado de aceitação no final.

Conversão de AFD e AFN

Todo AFN tem um AFD equivalente que reconhece a mesma linguagem. A conversão padrão é chamada de construção por subconjuntos. Cada estado do novo AFD representa um conjunto de estados do AFN original.

Se o AFN tem \(n\) estados, o AFD convertido pode ter teoricamente até:

estados, pois existem \(2^n\) subconjuntos possíveis de um conjunto com \(n\) estados. Em muitos exemplos, apenas um pequeno número desses subconjuntos é alcançável. Em máquinas grandes ou altamente não determinísticas, porém, esse número pode crescer rapidamente.

Minimização de AFD

A minimização de AFD reduz um autômato determinístico a um AFD equivalente com menos estados quando alguns estados se comportam da mesma forma para todas as possíveis continuações da entrada. Uma abordagem comum começa separando os estados de aceitação dos estados de rejeição e depois refina repetidamente esses grupos de acordo com o destino das transições.

A ideia básica é:

1. Colocar os estados de aceitação e os estados que não são de aceitação em grupos separados.
2. Comparar como os estados do mesmo grupo se comportam para cada símbolo do alfabeto.
3. Dividir um grupo quando seus estados fazem transições para grupos diferentes.
4. Repetir até que não sejam encontradas mais divisões úteis.
5. Tratar cada grupo restante como um estado no AFD minimizado.

Um AFD minimizado é mais fácil de analisar porque os comportamentos equivalentes foram reunidos.

Expressões regulares a partir de autômatos

Autômatos finitos e expressões regulares descrevem a mesma classe de linguagens: as linguagens regulares. Uma forma de converter um autômato em uma expressão regular é a eliminação de estados. O método reescreve os caminhos pela máquina enquanto remove estados intermediários, deixando uma expressão regular que descreve as mesmas cadeias aceitas.

A eliminação de estados é mecânica, mas a expressão resultante pode ficar longa. Diferentes ordens de eliminação também podem produzir expressões com aparência diferente para a mesma linguagem. Por isso, a geração de expressões regulares é mais prática para máquinas pequenas.

---

Exemplos práticos de máquinas de estados finitos

Exemplo 1: um AFD que aceita cadeias binárias terminadas em 1

Suponha que o alfabeto seja:

$$ \Sigma = \{0, 1\} $$

Use dois estados:

• q0: a cadeia vista até agora está vazia ou termina em 0.
• q1: a cadeia vista até agora termina em 1.

Seja q0 o estado inicial e q1 o único estado de aceitação.

A tabela de transições é:

Estado atual	Entrada 0	Entrada 1
q0	q0	q1
q1	q0	q1

Para a entrada 101, o caminho é:

$$ q0 \xrightarrow{1} q1 \xrightarrow{0} q0 \xrightarrow{1} q1 $$

A máquina termina em q1, que é um estado de aceitação, portanto 101 é aceita.

Para a entrada 100, o caminho é:

$$ q0 \xrightarrow{1} q1 \xrightarrow{0} q0 \xrightarrow{0} q0 $$

A máquina termina em q0, que não é um estado de aceitação, portanto 100 é rejeitada.

---

Exemplo 2: um AFN com uma transição epsilon

Considere uma máquina com estado inicial q0 e estado de aceitação q1. Se houver uma transição epsilon de q0 para q1, então o fecho epsilon do estado inicial é:

$$ \epsilon\text{-closure}(\{q0\}) = \{q0, q1\} $$

Como o conjunto de estados atual já contém o estado de aceitação q1, a cadeia de entrada vazia é aceita.

Isso é diferente de ler um símbolo real. Uma transição epsilon altera o conjunto de estados possíveis sem consumir um caractere da entrada.

---

Exemplo 3: quando não resta nenhum caminho válido

Suppose the alphabet is:

$$ \Sigma = \{0, 1\} $$

Se a entrada for 102, o símbolo 2 estará fora do alfabeto. A simulação deve rejeitar a entrada porque não há uma regra de transição válida para um símbolo que a máquina não reconhece.

Em um rastreamento de AFN, outro caso extremo comum é o conjunto atual vazio:

$$ S_i = \{\} $$

Isso significa que não resta nenhum caminho possível depois do prefixo de entrada processado até então. Quando o conjunto atual está vazio, a máquina não pode se recuperar depois, a menos que o modelo de simulação forneça explicitamente um caminho, o que uma etapa de transição padrão de autômato finito não faz a partir de nenhum estado.

---

Como interpretar o resultado

Um resultado Aceito significa que a máquina terminou de processar toda a entrada com pelo menos uma possibilidade de aceitação. Para um AFD, isso significa que o único estado final é um estado de aceitação. Para um AFN, significa que o conjunto final de estados possíveis contém pelo menos um estado de aceitação.

Um resultado Rejeitado significa que a entrada não terminou em um estado ou conjunto de estados de aceitação. Também pode significar que a entrada continha um símbolo fora do alfabeto.

Um rastreamento mostra como o estado atual ou o conjunto de estados muda enquanto a entrada é processada. Os conjuntos de estados são exibidos entre chaves, como {q0, q2} ou {}. Para um AFN, uma entrada de rastreamento como {q0, q2} significa que tanto q0 quanto q2 são possíveis depois da etapa de entrada indicada. Uma entrada {} significa que não resta nenhum caminho válido para o prefixo processado.

A análise de determinismo exibida diz respeito à estrutura de transição real. Uma máquina é não determinística se tem uma transição epsilon ou mais de uma transição com o mesmo estado de origem e símbolo. Isso pode ser diferente do modo de edição selecionado se a própria estrutura de transição contiver características não determinísticas.

Estados alcançáveis são estados que podem ser visitados a partir do estado inicial. Estados inalcançáveis ainda podem aparecer em um diagrama, mas não afetam quais cadeias de entrada são aceitas, a menos que o estado inicial ou as transições mudem.

Os estados de AFD criados pela construção por subconjuntos representam conjuntos de estados do AFN original. Um estado de AFD convertido e nomeado com vários estados originais deve ser entendido como “o AFN poderia estar em qualquer um destes estados neste ponto”.

Os grupos de estados minimizados mostram estados que o processo de minimização trata como equivalentes. Se dois estados terminarem no mesmo grupo, o AFD minimizado poderá reuni-los sem alterar a linguagem aceita.

Uma expressão regular gerada descreve a mesma linguagem aceita somente quando a conversão está disponível para o tamanho e a estrutura atuais da máquina.

---

Erros comuns e conceitos equivocados

Um erro comum é colocar eps, epsilon, ε ou uma entrada em branco no alfabeto. Esses rótulos são reservados para transições epsilon. As letras comuns e e E continuam disponíveis como símbolos de entrada.

Outro erro é supor que um AFN aceita somente quando todos os caminhos aceitam. Um AFN aceita quando pelo menos um caminho possível chega a um estado de aceitação depois que toda a entrada é consumida.

Também é fácil confundir o modo AFD ou AFN selecionado com a estrutura de transição real. Um diagrama com transições duplicadas para o mesmo estado e símbolo é não determinístico, mesmo que a intenção fosse criar um AFD. Um diagrama com transições epsilon também é não determinístico.

Quando cada símbolo do alfabeto é um grafema Unicode, o simulador lê uma cadeia comum um grafema por vez; assim, um emoji ou caractere composto conta como um símbolo. Se algum símbolo do alfabeto contiver vários grafemas, informe a entrada de teste como tokens separados por espaços em branco.

Outro problema frequente é esquecer de marcar um estado de aceitação. Uma máquina sem estados de aceitação não pode aceitar nenhuma cadeia de entrada, mesmo que as transições pareçam razoáveis.

Nas transições importadas, os estados referenciados já devem existir. Importar linhas de transição não é o mesmo que importar uma definição completa da máquina com novos estados.

---

Quando usar máquinas de estados finitos

Use máquinas de estados finitos quando um problema puder ser descrito por um número finito de situações e transições símbolo por símbolo.

Os usos comuns incluem:

• Testar se as cadeias correspondem a um padrão regular.
• Aprender o comportamento de AFDs e AFNs na teoria da computação.
• Comparar um diagrama de estados com sua tabela de transições.
• Verificar alcançabilidade, estados armadilha e estados de aceitação.
• Demonstrar como funcionam o não determinismo e as transições epsilon.
• Converter um AFN em um AFD para entender a construção por subconjuntos.
• Minimizar um AFD para simplificar comportamentos equivalentes.
• Explorar a relação entre autômatos finitos e expressões regulares.

As máquinas de estados finitos são especialmente úteis quando a memória importante do sistema pode ser resumida pelo estado atual. Elas não são o modelo adequado quando a tarefa exige uma pilha ilimitada, contagem arbitrária ou memória de uma quantidade ilimitada da entrada anterior.

---

Limitações e pontos importantes

Os autômatos finitos reconhecem linguagens regulares. Eles não conseguem modelar todos os padrões possíveis. Por exemplo, linguagens que exigem corresponder a um número arbitrário de estruturas aninhadas ou pareadas geralmente precisam de um modelo mais poderoso que um autômato finito.

Esta calculadora oferece dois modos explícitos de entrada. Alfabetos com um único grafema usam cadeias comuns; alfabetos que contêm um símbolo com vários caracteres usam tokens de entrada separados por espaços em branco. A tentativa de adivinhar a correspondência mais longa nunca é usada.

Espaços em branco e vírgulas não podem ser símbolos do alfabeto porque delimitam entradas do alfabeto e tokens de entrada com vários caracteres. Os símbolos do alfabeto e a entrada são normalizados para Unicode NFC antes da correspondência.

No modo AFD, transições epsilon e destinos conflitantes para o mesmo estado e símbolo são erros de validação. Arestas duplicadas idênticas são deduplicadas com segurança, mas dados conflitantes nunca são excluídos silenciosamente.

A construção por subconjuntos pode crescer rapidamente. Esta calculadora limita a conversão de AFN para AFD a 32 estados de AFD. Se o limite for atingido, a conversão será marcada como truncada, e as afirmações de minimização e equivalência serão omitidas.

A geração de expressões regulares é limitada a máquinas pequenas. Esta calculadora tenta a eliminação de estados apenas para máquinas com 7 estados ou menos. Se uma expressão regular não for gerada para uma máquina maior, isso representa um limite prático de tamanho, e não uma prova de que não existe uma expressão regular equivalente.

Nas expressões regulares geradas, símbolos de um único caractere que são seguros usam a notação comum. Símbolos com vários caracteres ou de pontuação aparecem como átomos delimitados, como ⟨token⟩, significando um símbolo do alfabeto, e não uma sequência de caracteres.

A exclusão do único estado restante é bloqueada para que a máquina sempre tenha pelo menos um estado. As transições importadas devem fazer referência a estados existentes, e linhas de transição inválidas são ignoradas.

A exportação do grafo e as ações da área de transferência podem depender das permissões e do suporte do navegador. Se essas ações falharem, o autômato em si ainda poderá ser válido.

---

Como usar esta calculadora

1. Escolha o modo AFD ou AFN.
2. Informe o alfabeto como símbolos separados por vírgulas ou espaços em branco. A calculadora indicará se a entrada usa grafemas ou tokens delimitados por espaços em branco.
3. Construa o diagrama de estados adicionando estados, selecionando o estado inicial e marcando os estados de aceitação.
4. Adicione transições escolhendo um estado de origem, um símbolo de transição e um estado de destino, ou edite/importe linhas de transição no formato from, symbol, to.
5. Informe a cadeia de entrada a ser testada.
6. Execute a simulação de uma só vez ou avance por ela um símbolo de cada vez.
7. Revise o resultado, o rastreamento, a análise de determinismo, os estados alcançáveis, os estados armadilha, a conversão para AFD, os grupos minimizados e a saída da expressão regular quando disponíveis.
8. Copie o resumo da máquina ou baixe a imagem do grafo se o seu navegador oferecer suporte a essas ações.

---

Perguntas frequentes

---

Fontes e referências

Livros

1. Michael Sipser. Introduction to the Theory of Computation. 3ª ed., Course Technology/Cengage Learning, 2012. Capítulo 1, “Regular Languages”, especialmente autômatos finitos, não determinismo, expressões regulares e equivalências de linguagens regulares. ISBN 978-1133187790. Página do livro do autor.
2. John E. Hopcroft, Rajeev Motwani e Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 2ª ed., Addison-Wesley, 2001. Capítulos 2–3, “Finite Automata” e “Regular Expressions and Languages”. ISBN 978-0201441246. Registro no Google Books.

Fontes on-line e oficiais

1. JFLAP. “Building Your First Finite Automaton”. Acessado em 28 de junho de 2026.
2. JFLAP. “Converting a NFA to a DFA”. Acessado em 28 de junho de 2026.
3. JFLAP. “Converting a DFA to a Minimal State DFA”. Acessado em 28 de junho de 2026.
4. JFLAP. “Converting a FA to a Regular Expression”. Acessado em 28 de junho de 2026.
5. Jae-Hee Ahn e Yo-Sub Han. “Implementation of State Elimination Using Heuristics”. Implementation and Application of Automata, Lecture Notes in Computer Science, vol. 5642, Springer, 2009, p. 178–187. Springer Link.