Autômatos e Linguagens Formais

2026-07-26 compiladores, algoritmos teoria-da-computacao basico

Autômatos e Linguagens Formais

Um autômato finito é o modelo de computação mais simples que existe: memória constante, uma passada pela entrada. Apesar da limitação, ele descreve exatamente o poder das expressões regulares e é a base de analisadores léxicos, validadores de protocolo e busca de padrões.

Alfabetos e linguagens

Um alfabeto $\Sigma$ é um conjunto finito de símbolos; uma cadeia é uma sequência finita deles; uma linguagem é um conjunto de cadeias.

$\Sigma^*$ denota todas as cadeias sobre $\Sigma$, incluindo a vazia $\varepsilon$.

Autômato finito determinístico

Uma quíntupla $(Q, \Sigma, \delta, q_0, F)$: estados, alfabeto, função de transição, estado inicial e estados de aceitação.

O autômato lê a entrada símbolo a símbolo e aceita se termina em estado de $F$. Note o que ele não tem: nenhuma memória além do estado atual. Com $|Q|$ estados, ele distingue no máximo $|Q|$ situações diferentes.

def aceita(delta, q0, finais, cadeia):
    q = q0
    for c in cadeia:
        q = delta.get((q, c))
        if q is None:
            return False
    return q in finais

Custo: $O(n)$ em tempo e $O(1)$ em espaço. É por isso que autômatos são usados em processamento de fluxo — validar um bilhão de linhas não exige memória crescente.

Não determinismo

Um AFN pode ter várias transições para o mesmo símbolo e transições vazias. Ele aceita se algum caminho leva a estado final.

O resultado central: AFD e AFN reconhecem exatamente as mesmas linguagens. A construção de subconjuntos converte um AFN de $n$ estados num AFD de até $2^n$ estados.

O não determinismo não acrescenta poder, mas acrescenta concisão — e essa explosão exponencial é exatamente a razão de algumas expressões regulares causarem lentidão catastrófica.

Expressões regulares

O teorema de Kleene garante a equivalência: uma linguagem é reconhecida por autômato finito se e somente se é descrita por expressão regular.

Operações: união, concatenação e fecho de Kleene.

Um alerta prático importante: as "expressões regulares" da maioria das linguagens de programação não são regulares. Retrovisores (\1) e lookahead acrescentam poder além dos autômatos finitos, e são implementados por retrocesso — o que abre a porta para ReDoS, negação de serviço por expressão regular. Um padrão como (a+)+b sobre uma entrada de 30 letras a pode levar horas.

Motores baseados em autômatos (RE2, o motor de regex do Rust, grep) garantem tempo linear ao custo de não suportar retrovisores. Em código que processa entrada não confiável, essa é a escolha certa.

Lema do bombeamento

Para provar que uma linguagem não é regular. Se $L$ é regular, existe $p$ tal que toda cadeia $s \in L$ com $|s| \ge p$ se decompõe em $s = xyz$ com $|y| > 0$, $|xy| \le p$ e $xy^iz \in L$ para todo $i \ge 0$.

A intuição é a casa dos pombos: com mais símbolos que estados, algum estado se repete, e o trecho entre as repetições pode ser bombeado.

Exemplo: $L = {a^nb^n}$ não é regular. Tomando $s = a^pb^p$, o trecho $y$ está inteiramente nos $a$; bombeando, desequilibra-se a contagem.

Este resultado explica por que não se deve analisar HTML ou linguagens balanceadas com expressão regular. Balanceamento exige contagem ilimitada, e autômatos finitos não contam.

Hierarquia de Chomsky

Tipo	Linguagem	Reconhecedor	Exemplo
3	Regular	Autômato finito	Identificadores, números
2	Livre de contexto	Autômato com pilha	Expressões aninhadas
1	Sensível ao contexto	Autômato linearmente limitado	$a^nb^nc^n$
0	Recursivamente enumerável	Máquina de Turing	Tudo computável

A hierarquia é estrita: cada nível é estritamente mais poderoso.

Em compiladores, a divisão é direta: o analisador léxico usa linguagens regulares (identificadores, números, operadores) e o sintático usa livres de contexto (estrutura aninhada). Verificações que exigem contexto — como "a variável foi declarada" — ficam para a análise semântica, porque estão além do que a gramática expressa.

Propriedades de fechamento

Linguagens regulares são fechadas para união, interseção, complemento, concatenação, fecho e reverso.

O fechamento por complemento é útil na prática: para verificar se um autômato aceita algo que não deveria, complementa-se e testa-se vaziedade. É a base de várias ferramentas de verificação de protocolo.

Minimização

Todo AFD tem um AFD mínimo único (a menos de renomeação), obtido fundindo estados indistinguíveis. O algoritmo de Hopcroft roda em $O(n\log n)$.

A relação "ser indistinguível" é uma relação de equivalência, e a minimização é o cálculo de suas classes — uma aplicação direta do conceito de partição.

Exemplo trabalhado

Autômato que aceita cadeias sobre ${0,1}$ com número par de zeros.

Dois estados: $q_0$ (par, aceitação) e $q_1$ (ímpar).

Estado	0	1
$q_0$	$q_1$	$q_0$
$q_1$	$q_0$	$q_1$

O símbolo 1 não altera o estado; o 0 alterna. Note que dois estados bastam para uma propriedade sobre cadeias de comprimento ilimitado — o autômato guarda apenas a paridade, não a contagem.

Aplicações em computação

Análise léxica. Ferramentas como lex e flex geram autômatos a partir de expressões regulares.

Busca em texto. Knuth-Morris-Pratt e Aho-Corasick constroem autômatos para busca em tempo linear.

Validação de protocolo. Máquinas de estado descrevem estados válidos de TCP, de uma conexão TLS ou de um fluxo de pedido.

Verificação de modelos. Propriedades temporais viram autômatos sobre palavras infinitas.

Interfaces. Fluxos de navegação e estados de componente são máquinas de estado.

Erros comuns

Analisar linguagens aninhadas com regex.
Expor regex com retrocesso a entrada não confiável (ReDoS).
Supor que a regex da linguagem é regular.
Confundir não determinismo com aleatoriedade.
Esquecer o caso da cadeia vazia ao projetar autômatos.

Leituras recomendadas

Sipser, Introduction to the Theory of Computation, capítulo 1 — a melhor introdução; clara e rigorosa.
Hopcroft, Motwani e Ullman — cobertura mais ampla, com muitos algoritmos.
Russ Cox, "Regular Expression Matching Can Be Simple And Fast" — por que autômatos vencem retrocesso; leitura essencial.
Documentação do RE2 e do crate regex do Rust — garantias de tempo linear na prática.

Michael Sipser (2012). Introduction to the Theory of Computation. Cengage Learning. ISBN 9781133187790. John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Pearson. ISBN 9780321455369.

Referências

Michael Sipser (2012). Introduction to the Theory of Computation. Cengage Learning.
John E. Hopcroft; Rajeev Motwani; Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Pearson.