1 Determinização e minimização — Projeto do Professor
Este é o projeto de referência do professor — as tarefas do Projeto Integrador deste módulo resolvidas do começo ao fim, com as decisões justificadas uma a uma. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: a construção que você escreve, o algoritmo de redução que escolhe e o caso de explosão que constrói são seus. O que se copia daqui é o nível de acabamento e o hábito de fazer o próprio sistema reportar o número em vez de contá-lo à mão.
1.1 Visão Geral
Este módulo produz a peça mais reaproveitada de todo o sistema, e a razão é estrutural: o mesmo componente serve ao reconhecimento dos símbolos da própria linguagem, mais adiante, e à compilação dos padrões que quem usa a Peneira escreve nela, no fecho do percurso. Uma peça, dois níveis — um defeito deixado aqui volta duas vezes, e da segunda vez sem se apresentar.
As três tarefas fecham o ciclo que começou com uma expressão escrita em texto. A primeira converte a máquina não determinística do módulo anterior em determinística; a segunda a reduz ao número mínimo de estados; a terceira exige a evidência — equivalência comprovada por comparação sobre cadeias, e um caso de explosão de estados construído de propósito e observado acontecendo.
Uma dívida do segundo módulo é paga aqui. Naquele momento decidimos não expandir o coringa em alternância de todo o alfabeto, porque a árvore ganharia uma centena de folhas por ocorrência. A determinização é o lugar barato para essa expansão: o autômato determinístico já é denso por construção, e uma coluna a mais na tabela custa exatamente uma coluna. É por isso que o alfabeto da determinização é parâmetro — ele fecha o mundo sobre o qual “qualquer símbolo” passa a significar alguma coisa.
Todo o conteúdo teórico do módulo tem código: a construção de subconjuntos e a equivalência entre as duas famílias, a explosão de estados com as condições em que se manifesta, a relação de indistinguibilidade e a minimização por refinamento de partições. O código compila com avisos tratados como erro e roda pelo subcomando que este módulo acrescenta, sexto teste da bateria.
1.2 Tarefa 1: Converter a máquina para a forma determinística
O que a tarefa pede
Implementar a conversão da máquina não determinística em uma máquina determinística equivalente. Esta é a peça mais reaproveitada de todo o sistema, e a razão é estrutural: o mesmo componente serve ao reconhecimento dos símbolos da própria linguagem, mais adiante, e à compilação dos padrões que o usuário escreve nela, no fecho. Uma peça, dois níveis.
05_determinizacao.h
// 05_determinizacao.h — Construção de subconjuntos e minimização.
//
// A peça mais reaproveitada do sistema. O mesmo componente serve, adiante, ao
// reconhecimento dos símbolos da própria linguagem e, no fecho, à compilação dos
// patterns que quem usa a Peneira escreve nela. Uma peça, dois níveis — o que
// torna cada defeito deixado aqui um defeito que aparece duas vezes, em
// contextos que parecem não ter relação um com o outro.
//
// UMA DÍVIDA DO SEGUNDO ARCO É PAGA AQUI. Naquele momento decidimos NÃO expandir
// o coringa em alternância de todo o alfabeto, porque a árvore ficaria com uma
// centena de folhas por ocorrência. A determinização é o lugar barato para essa
// expansão: o AFD já é denso por construção, e uma coluna a mais na tabela não
// custa nada além da própria coluna. É por isso que o alfabeto da determinização
// é um parâmetro — ele fecha o mundo sobre o qual "qualquer símbolo" significa
// alguma coisa.
#ifndef PENEIRA_05_DETERMINIZACAO_H
#define PENEIRA_05_DETERMINIZACAO_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
#include "04_afn.h"
namespace peneira {
struct ResultadoDaDeterminizacao {
Afd afd;
std::size_t estadosDoAfn = 0;
std::size_t estadosDoAfd = 0;
// Para cada estado do AFD, o conjunto de estados do AFN que ele representa.
// Guardado porque é a evidência de que a construção é o que diz ser: um
// estado do AFD é literalmente um subconjunto de estados do AFN.
std::vector<std::vector<Estado>> subconjuntos;
};
struct ResultadoDaMinimizacao {
Afd afd;
std::size_t estadosAntes = 0;
std::size_t estadosDepois = 0;
// Quantos blocos a partição tinha em cada rodada de refinamento. A última
// rodada não muda nada — é ela que prova que o ponto fixo foi atingido.
std::vector<std::size_t> blocosPorRodada;
};
// Os símbolos concretos que aparecem nas transições do AFN, em ordem. O coringa
// não entra: ele não é símbolo, é a promessa de casar qualquer um deles.
std::string alfabetoDoAfn(const Afn& afn);
ResultadoDaDeterminizacao determinizar(const Afn& afn, const std::string& alfabeto);
ResultadoDaMinimizacao minimizar(const Afd& afd);
// Compara duas máquinas sobre um conjunto de cadeias e devolve a primeira em que
// discordam, ou cadeia vazia se concordaram em todas. É a verificação de
// equivalência que a tarefa exige — por comparação, e nunca por inspeção do
// diagrama, que é a forma mais confiável de concordar consigo mesmo.
struct Discordancia {
bool houve = false;
std::string cadeia;
bool primeiraAceitou = false;
bool segundaAceitou = false;
};
Discordancia compararSobre(const Afd& primeira, const Afd& segunda,
const std::vector<std::string>& cadeias);
Discordancia compararSobre(const Afn& afn, const Afd& afd,
const std::vector<std::string>& cadeias);
// Gera todas as cadeias até um comprimento sobre um alfabeto. Uma bateria
// exaustiva pequena vale mais do que uma amostra grande e enviesada: se duas
// máquinas concordam em TODAS as cadeias até comprimento seis, a chance de
// diferirem só a partir da sétima é remota — e o argumento por construção cobre
// o resto.
std::vector<std::string> todasAsCadeias(const std::string& alfabeto,
std::size_t comprimentoMaximo);
} // namespace peneira
#endif // PENEIRA_05_DETERMINIZACAO_H05_determinizacao.cpp
#include "05_determinizacao.h"
#include <algorithm>
#include <map>
namespace peneira {
std::string alfabetoDoAfn(const Afn& afn) {
std::vector<char> vistos(256, 0);
std::string alfabeto;
for (Estado estado = 0; estado < afn.quantidadeDeEstados(); ++estado) {
for (const TransicaoAfn& transicao : afn.transicoesDe(estado)) {
if (transicao.simbolo == kEpsilon || transicao.simbolo == kQualquer) {
continue;
}
const std::size_t byte = static_cast<unsigned char>(transicao.simbolo);
if (!vistos[byte]) {
vistos[byte] = 1;
alfabeto += transicao.simbolo;
}
}
}
std::sort(alfabeto.begin(), alfabeto.end());
return alfabeto;
}
namespace {
// O conjunto de estados alcançáveis a partir de `conjunto` consumindo `simbolo`,
// já com o fecho vazio aplicado. É a única operação da construção de
// subconjuntos, e ela devolve o conjunto ORDENADO — a ordem é o que permite usar
// o conjunto como chave e reconhecer que já foi visto.
// recorte:inicio avancar-e-expandir-o-coringa
std::vector<Estado> avancar(const Afn& afn, const std::vector<Estado>& conjunto,
const char simbolo) {
std::vector<Estado> alcancados;
for (const Estado estado : conjunto) {
for (const TransicaoAfn& transicao : afn.transicoesDe(estado)) {
// O coringa casa qualquer símbolo do alfabeto fechado aqui. É a
// expansão que o segundo arco adiou, feita no lugar onde custa uma
// coluna de tabela em vez de uma centena de folhas de árvore.
const bool casa = transicao.simbolo == simbolo || transicao.simbolo == kQualquer;
if (casa) {
alcancados.push_back(transicao.destino);
}
}
}
std::vector<Estado> resultado = afn.fechoVazio(alcancados);
std::sort(resultado.begin(), resultado.end());
resultado.erase(std::unique(resultado.begin(), resultado.end()), resultado.end());
return resultado;
}
// recorte:fim avancar-e-expandir-o-coringa
} // namespace
ResultadoDaDeterminizacao determinizar(const Afn& afn, const std::string& alfabeto) {
ResultadoDaDeterminizacao resultado;
resultado.estadosDoAfn = afn.quantidadeDeEstados();
// recorte:inicio subconjunto-vira-estado
// Cada estado do AFD É um subconjunto de estados do AFN. O mapa guarda os
// subconjuntos já vistos; encontrá-lo de novo não cria estado novo, e é
// essa reutilização que faz a construção terminar — o número de
// subconjuntos distintos é finito, ainda que grande.
std::map<std::vector<Estado>, Estado> indiceDoSubconjunto;
std::vector<std::vector<Estado>> subconjuntos;
std::vector<std::vector<Estado>> pendentes;
std::vector<Estado> inicialDoAfn = afn.fechoVazio({afn.inicial()});
std::sort(inicialDoAfn.begin(), inicialDoAfn.end());
indiceDoSubconjunto[inicialDoAfn] = 0;
subconjuntos.push_back(inicialDoAfn);
pendentes.push_back(inicialDoAfn);
// recorte:fim subconjunto-vira-estado
// Tabela de destinos, montada antes de o Afd existir: o construtor do Afd
// exige saber quantos estados haverá, e só sabemos isso no fim.
std::vector<std::vector<Estado>> destinos;
// Marca de "sem destino" para distinguir do estado zero, que é legítimo.
constexpr Estado kSemDestino = static_cast<Estado>(-1);
while (!pendentes.empty()) {
const std::vector<Estado> atual = pendentes.back();
pendentes.pop_back();
const Estado origem = indiceDoSubconjunto[atual];
if (destinos.size() <= origem) {
destinos.resize(origem + 1, std::vector<Estado>(alfabeto.size(), kSemDestino));
}
for (std::size_t coluna = 0; coluna < alfabeto.size(); ++coluna) {
const std::vector<Estado> proximo = avancar(afn, atual, alfabeto[coluna]);
// recorte:inicio conjunto-vazio-e-o-erro
if (proximo.empty()) {
// Conjunto vazio: no AFD isso é o estado de erro, que o
// construtor já cria. Deixamos a posição sem destino.
continue;
}
// recorte:fim conjunto-vazio-e-o-erro
auto encontrado = indiceDoSubconjunto.find(proximo);
Estado indice = 0;
if (encontrado == indiceDoSubconjunto.end()) {
indice = subconjuntos.size();
indiceDoSubconjunto[proximo] = indice;
subconjuntos.push_back(proximo);
pendentes.push_back(proximo);
} else {
indice = encontrado->second;
}
if (destinos.size() <= origem) {
destinos.resize(origem + 1, std::vector<Estado>(alfabeto.size(), kSemDestino));
}
destinos[origem][coluna] = indice;
}
}
destinos.resize(subconjuntos.size(), std::vector<Estado>(alfabeto.size(), kSemDestino));
Afd afd(alfabeto, subconjuntos.size(), 0);
for (std::size_t origem = 0; origem < subconjuntos.size(); ++origem) {
for (std::size_t coluna = 0; coluna < alfabeto.size(); ++coluna) {
if (destinos[origem][coluna] != kSemDestino) {
afd.definirTransicao(origem, alfabeto[coluna], destinos[origem][coluna]);
}
}
// Um estado do AFD aceita quando o subconjunto que ele representa contém
// o estado de aceitação do AFN. Aceitação por existência de caminho, do
// arco anterior, virada propriedade do conjunto.
for (const Estado estadoDoAfn : subconjuntos[origem]) {
if (estadoDoAfn == afn.aceitacao()) {
afd.marcarAceitacao(origem);
break;
}
}
std::string nome = "{";
for (std::size_t i = 0; i < subconjuntos[origem].size(); ++i) {
if (i > 0) {
nome += ",";
}
nome += std::to_string(subconjuntos[origem][i]);
}
nome += "}";
afd.nomearEstado(origem, nome);
}
resultado.afd = afd;
// COM o estado de erro, para ficar na mesma unidade que a minimização
// reporta. Contar os subconjuntos e comparar com os blocos da partição faria
// a minimização parecer AUMENTAR o número de estados numa máquina já mínima
// — defeito observado antes de as duas contagens serem uniformizadas.
resultado.estadosDoAfd = afd.quantidadeDeEstados();
resultado.subconjuntos = subconjuntos;
return resultado;
}
ResultadoDaMinimizacao minimizar(const Afd& afd) {
ResultadoDaMinimizacao resultado;
const std::size_t total = afd.quantidadeDeEstados(); // já inclui o de erro
const std::string& alfabeto = afd.alfabeto();
resultado.estadosAntes = total;
// recorte:inicio particao-inicial-aceita-ou-nao
// Refinamento de partições. A partição inicial separa o que a linguagem já
// distingue sem consumir símbolo algum: aceita ou não aceita. Dois estados
// no mesmo bloco são indistinguíveis ATÉ AQUI; cada rodada testa se algum
// símbolo os separa, e quem se separa forma bloco novo.
std::vector<std::size_t> bloco(total, 0);
for (std::size_t estado = 0; estado < total; ++estado) {
bloco[estado] = afd.ehDeAceitacao(estado) ? 1 : 0;
}
std::size_t quantidadeDeBlocos = 2;
resultado.blocosPorRodada.push_back(quantidadeDeBlocos);
// recorte:fim particao-inicial-aceita-ou-nao
while (true) {
// recorte:inicio assinatura-refina-a-particao
// A assinatura de um estado é o bloco em que ele está mais o bloco para
// onde cada símbolo o leva. Dois estados com a mesma assinatura
// permanecem juntos; assinaturas diferentes separam.
std::map<std::vector<std::size_t>, std::size_t> blocoDaAssinatura;
std::vector<std::size_t> novoBloco(total, 0);
std::size_t novosBlocos = 0;
for (std::size_t estado = 0; estado < total; ++estado) {
std::vector<std::size_t> assinatura;
assinatura.push_back(bloco[estado]);
for (const char simbolo : alfabeto) {
assinatura.push_back(bloco[afd.transicao(estado, simbolo)]);
}
// recorte:fim assinatura-refina-a-particao
auto encontrado = blocoDaAssinatura.find(assinatura);
if (encontrado == blocoDaAssinatura.end()) {
blocoDaAssinatura[assinatura] = novosBlocos;
novoBloco[estado] = novosBlocos;
++novosBlocos;
} else {
novoBloco[estado] = encontrado->second;
}
}
resultado.blocosPorRodada.push_back(novosBlocos);
if (novosBlocos == quantidadeDeBlocos) {
// Ponto fixo: uma rodada que não separa ninguém prova que nenhum
// símbolo distingue dois estados do mesmo bloco, e é isso que a
// definição de máquina mínima pede.
break;
}
bloco = novoBloco;
quantidadeDeBlocos = novosBlocos;
}
// Reconstrução: um estado por bloco. O bloco que contém o antigo estado de
// erro precisa virar o estado de erro do novo autômato, e o construtor
// sempre põe o erro no último índice — então renumeramos os blocos para que
// o do erro seja o último.
const std::size_t blocoDoErro = bloco[afd.estadoDeErro()];
std::vector<std::size_t> novoIndice(quantidadeDeBlocos, 0);
std::size_t proximo = 0;
for (std::size_t b = 0; b < quantidadeDeBlocos; ++b) {
if (b != blocoDoErro) {
novoIndice[b] = proximo++;
}
}
novoIndice[blocoDoErro] = quantidadeDeBlocos - 1;
Afd minimo(alfabeto, quantidadeDeBlocos - 1, novoIndice[bloco[afd.estadoInicial()]]);
std::vector<char> jaTratado(quantidadeDeBlocos, 0);
for (std::size_t estado = 0; estado < total; ++estado) {
const std::size_t destinoDoBloco = novoIndice[bloco[estado]];
if (jaTratado[bloco[estado]]) {
continue;
}
jaTratado[bloco[estado]] = 1;
for (const char simbolo : alfabeto) {
const Estado alvo = afd.transicao(estado, simbolo);
if (bloco[alvo] != blocoDoErro) {
minimo.definirTransicao(destinoDoBloco, simbolo, novoIndice[bloco[alvo]]);
}
}
if (afd.ehDeAceitacao(estado)) {
minimo.marcarAceitacao(destinoDoBloco);
}
minimo.nomearEstado(destinoDoBloco, "b" + std::to_string(destinoDoBloco));
}
resultado.afd = minimo;
resultado.estadosDepois = quantidadeDeBlocos;
return resultado;
}
std::vector<std::string> todasAsCadeias(const std::string& alfabeto,
const std::size_t comprimentoMaximo) {
std::vector<std::string> cadeias{std::string{}};
std::vector<std::string> nivel{std::string{}};
for (std::size_t comprimento = 0; comprimento < comprimentoMaximo; ++comprimento) {
std::vector<std::string> proximo;
for (const std::string& base : nivel) {
for (const char simbolo : alfabeto) {
proximo.push_back(base + simbolo);
}
}
cadeias.insert(cadeias.end(), proximo.begin(), proximo.end());
nivel = proximo;
}
return cadeias;
}
Discordancia compararSobre(const Afd& primeira, const Afd& segunda,
const std::vector<std::string>& cadeias) {
Discordancia discordancia;
for (const std::string& cadeia : cadeias) {
const bool a = primeira.aceita(cadeia);
const bool b = segunda.aceita(cadeia);
if (a != b) {
discordancia.houve = true;
discordancia.cadeia = cadeia;
discordancia.primeiraAceitou = a;
discordancia.segundaAceitou = b;
return discordancia;
}
}
return discordancia;
}
// recorte:inicio comparar-maquina-com-maquina
Discordancia compararSobre(const Afn& afn, const Afd& afd,
const std::vector<std::string>& cadeias) {
Discordancia discordancia;
for (const std::string& cadeia : cadeias) {
const bool a = afn.aceita(cadeia);
const bool b = afd.aceita(cadeia);
if (a != b) {
discordancia.houve = true;
discordancia.cadeia = cadeia;
discordancia.primeiraAceitou = a;
discordancia.segundaAceitou = b;
return discordancia;
}
}
return discordancia;
}
// recorte:fim comparar-maquina-com-maquina
} // namespace peneiraA construção tem uma ideia só, e ela cabe numa frase: um estado do autômato determinístico é um subconjunto de estados do não determinístico. Guardamos os subconjuntos no resultado justamente para que essa frase seja verificável em vez de acreditável — a demonstração imprime, para a primeira expressão, qual conjunto cada estado representa, e ali se lê que o estado zero é o fecho vazio do inicial, com seis estados dentro.
O que faz a construção terminar é o mapa de subconjuntos já vistos. Reencontrar um conjunto não cria estado novo, e como o número de subconjuntos distintos de um conjunto finito é finito, a fila de pendentes acaba. Grande, mas finito — e é exatamente essa fronteira entre “finito” e “grande” que a terceira tarefa vai iluminar.
Duas decisões merecem justificativa. A primeira é o conjunto ordenado como chave: ordenar e remover duplicatas antes de consultar o mapa é o que faz {0,2,4} e {4,0,2} serem reconhecidos como o mesmo estado. Sem a ordenação, a construção não termina — ela cria um estado novo para cada ordem em que os mesmos elementos aparecerem, e o número de ordens é fatorial. Com dez estados no conjunto, são 3.628.800 maneiras de escrever a mesma coisa, e o programa se dispõe a escrever todas. É o defeito mais caro deste módulo, e ele se manifesta como programa que não para.
A segunda é o conjunto vazio virando o estado de erro já existente, em vez de um estado próprio. O autômato determinístico do módulo anterior já nasce com erro absorvente e função total; um conjunto vazio de estados ativos é precisamente isso. Reaproveitar em vez de criar mantém as duas peças com a mesma semântica de recusa, e é o que permite comparar as três máquinas com o mesmo código de teste.
Repare no tratamento do coringa dentro da função que avança o conjunto: ele casa qualquer símbolo do alfabeto fechado. A decisão adiada três módulos atrás é paga aqui, com uma linha, e no lugar onde ela custa o mínimo. Esse é o formato que uma decisão adiada deve ter — registrada onde foi tomada, paga onde é barata, e não descoberta por acidente.
Onde é fácil errar. Esquecer o fecho vazio depois de avançar sob o símbolo. O conjunto alcançado por uma transição precisa ser fechado antes de virar estado, senão o autômato determinístico “perde” os caminhos que dependem de transições vazias posteriores. Como verificar que está correta: compare o número de estados do determinístico com o do não determinístico numa expressão pequena e confira, à mão, que o estado inicial é o fecho vazio do inicial do não determinístico — se ele tiver um único elemento numa expressão que começa com alternância, o fecho faltou.
1.3 Tarefa 2: Reduzir a máquina ao número mínimo de estados
O que a tarefa pede
Implementar a redução ao número mínimo de estados. É o que transforma um reconhecedor correto porém caro em algo utilizável, e é também o primeiro momento em que o sistema devolve um número que mede o efeito de uma decisão sua. O próprio sistema deve reportar a contagem antes e depois: um número que só existe quando alguém se lembra de contá-lo à mão vale como impressão, e nunca como medida — ele deixa de ser produzido exatamente nas ocasiões em que seria mais interessante, que são aquelas em que o resultado surpreende.
Implementamos o refinamento de partições, e a escolha se justifica pelo que ele torna observável. A partição inicial separa o que a linguagem já distingue sem consumir símbolo algum — aceita ou não aceita —, e cada rodada pergunta se algum símbolo separa dois estados que ainda estavam juntos. Quem se separa forma bloco novo. Quando uma rodada não separa ninguém, o ponto fixo foi atingido, e a demonstração imprime a sequência de contagens rodada a rodada para que isso seja visto: dois blocos, três, quatro, cinco, cinco. A última repete a anterior, e é ela que prova a parada. A rodada que não faz nada é a única que demonstra alguma coisa.
A assinatura de um estado é o bloco em que ele está mais o bloco para onde cada símbolo o leva. Dois estados com a mesma assinatura permanecem juntos; assinaturas diferentes separam. Essa é a relação de indistinguibilidade implementada literalmente, e é o motivo de o algoritmo estar correto: no ponto fixo, nenhum símbolo distingue dois estados do mesmo bloco, que é a definição de estados equivalentes.
A reconstrução tem um detalhe que custa uma leitura atenta. O bloco que contém o antigo estado de erro precisa virar o estado de erro do novo autômato, e o construtor sempre põe o erro no último índice — então os blocos são renumerados para que o do erro caia lá. Sem esse cuidado, a máquina mínima teria um estado de erro no meio da numeração e outro, vazio, no fim.
Um defeito que este módulo produziu. A primeira versão reportava “AFD 4 → mínimo 5” para uma expressão simples: o sistema sustentava, com todas as letras, que reduzir uma máquina a torna maior. Não havia erro no algoritmo — as duas contagens estavam em unidades diferentes, porque a determinização contava subconjuntos (sem o estado de erro) e a minimização contava blocos (com ele). O número absurdo apareceu porque o sistema o reportava; contado à mão, ele teria sido “conferido” e a inconsistência sobreviveria. É a razão pela qual o enunciado insiste na instrumentação, e a demonstração agora declara na primeira linha que as contagens de determinístico e mínimo incluem o estado de erro e a do não determinístico não — porque num autômato não determinístico a ausência de transição já significa caminho morto.
Os números do ciclo completo dizem para onde a redução foi: a expressão de endereço com sinal opcional sai de oitenta e quatro estados no não determinístico para vinte e três no determinístico e quatro no mínimo. A maior parte da redução veio da minimização, não da determinização — e ela vem das classes de símbolos expandidas em alternâncias no módulo dois, que produzem dezenas de estados indistinguíveis entre si.
Onde é fácil errar. Parar o refinamento na primeira rodada que produz o número de blocos esperado, em vez de na primeira que não separa ninguém. As duas coincidem quase sempre e divergem justamente nas máquinas em que a redução importa. Como verificar que está correta: confira que a sequência de contagens termina com dois números iguais. Se o último for diferente do penúltimo, o algoritmo parou cedo.
1.4 Tarefa 3: Evidenciar a equivalência e o crescimento de estados
O que a tarefa pede
Demonstrar que a máquina reduzida aceita exatamente a mesma linguagem que a original, por comparação sobre um conjunto de cadeias — nunca por inspeção visual do diagrama, que é a forma mais confiável de concordar consigo mesmo. E construir, de propósito, um caso de crescimento acentuado no número de estados, observando-o acontecer: o fenômeno é conhecido em teoria e raramente é vivido.
A equivalência é verificada por comparação exaustiva sobre cadeias curtas, e não por amostragem. Geramos todas as cadeias até um comprimento sobre o alfabeto da máquina e submetemos as três às mesmas — não determinística, determinística e mínima. Cento e vinte e sete cadeias para a primeira expressão, mil trezentas e sessenta e cinco para a segunda. Se duas máquinas concordam em todas as cadeias até comprimento seis, a chance de diferirem só a partir da sétima é remota, e o argumento por construção cobre o resto. Uma amostra grande e enviesada vale menos: ela tende a conter as cadeias em que quem escreveu já pensou.
Repare que a comparação é feita nos dois saltos, e não só nas pontas. Comparar apenas a não determinística com a mínima esconderia dois erros que se cancelam, e erros que se cancelam sobre uma bateria são justamente os que sobrevivem até o fim.
O caso de explosão é a expressão que descreve a linguagem “o enésimo símbolo contado do fim é um a”. Ela é reconhecível por um não determinístico pequeno porque ele pode adivinhar onde começa o sufixo relevante; um determinístico não adivinha, e precisa lembrar os últimos n símbolos lidos para responder — o que exige 2^n situações distintas.
Os números confirmam a previsão estado a estado. O não determinístico cresce de seis em seis; o determinístico tem a parte que cresce dobrando a cada incremento, e para n = 8 chega a duzentos e cinquenta e oito estados contra cinquenta e dois do não determinístico. A conta fecha em 2^n + 2 no determinístico e 2^n + 1 no mínimo. Um dos estados que sobram acima do piso de 2^n é o de erro — o único que não faz nada e ainda assim entra na conta, e que o construtor cria sempre, seja ele alcançável ou não.
E aqui está a razão de a terceira tarefa pedir a minimização junto: o mínimo acompanha o determinístico, duzentos e cinquenta e sete contra duzentos e cinquenta e oito. Se a explosão fosse desperdício da construção de subconjuntos, a minimização a desfaria. Ela não desfaz, e isso prova algo mais forte do que o algoritmo ser ineficiente — prova que a linguagem exige 2^n estados de qualquer autômato determinístico, e que o punhado acima disso é convenção de representação, não desperdício da construção. É a diferença entre “meu programa está gastando demais” e “nenhum programa determinístico gasta menos que 2^n”, e só a medição com a máquina mínima ao lado separa as duas.
Onde é fácil errar (ao concluir). Achar, ao ver o crescimento, que a determinização foi mal implementada. É a reação natural, e a minimização é o que a refuta. Como verificar que está correta: construa o caso com n crescente e confira que o número de estados do mínimo dobra junto com o do determinístico. Se o mínimo ficar pequeno enquanto o determinístico explode, o problema é seu; se os dois dobram, o problema é da linguagem — e aí a decisão passa a ser sobre quais padrões o seu sistema aceita, e não sobre como ele os compila.
1.5 Por que as duas famílias reconhecem a mesma classe
A equivalência entre as duas famílias de máquinas se demonstra por construção. A analogia é tentadora, soa convincente e não prova nada.
A analogia diria: o não determinístico e o determinístico “fazem a mesma coisa de jeitos diferentes”, e a bateria de cadeias confirma. Só que a bateria confirma para as cadeias testadas, e uma linguagem tem infinitas. O que a bateria pega é erro de transcrição; o que ela não pode pegar é uma diferença que só apareça em cadeias mais longas do que as testadas.
A demonstração por construção é outra coisa, e o código deste módulo é ela. Um lado da equivalência é trivial: todo autômato determinístico já é um não determinístico — aquele em que cada conjunto de destinos tem exatamente um elemento e não há transição vazia. Nada a construir: o determinístico já vinha sendo não determinístico o tempo todo, sem nunca exercer o direito.
O lado interessante é o outro, e é o algoritmo que escrevemos. Ele exibe, para cada não determinístico, um determinístico que aceita a mesma linguagem, e o argumento que sustenta isso é uma invariante: após consumir um prefixo qualquer, o estado em que o determinístico se encontra representa exatamente o conjunto de estados em que o não determinístico poderia estar. Vale para o prefixo vazio, porque o estado inicial é definido como o fecho vazio do inicial; e se vale para um prefixo, vale para ele mais um símbolo, porque é assim que a função que avança o conjunto foi escrita. Por indução sobre o comprimento, vale para todo prefixo — inclusive para a cadeia inteira, que é onde a aceitação é decidida. E o determinístico aceita quando o conjunto contém o estado de aceitação, que é precisamente o critério de aceitação por existência de caminho do módulo anterior.
Repare que esse argumento não menciona nenhuma cadeia específica, e é isso que o torna uma demonstração. A bateria exaustiva continua valendo a pena por outra razão: ela verifica que o código escrito realiza o algoritmo argumentado, e é aí que moram os defeitos reais — o fecho vazio esquecido, o conjunto não ordenado, o coringa não tratado.
A minimização tem um argumento da mesma natureza, e ele também é acessível. Cada rodada de refinamento só separa estados; nunca junta. Um estado separado do outro numa rodada permanece separado em todas as seguintes, porque a assinatura que os separou continua diferente. Logo a sequência de partições é monótona, o número de blocos nunca decresce, e como ele é limitado pelo número de estados, o processo termina. No ponto fixo, dois estados no mesmo bloco têm a mesma assinatura sob todo símbolo — ou seja, nenhuma cadeia os distingue, que é a definição de indistinguíveis. Fundir indistinguíveis não muda a linguagem; e como nenhum par restante é indistinguível, não há o que fundir a mais.
Os dois argumentos cabem em um parágrafo cada, e o lugar deles é o diário da construção. Um algoritmo cuja correção você consegue argumentar é um algoritmo que você consegue depurar quando ele falhar — e o dia em que ele falhar é o dia em que a bateria não vai bastar.