flowchart TD
I["conjunto inicial:<br/>fecho vazio do estado inicial"] --> Q["entra na fila<br/>e no dicionário"]
Q --> L{"fila vazia?"}
L -->|sim| F["autômato determinístico pronto"]
L -->|não| R["retira um conjunto S"]
R --> M["para cada símbolo a:<br/>primeiro mover por a,<br/>depois fechar sobre transições vazias"]
M --> D{"o conjunto destino<br/>já está no dicionário?"}
D -->|sim| U["reaproveita o estado existente"]
D -->|não| N["cria estado novo<br/>e enfileira o conjunto"]
U --> L
N --> L
1 Módulo 05: Determinização e Minimização — Resumo
Esta é a versão de revisão. Recapitulo aqui, em ritmo de véspera, o que este módulo tem de guardado; nenhuma demonstração aparece por inteiro, e para isso existem a versão completa do material deste módulo e o livro. Use este texto para conferir se você reconstrói de cabeça o caminho que vai do autômato que adivinha até o menor autômato que decide.
Ficou uma pergunta em aberto no módulo anterior: aquela máquina que toma os dois caminhos ao mesmo tempo, muda de estado sem consumir símbolo e aceita a cadeia se algum ramo terminar em estado final — ela reconhece mais coisas do que uma máquina que só sabe seguir em frente? A resposta cabe numa observação incômoda: a simulação que nós mesmos escrevemos, aquela que carrega um conjunto de estados e o atualiza a cada símbolo, não escolhe nada. É determinística. E se é determinística, ela é um autômato determinístico — cujos estados são conjuntos de estados do original.
1.1 A construção de subconjuntos
Essa é a ideia de Michael Rabin e Dana Scott, publicada em 1959, trabalho pelo qual receberam o Prêmio Turing em 1976. Fixando a notação: o não determinístico é N = (Q, \Sigma, \delta, q_0, F), com \delta devolvendo um conjunto; o determinístico é D = (Q', \Sigma, \Delta, s_0, F'), com \Delta devolvendo um estado só. Duas operações já prontas do módulo anterior fazem todo o serviço: o fecho vazio E(S), que junta a S tudo que se alcança sem consumir símbolo, e o movimento
\mathrm{mover}(S, a) = \bigcup_{p \in S} \delta(p, a).
Com elas, o determinístico correspondente cabe em três linhas: os estados são subconjuntos de Q; o inicial é E(\{q_0\}); um conjunto é final quando toca algum final do original; e a transição é \Delta(S, a) = E(\mathrm{mover}(S, a)).
Três detalhes, e cada um corresponde a um erro que aparece todo semestre. A ordem é mover primeiro e fechar depois; quem inverte produz um autômato que rejeita cadeias legítimas, e o defeito é silencioso, porque só aparece em expressões com fecho ou opcional no meio — exatamente as que qualquer especificação léxica usa. O inicial é o fecho de q_0, não q_0 sozinho. E a finalidade exige pelo menos um estado final dentro do conjunto, não todos.
Ao pé da letra, a definição manda construir 2^{|Q|} estados, número sem sentido físico já para um autômato de Thompson de trezentos estados. Ninguém faz isso: gera-se apenas o que é alcançável a partir do inicial, e a peça que faz tudo funcionar é o dicionário que leva cada conjunto ao índice do estado que o representa. É ele que faz dois caminhos distintos chegando ao mesmo conjunto reaproveitarem o mesmo estado; sem ele, qualquer autômato com ciclo geraria uma árvore infinita. Sobre o movimento que dá vazio, há duas convenções — criar um estado de erro absorvente (forma completa, exigida pelo refinamento) ou não declarar a transição (forma parcial, que é o que a representação esparsa faz). As duas reconhecem a mesma linguagem; o que não se pode é oscilar entre elas.
1.2 O preço, e por que ele quase nunca é cobrado
A definição dá de graça o limite superior de 2^n estados, e ele é tranquilizador por ser finito — é isso que garante que a fila esvazia e o algoritmo termina — e alarmante porque com n = 40 já passa de um trilhão. Resta saber se o limite é apertado, e é. Tome a linguagem L_k das cadeias sobre \{a,b\} cujo k-ésimo símbolo contado do fim é a: um não determinístico a reconhece com k+1 estados, e todo determinístico precisa de pelo menos 2^k.
flowchart LR
Q0(("q0<br/>inicial")) -->|"a, b"| Q0
Q0 -->|"a: adivinha que este<br/>é o símbolo de interesse"| Q1(("q1"))
Q1 -->|"a, b"| Q2(("q2"))
Q2 -->|"a, b"| QM(("cadeia de<br/>k-1 estados"))
QM -->|"a, b"| QF(("qk<br/>final"))
O argumento é de contagem e vale a pena guardar, porque é curto: considere as 2^k cadeias de comprimento k; duas delas, diferindo primeiro na posição i, ficam separadas anexando-se i-1 símbolos quaisquer, pois aí a posição i passa a ser a k-ésima do fim, e uma cadeia entra em L_k enquanto a outra não. Se as duas levassem ao mesmo estado, o autômato daria o mesmo veredicto sobre ambas.
Repare no que isso significa para a etapa seguinte. O crescimento exponencial não é defeito do algoritmo de Rabin e Scott — é a diferença de expressividade entre os dois formalismos, e qualquer construção correta pagaria o mesmo. E a minimização não terá o que fazer aqui, porque acabamos de mostrar que aqueles estados são dois a dois distinguíveis.
Então por que a técnica é padrão em compiladores? Porque a explosão exige manter vivas muitas hipóteses não convergentes, e as expressões que a gente escreve de verdade não têm essa característica: os caminhos paralelos que Thompson gera desembocam no mesmo ponto de junção. A classe das letras minúsculas vira cerca de cem estados para dizer “uma letra qualquer” — mas, lida uma letra, o conjunto alcançado é o mesmo seja qual for a letra, e o dicionário descobre isso sozinho. Não confunda “raramente acontece” com “não acontece”: se o seu projeto aceitar expressões escritas por terceiros, imponha um teto de estados com mensagem clara.
1.3 Órfãos e mortos, antes de minimizar
Há um desperdício que nada tem a ver com indistinguibilidade e que precisa sair primeiro. Um estado inalcançável não participa de computação nenhuma; identificá-lo é um percurso a partir do inicial marcando o que se visita, e o que sobra sem marca vai embora. O trabalho real está em renumerar o que resta, e o defeito clássico é esquecer de traduzir os índices que aparecem nos destinos das transições e no registro dos finais. Um estado morto é aquele de onde nenhum final é alcançável: uma vez dentro, a rejeição é certa. Todos os mortos são indistinguíveis entre si e a minimização os funde num só.
flowchart LR
S(("inicial")) -->|a| P(("p"))
S -->|b| S
P -->|b| F(("f<br/>final"))
P -->|a| M(("m<br/>morto"))
M -->|"a, b"| M
F -->|"a, b"| F
O(("o<br/>inalcançável")) -->|a| F
A ordem é fácil de enunciar e fácil de esquecer: inalcançáveis saem antes do refinamento. Um órfão participaria do refinamento como qualquer outro estado, sobreviveria sozinho num bloco e ainda poderia induzir separações que no autômato limpo não existiriam. O resultado continua reconhecendo a linguagem certa e deixa de ser mínimo — correto o bastante para passar nos testes e errado o bastante para quebrar a unicidade, que é justamente o que se quer.
1.4 Quando dois estados são o mesmo
Aqui está o ponto conceitualmente mais difícil. A resposta ingênua olha para dentro do estado: as transições que saem dele, os símbolos que ele aceita, a posição no desenho. Todas erradas do mesmo jeito, porque olham para a estrutura quando a pergunta é sobre comportamento. O critério correto: p e q são indistinguíveis quando, para toda cadeia w, vale \hat\Delta(p,w) \in F se e somente se \hat\Delta(q,w) \in F. O quantificador inclui a cadeia vazia, e já ela diz que final nunca é indistinguível de não final — é por onde o algoritmo começa.
Pare e pense. Determinização e minimização parecem duas etapas da mesma faxina, e não são: uma apenas reorganiza informação, antecipando um cálculo que a simulação fazia a cada entrada; a outra descarta informação, fundindo o que nenhuma continuação separa. Qual é qual? Confundir as duas é o erro conceitual mais comum deste assunto.
Dois estados com as mesmas letras saindo deles podem ser distinguíveis, e dois estados cujas transições apontam para destinos diferentes podem ser indistinguíveis, desde que esses destinos o sejam entre si. É essa circularidade que impede verificação local e obriga a um ponto fixo. Ela se resolve estratificando por comprimento: p e q são (k{+}1)-indistinguíveis exatamente quando são k-indistinguíveis e, para todo símbolo a, os destinos \Delta(p,a) e \Delta(q,a) também são k-indistinguíveis. Basta olhar um passo à frente, sabida a resposta para k. Como a relação é de equivalência, ela particiona os estados, e o autômato quociente toma as classes como estados — bem definido porque destinos de estados indistinguíveis são indistinguíveis.
1.5 O refinamento de partições
O cálculo é o algoritmo de Edward Moore, de 1956, num trabalho sobre o que se descobre de uma máquina sequencial apenas experimentando com ela — nada coincidente. Começa-se com dois blocos, finais e não finais, e a cada rodada calcula-se a assinatura de cada estado: a lista, ordenada pelos símbolos, dos blocos a que suas transições levam. Estados do mesmo bloco com assinaturas diferentes se separam; quando uma rodada não subdivide nada, chegou-se ao ponto fixo, e cada bloco vira um estado do mínimo.
flowchart TD
R["rodada inicial<br/>bloco dos não finais {0, 1, 2, 2'}<br/>bloco dos finais {3}"]
A["primeira rodada<br/>{0, 1} · {2, 2'} · {3}"]
B["segunda rodada<br/>{0} · {1} · {2, 2'} · {3}"]
C["terceira rodada<br/>nenhuma separação nova:<br/>ponto fixo alcançado"]
R -->|"separa quem alcança o final em um passo"| A
A -->|"separa quem alcança o final em dois passos"| B
B --> C
A assinatura é de blocos de destino, não de símbolos. Montá-la com os símbolos para os quais existe transição, ignorando para onde ela vai, produz partição grossa demais, término precoce e linguagem errada — defeito silencioso, porque a linguagem errada costuma ser um superconjunto que passa em muitos testes.
Moore custa da ordem de k\,n^2 com k símbolos, e sua vantagem didática é que a partição de cada rodada é observável. Hopcroft, em 1971, resolve o mesmo problema em k\,n \log n, examinando só os estados com transição entrando no separador e enfileirando sempre o menor pedaço ao dividir um bloco; compensa com milhares de estados. Brzozowski, em 1962, chega ao mínimo revertendo e determinizando duas vezes, com pior caso exponencial.
1.6 Unicidade, e o que ela decide
Entre todos os autômatos determinísticos completos que reconhecem uma linguagem regular, existe um com número mínimo de estados, único a menos de isomorfismo, e ele é o quociente de qualquer autômato completo e acessível daquela linguagem. As hipóteses não são decorativas: sem acessibilidade, dois autômatos reduzidos podem ter tamanhos diferentes; e sem convenção fixa quanto à totalidade, o mínimo completo tem o estado morto e o parcial não, diferença de exatamente um estado que não significa nada.
flowchart LR
E1["primeira expressão"] --> N1["autômato não determinístico"] --> D1["determinizar"] --> A1["remover inalcançáveis"] --> M1["minimizar"] --> C1["numeração canônica"]
E2["segunda expressão"] --> N2["autômato não determinístico"] --> D2["determinizar"] --> A2["remover inalcançáveis"] --> M2["minimizar"] --> C2["numeração canônica"]
C1 --> T{"finalidade e transições<br/>casam estado a estado?"}
C2 --> T
T -->|sim| S["as duas expressões<br/>denotam a mesma linguagem"]
T -->|não| X["existe cadeia que<br/>uma aceita e a outra não"]
Objeto mínimo e único é forma canônica, e é aqui que o teorema vira ferramenta: remova inalcançáveis, minimize e numere canonicamente por percurso em largura visitando os símbolos em ordem. Antes disso, comparar duas expressões só era possível gerando as cadeias que cada uma denota até um comprimento escolhido — evidência frágil, porque duas podem coincidir até dez e divergir em onze. E não aceite igualdade de contagem como prova: dois autômatos mínimos do mesmo tamanho podem reconhecer linguagens completamente diferentes. Decidir se uma linguagem regular é vazia vira verificar se algum final é alcançável; decidir se é infinita, procurar um ciclo num caminho até um final; e detectar duas categorias léxicas sobrepostas vira compor os autômatos por interseção e perguntar se o resultado é vazio — resposta obtida antes de qualquer entrada existir.
1.7 Ver para depurar, e o motor do caso conduzido
A partir daqui os autômatos são produzidos por algoritmo, com centenas de estados, e conferir a tabela vira a tarefa em que a atenção humana falha em silêncio. O olho, por outro lado, é excelente em grafos: percebe num segundo a ilha desconectada, o final sem entrada, o rótulo com uma letra a mais. O formato consagrado é a linguagem DOT, com círculo duplo para finais, seta vinda de nó invisível para o inicial e — detalhe que separa o diagrama útil do borrão — símbolos contíguos de mesmo destino agrupados numa aresta rotulada com a faixa.
Na implementação de referência da Peneira, a minimização declara três operações, e a terceira é a que transforma o teorema de unicidade em verificação executável:
// Minimização por refinamento de partições (algoritmo de Moore).
//
// A ideia: começar supondo que só existem duas classes de estados — finais e
// não finais — e ir separando sempre que dois estados da mesma classe levarem,
// com o mesmo símbolo, a classes diferentes. Quando nenhuma separação nova
// aparece, cada classe vira um estado do autômato mínimo.
Afd minimizar(const Afd& original, std::string nome);Os números medidos fecham o argumento do módulo anterior: as seis categorias léxicas somam mil duzentos e noventa e seis estados por Thompson, trezentos e trinta e dois depois da determinização e vinte depois da minimização. O identificador é o caso mais instrutivo, de duzentos e cinquenta para dois — os dois estados que qualquer pessoa desenharia à mão. E a verificação que vale o módulo inteiro: o autômato do número desenhado à mão lá atrás, com cinco estados, já era mínimo, e sai isomorfo ao que vem pela via automática, que parte de cento e sessenta e oito, determiniza para quarenta e três e minimiza para cinco. Dois caminhos independentes, o mesmo objeto.
Um defeito que só o diagrama revelou. No desenho da categoria de espaço em branco, uma aresta listava as letras n, r e t ao lado do espaço: o analisador da notação tratava a barra invertida seguida de t como remoção de significado especial, devolvendo a letra em vez do caractere de tabulação. Autômato bem formado, determinização e minimização impecáveis sobre ele, testes de estrutura passando — e a linguagem reconhecida errada. Nenhuma bateria de cadeias o pegaria, porque cadeias de teste só verificam o que alguém pensou em testar.
A sua entrega tem a mesma forma, sobre a linguagem que o seu grupo definiu: determinização com tratamento correto das transições vazias, minimização, exportação visual com os diagramas salvos, a tabela de contagem nas três etapas por categoria, e a verificação de que o mínimo aceita e rejeita exatamente o mesmo que o reconhecedor desenhado à mão.
1.8 Síntese
O não determinismo não aumenta o poder de reconhecimento, e a demonstração é construtiva: é a construção de subconjuntos. Os dois pontos em que se erra ao implementá-la são a ordem entre movimento e fecho vazio — mover primeiro — e o estado inicial, que é o fecho do inicial. O preço é exponencial no pior caso, e o pior caso é real, mas quase não aparece em especificações léxicas porque os caminhos paralelos de Thompson convergem e o dicionário percebe isso. A minimização é operação de outra natureza: funde o que nenhuma continuação distingue, critério comportamental e não estrutural, circularidade que o refinamento de Moore resolve estratificando por comprimento. O que dá valor a tudo é a unicidade, porque forma canônica torna decidível a equivalência de linguagens regulares — pergunta que até aqui só sabíamos responder por amostragem, e portanto não sabíamos responder. O módulo seguinte faz a pergunta oposta: não o que essa maquinaria consegue, mas o que ela não consegue, e a resposta virá de algo que já apareceu aqui de passagem — um autômato com n estados, lendo uma cadeia mais longa que n, repete algum estado.