Autômatos finitos: a teoria que você usa todo dia sem perceber

Na primeira aula de Linguagens Formais e Autômatos, a pergunta aparece antes mesmo da chamada:

“Professor, pra que eu vou usar isso na vida?”

É uma pergunta justa. A disciplina tem fama de ser só teoria: estados, símbolos, conjuntos, demonstrações. Mas a verdade é que você usa autômatos finitos todos os dias, em quase todo programa que escreve. Só não sabia o nome.

Toda vez que você valida um CEP, escreve uma expressão regular ou compila um programa, tem um autômato trabalhando por baixo. Hoje a gente vai entender o que ele é, ver um funcionando passo a passo e implementar um do zero.

O que é um autômato finito

Um autômato finito é uma máquina abstrata muito simples, que lê uma palavra um símbolo por vez e, no final, responde só uma coisa: aceito ou rejeito.

Ele é formado por cinco peças:

• um conjunto finito de estados (desenhados como círculos);
• um alfabeto, os símbolos que ele sabe ler;
• as transições, setas que dizem “estando neste estado e lendo este símbolo, vá para aquele estado”;
• um estado inicial, onde a leitura começa (marcado com uma seta vinda do nada);
• um ou mais estados finais (desenhados com círculo duplo).

A regra do jogo: comece no estado inicial, siga as setas conforme lê cada símbolo e, quando a palavra acabar, olhe onde você parou. Parou num estado final? A palavra é aceita. Caso contrário, é rejeitada.

O “finito” do nome é importante e vamos voltar a ele no fim: a máquina tem um número limitado de estados, e é só isso que ela tem de memória.

Um exemplo para desenhar

O autômato da capa deste artigo tem três estados, q0, q1 e q2, alfabeto a e b:

• de q0, lendo a, vai para q1;
• de q1, lendo a, fica em q1 (o laço);
• de q1, lendo b, vai para q2, que é o estado final.

Que palavras ele aceita? Pense antes de continuar a leitura.

Ele aceita ab, aab, aaab… ou seja, um ou mais a seguidos de exatamente um b. Na notação da disciplina, a linguagem é L = { aⁿb | n ≥ 1 }.

Repare que algumas transições não foram desenhadas: não há seta saindo de q0 com b, nem saindo de q2 com nada. Por convenção, transição que não existe leva a um estado de erro implícito, de onde não se sai mais. A palavra morre ali e é rejeitada.

Lendo uma palavra, passo a passo

Vamos rodar a máquina com a palavra aab:

Passo	Estado atual	Símbolo lido	Próximo estado
1	q0	a	q1
2	q1	a	q1
3	q1	b	q2
fim	q2	(acabou)	q2 é final: aceita

Agora com aaba:

Passo	Estado atual	Símbolo lido	Próximo estado
1	q0	a	q1
2	q1	a	q1
3	q1	b	q2
4	q2	a	não há transição: rejeita

E b sozinho é rejeitado logo no primeiro passo, porque q0 não sabe o que fazer com b.

Percebe como a máquina é “burra” no bom sentido? Ela não volta atrás, não conta, não pensa. Só olha o estado atual e o símbolo, e segue a seta. É essa simplicidade que a torna tão rápida e tão útil.

Implementando em poucas linhas

A tradução para código é quase direta. As transições viram uma tabela, e a leitura vira um laço:

const automato = {
  inicial: 'q0',
  finais: new Set(['q2']),
  transicoes: {
    q0: { a: 'q1' },
    q1: { a: 'q1', b: 'q2' },
    q2: {},
  },
};

function aceita(automato, palavra) {
  let estado = automato.inicial;
  for (const simbolo of palavra) {
    estado = automato.transicoes[estado][simbolo];
    if (estado === undefined) return false; // sem transição: rejeita
  }
  return automato.finais.has(estado);
}

console.log(aceita(automato, 'aab'));  // true
console.log(aceita(automato, 'aaba')); // false
console.log(aceita(automato, 'b'));    // false

Repare no custo: um passo por símbolo, nada mais. Uma palavra de tamanho n é decidida em tempo O(n), com memória constante. Não existe forma mais eficiente de ler uma entrada.

Esse código cabe no Visualizador HTML, se você quiser testar outras palavras sem instalar nada.

Onde ele aparece no mundo real

Expressões regulares

Uma expressão regular clássica e um autômato finito são duas formas de descrever exatamente as mesmas linguagens. Esse é um dos resultados mais bonitos da disciplina, o Teorema de Kleene. A expressão a+b descreve a mesmíssima linguagem do nosso autômato.

Quando você escreve um regex para validar e-mail ou telefone, muitas bibliotecas transformam essa expressão num autômato para rodar a verificação. (As bibliotecas modernas trazem recursos a mais, como backreferences, que vão além do que um autômato finito consegue; mas o núcleo é esse.)

O analisador léxico do compilador

A primeira fase de todo compilador é a análise léxica: transformar uma sequência de caracteres em tokens, como identificadores, números, palavras reservadas e operadores. E cada tipo de token é reconhecido por… um autômato finito.

Veja um que reconhece números como 42 e 3.14:

• q0 (inicial): lendo um dígito, vai para q1;
• q1 (final): lendo dígito, fica em q1; lendo ., vai para q2;
• q2: lendo dígito, vai para q3;
• q3 (final): lendo dígito, fica em q3.

Ele aceita 42 (para em q1), aceita 3.14 (para em q3) e rejeita 3. (para em q2, que não é final). Exatamente a regra que a linguagem de programação define para literais numéricos simples.

Fluxos com estados

Pedido de loja virtual (aguardando pagamento → pago → enviado → entregue), conexão de rede, tela de login com etapas, semáforo, máquina de café. Sempre que um sistema tem estados bem definidos e eventos que mudam de um para outro, você está modelando um autômato. Desenhar o diagrama antes de programar evita a clássica situação do pedido “enviado” que volta para “aguardando pagamento” porque ninguém pensou nessa transição.

O limite do autômato finito

Lembra do “finito”? Ele cobra um preço.

Tente desenhar um autômato que aceite aⁿbⁿ: um número qualquer de a seguido do mesmo número de b (ab, aabb, aaabbb…). Não importa quantos estados você use: para qualquer quantidade finita de estados, existe uma palavra com mais a do que a máquina consegue “contar”.

E isso tem consequência prática enorme: um autômato finito não consegue verificar se os parênteses de uma expressão estão balanceados. Para isso, a máquina precisa de uma memória extra, uma pilha. Esse é o autômato com pilha, que está por trás da análise sintática dos compiladores. Mas isso é assunto para outro artigo.

Desenhe o seu

Autômato se aprende desenhando e testando. No Construtor de Autômatos, gratuito e direto no navegador (inclusive no celular), você cria estados, liga as transições e testa palavras passo a passo: a fita mostra o símbolo lido e o desenho acende o estado atual e a seta usada, exatamente como nas tabelas deste artigo. Os dois autômatos daqui, o de aⁿb e o de números, já estão na lista de exemplos. Abra um, teste aab e aaba, e depois tente desenhar o seu do zero.

Se quiser ir fundo, do autômato finito à máquina de Turing, com o método que uso em sala, o curso de Linguagens Formais e Autômatos cobre a disciplina inteira.

Conclusão

Autômato finito não é teoria descolada da realidade. É o modelo mais simples de computação que existe, e justamente por ser simples, está em todo lugar:

• lê um símbolo por vez e decide em tempo linear;
• é equivalente às expressões regulares;
• é a base da análise léxica de todo compilador;
• e ensina a pensar sistemas como estados e transições.

Da próxima vez que escrever um regex, lembre: tem uma maquininha de círculos e setas trabalhando para você. Programar é um ato de pensar, e entender o que roda por baixo é o que separa quem usa a ferramenta de quem entende a ferramenta.