1 Módulo 05: Projeto do Professor — Mil Duzentos e Noventa e Seis Estados Viram Vinte
Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro, com as decisões justificadas uma a uma. Os números da sua linguagem serão outros, mas a forma de conferi-los é a mesma.
1.1 Visão Geral do Módulo 05
O módulo anterior terminou com um constrangimento numérico. Os autômatos gerados pela construção de Thompson para as seis categorias léxicas da Peneira somavam 1296 estados — trezentos e noventa e dois só para reconhecer texto entre aspas. Nenhum deles foi escolhido por alguém; todos vieram das seis regras da construção, aplicadas sem exceção. Este módulo cobra essa conta.
A atividade pede a ferramenta completa: expressão regular entra, autômato determinístico mínimo sai. São três etapas encadeadas — determinizar, minimizar e exportar para visualização — mais a tabela de contagem de estados nas três, e a verificação de que o resultado continua reconhecendo o que o autômato desenhado à mão no módulo 3 reconhecia.
O que torna este módulo diferente dos anteriores é que ele entrega, além de capacidade, uma decisão. Até aqui o projeto sabia construir autômatos e executá-los. A partir da minimização, ele sabe responder se duas especificações descrevem a mesma linguagem — pergunta que o módulo 2 deixou explicitamente em aberto, quando a comparação de linguagens até um comprimento foi apresentada como evidência e não como prova.
1.2 Tarefa 1: A determinização
A atividade — converter o autômato não determinístico em determinístico, tratando corretamente as transições vazias.
A construção de subconjuntos cabe em uma frase: cada estado do autômato resultante é um conjunto de estados do original. E é exatamente o conjunto que a simulação do módulo 4 carregava durante a execução. A diferença é quando o cálculo acontece — lá, a cada entrada processada; aqui, uma vez só, na construção.
05_determinizacao.h
#ifndef PENEIRA_05_DETERMINIZACAO_H
#define PENEIRA_05_DETERMINIZACAO_H
#include <cstddef>
#include <string>
#include "03_afd.h"
#include "04_afn.h"
namespace peneira {
// Construção de subconjuntos: converte o autômato não determinístico no
// determinístico equivalente.
//
// A ideia inteira cabe numa frase: cada estado do autômato resultante é um
// CONJUNTO de estados do original. É exatamente o conjunto que a simulação do
// módulo 4 carregava durante a execução — a diferença é que aqui o cálculo é
// feito uma vez, ainda na construção, e não a cada entrada processada.
Afd determinizar(const Afn& afn, std::string nome);
// Remove os estados que não são alcançáveis a partir do inicial. A construção
// de subconjuntos já produz só estados alcançáveis, mas um autômato escrito à
// mão pode ter estados órfãos, e a minimização precisa deles fora antes de
// começar.
Afd removerInalcancaveis(const Afd& original);
// Quantos estados do autômato dado são inalcançáveis. Usado nos relatórios.
std::size_t contarInalcancaveis(const Afd& original);
} // namespace peneira
#endif // PENEIRA_05_DETERMINIZACAO_H05_determinizacao.cpp
#include "05_determinizacao.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
namespace peneira {
namespace {
// Percorre o autômato a partir do inicial e devolve os estados alcançados.
std::set<Estado> alcancaveis(const Afd& a) {
std::set<Estado> vistos;
if (a.inicial() == kSemEstado) {
return vistos;
}
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
std::vector<Estado> pilha{a.inicial()};
vistos.insert(a.inicial());
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(atual, s);
if (destino != kSemEstado && vistos.insert(destino).second) {
pilha.push_back(destino);
}
}
}
return vistos;
}
} // namespace
Afd determinizar(const Afn& afn, std::string nome) {
Afd resultado(std::move(nome));
if (afn.inicial() == kSemEstado) {
return resultado;
}
const std::vector<Simbolo> alfabeto = afn.simbolosUsados();
// O mapa é a peça central: leva cada conjunto de estados do original ao
// índice do estado que o representa no resultado. É ele que faz dois
// caminhos diferentes que chegam ao mesmo conjunto reutilizarem o mesmo
// estado, em vez de duplicá-lo — e é por isso que o resultado costuma ser
// muito menor que o pior caso teórico.
std::map<std::set<Estado>, Estado> conhecidos;
std::vector<std::set<Estado>> fila;
const std::set<Estado> inicial = afn.fechoVazio(std::set<Estado>{afn.inicial()});
conhecidos[inicial] = resultado.novoEstado(inicial.count(afn.final()) > 0);
resultado.definirInicial(conhecidos[inicial]);
fila.push_back(inicial);
for (std::size_t i = 0; i < fila.size(); ++i) {
const std::set<Estado> atual = fila[i];
const Estado origem = conhecidos[atual];
for (const Simbolo s : alfabeto) {
const std::set<Estado> destino =
afn.fechoVazio(afn.mover(atual, s));
// Conjunto vazio significa que não há para onde ir com este
// símbolo. Não criamos estado para ele: fica como transição
// indefinida, que é o estado de erro implícito da representação
// esparsa adotada no módulo 3.
if (destino.empty()) {
continue;
}
const auto it = conhecidos.find(destino);
Estado indice;
if (it == conhecidos.end()) {
indice = resultado.novoEstado(destino.count(afn.final()) > 0);
conhecidos[destino] = indice;
fila.push_back(destino);
} else {
indice = it->second;
}
resultado.adicionarTransicao(origem, s, indice);
}
}
return resultado;
}
std::size_t contarInalcancaveis(const Afd& original) {
return original.quantidadeDeEstados() - alcancaveis(original).size();
}
Afd removerInalcancaveis(const Afd& original) {
const std::set<Estado> vivos = alcancaveis(original);
Afd resultado(original.nome());
std::map<Estado, Estado> novoIndice;
for (const Estado e : vivos) {
novoIndice[e] = resultado.novoEstado(original.ehFinal(e));
}
if (novoIndice.count(original.inicial()) > 0) {
resultado.definirInicial(novoIndice[original.inicial()]);
}
const std::vector<Simbolo> alfabeto = original.simbolosUsados();
for (const Estado e : vivos) {
for (const Simbolo s : alfabeto) {
const Estado destino = original.transicao(e, s);
if (destino != kSemEstado && novoIndice.count(destino) > 0) {
resultado.adicionarTransicao(novoIndice[e], s,
novoIndice[destino]);
}
}
}
return resultado;
}
} // namespace peneiraRepare que o algoritmo reutiliza sem alteração as duas funções escritas no módulo 4, o fecho vazio e o movimento por símbolo. Não foi sorte: elas foram escritas naquele módulo já sabendo que seriam consumidas aqui, e o comentário no cabeçalho delas dizia isso. Quem escreveu o fecho como peça independente, em vez de enterrá-lo dentro da simulação, ganha este módulo de presente.
A peça central da implementação é o mapa que leva cada conjunto de estados ao índice do estado que o representa. É ele que faz dois caminhos diferentes que chegam ao mesmo conjunto reutilizarem o mesmo estado, em vez de duplicá-lo — e é essa reutilização que explica por que o resultado prático fica tão longe do pior caso teórico.
Uma decisão de representação: quando o conjunto destino é vazio, não crio estado para ele. A transição fica indefinida, o que na representação esparsa adotada no módulo 3 já significa rejeição. Poderia criar um estado morto explícito e teria a função de transição total da definição formal; preferi manter a coerência com o que já existia, e a conversão para a forma completa continua disponível de um lado e de outro.
Onde é fácil errar aqui. Esquecer o fecho vazio depois do movimento. A sequência correta é mover por símbolo e então fechar sobre as transições vazias do resultado; quem só fecha no estado inicial produz um autômato que rejeita cadeias válidas, e o defeito só aparece em expressões com estrela ou opcional no meio — que são justamente as que a especificação léxica usa.
Como verificar. A determinização derruba as seis categorias de 1296 para 332 estados, e nenhum dos autômatos resultantes pode mudar de veredicto sobre os corpora do módulo 2. As duas coisas são conferidas na tabela da tarefa 3.
1.3 Tarefa 2: A minimização
A atividade — reduzir o autômato determinístico ao menor equivalente, por refinamento de partições.
A determinização reorganiza; a minimização funde. São operações de naturezas diferentes e vale ter isso claro: a primeira agrupa em um estado cada conjunto que a simulação carregaria junto; a segunda junta estados que ninguém consegue distinguir pelo que aceitam dali para a frente.
05_minimizacao.h
#ifndef PENEIRA_05_MINIMIZACAO_H
#define PENEIRA_05_MINIMIZACAO_H
#include <string>
#include "03_afd.h"
namespace peneira {
// 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.
//
// O resultado é ÚNICO a menos de renomeação dos estados, e é esse resultado
// que transforma a pergunta "estas duas especificações descrevem a mesma
// linguagem?" num procedimento mecânico: minimize as duas e compare.
Afd minimizar(const Afd& original, std::string nome);
// Registro passo a passo do refinamento: quais estados estavam juntos em cada
// rodada e o que provocou cada separação.
std::string tracarMinimizacao(const Afd& original);
// Compara dois autômatos por estrutura, ignorando os nomes dos estados.
// Numera os dois canonicamente por percurso em largura a partir do inicial,
// visitando os símbolos em ordem, e exige que a numeração resultante case.
//
// É com esta função que a unicidade do autômato mínimo deixa de ser um
// enunciado e vira verificação: dois autômatos mínimos da mesma linguagem
// precisam sair isomorfos, venham de onde vierem.
bool isomorfos(const Afd& a, const Afd& b);
} // namespace peneira
#endif // PENEIRA_05_MINIMIZACAO_H05_minimizacao.cpp
#include "05_minimizacao.h"
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <utility>
#include <vector>
#include "05_determinizacao.h"
namespace peneira {
namespace {
// Calcula a partição estável dos estados. Devolve, para cada estado, o índice
// do bloco a que ele pertence.
std::vector<std::size_t> particionar(const Afd& a,
const std::vector<Simbolo>& alfabeto,
std::ostringstream* trilha) {
const std::size_t n = a.quantidadeDeEstados();
std::vector<std::size_t> bloco(n, 0);
// Partição inicial: finais de um lado, não finais do outro. Se todos os
// estados forem do mesmo tipo, já começamos com um bloco só.
for (std::size_t e = 0; e < n; ++e) {
bloco[e] = a.ehFinal(e) ? 1u : 0u;
}
std::size_t rodada = 0;
for (;;) {
if (trilha != nullptr) {
std::map<std::size_t, std::vector<Estado>> porBloco;
for (std::size_t e = 0; e < n; ++e) {
porBloco[bloco[e]].push_back(e);
}
*trilha << " rodada " << rodada << ": " << porBloco.size()
<< " bloco(s)\n";
for (const auto& par : porBloco) {
*trilha << " {";
for (std::size_t i = 0; i < par.second.size(); ++i) {
if (i > 0) *trilha << ", ";
*trilha << "q" << par.second[i];
}
*trilha << "}" << (a.ehFinal(par.second.front()) ? " final" : "")
<< '\n';
}
}
// A assinatura de um estado é o bloco dele mais o bloco de destino de
// cada símbolo. Dois estados no mesmo bloco com assinaturas diferentes
// são distinguíveis e precisam ser separados.
std::map<std::vector<long long>, std::size_t> novoIndice;
std::vector<std::size_t> novoBloco(n, 0);
for (std::size_t e = 0; e < n; ++e) {
std::vector<long long> assinatura;
assinatura.reserve(alfabeto.size() + 1);
assinatura.push_back(static_cast<long long>(bloco[e]));
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
assinatura.push_back(
destino == kSemEstado
? -1
: static_cast<long long>(bloco[destino]));
}
const auto it = novoIndice.find(assinatura);
if (it == novoIndice.end()) {
const std::size_t indice = novoIndice.size();
novoIndice[assinatura] = indice;
novoBloco[e] = indice;
} else {
novoBloco[e] = it->second;
}
}
if (novoBloco == bloco) {
if (trilha != nullptr) {
*trilha << " nenhuma separacao nova: ponto fixo alcancado\n";
}
return bloco;
}
bloco = novoBloco;
++rodada;
}
}
// Um bloco é morto quando não tem estado final e todas as suas transições
// voltam para ele mesmo: entrar nele significa nunca mais aceitar.
bool blocoEhMorto(const Afd& a, const std::vector<std::size_t>& bloco,
std::size_t alvo, const std::vector<Simbolo>& alfabeto) {
bool temEstado = false;
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
if (bloco[e] != alvo) {
continue;
}
temEstado = true;
if (a.ehFinal(e)) {
return false;
}
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
if (destino != kSemEstado && bloco[destino] != alvo) {
return false;
}
}
}
return temEstado;
}
} // namespace
Afd minimizar(const Afd& original, std::string nome) {
// Ordem obrigatória: primeiro tirar os inalcançáveis. Um estado que
// ninguém alcança pode ficar sozinho num bloco e inflar o resultado sem
// que isso signifique nada sobre a linguagem.
const Afd limpo = removerInalcancaveis(original);
const std::vector<Simbolo> alfabeto = limpo.simbolosUsados();
if (limpo.quantidadeDeEstados() == 0) {
return Afd(std::move(nome));
}
const std::vector<std::size_t> bloco =
particionar(limpo, alfabeto, nullptr);
std::size_t totalDeBlocos = 0;
for (const std::size_t b : bloco) {
totalDeBlocos = (b + 1 > totalDeBlocos) ? b + 1 : totalDeBlocos;
}
// O bloco morto é descartado: voltamos à representação esparsa do módulo 3,
// em que a transição ausente já significa rejeição. O autômato mínimo da
// teoria, com função total, é este mais o estado morto de volta — mesma
// linguagem, uma escolha de representação de diferença.
std::size_t blocoMorto = totalDeBlocos;
for (std::size_t b = 0; b < totalDeBlocos; ++b) {
if (blocoEhMorto(limpo, bloco, b, alfabeto)) {
blocoMorto = b;
break;
}
}
Afd resultado(std::move(nome));
std::map<std::size_t, Estado> indiceDoBloco;
for (std::size_t b = 0; b < totalDeBlocos; ++b) {
if (b == blocoMorto) {
continue;
}
bool final = false;
for (std::size_t e = 0; e < limpo.quantidadeDeEstados(); ++e) {
if (bloco[e] == b) {
final = limpo.ehFinal(e);
break;
}
}
indiceDoBloco[b] = resultado.novoEstado(final);
}
if (indiceDoBloco.count(bloco[limpo.inicial()]) > 0) {
resultado.definirInicial(indiceDoBloco[bloco[limpo.inicial()]]);
}
// Uma transição por bloco e símbolo: como todos os estados do bloco têm a
// mesma assinatura, basta consultar o primeiro deles.
std::set<std::size_t> jaEmitidos;
for (std::size_t e = 0; e < limpo.quantidadeDeEstados(); ++e) {
const std::size_t b = bloco[e];
if (b == blocoMorto || !jaEmitidos.insert(b).second) {
continue;
}
for (const Simbolo s : alfabeto) {
const Estado destino = limpo.transicao(e, s);
if (destino == kSemEstado) {
continue;
}
const std::size_t destinoBloco = bloco[destino];
if (destinoBloco == blocoMorto) {
continue;
}
resultado.adicionarTransicao(indiceDoBloco[b], s,
indiceDoBloco[destinoBloco]);
}
}
return resultado;
}
std::string tracarMinimizacao(const Afd& original) {
const Afd limpo = removerInalcancaveis(original);
std::ostringstream trilha;
trilha << "refinamento de particoes de " << original.nome() << " ("
<< limpo.quantidadeDeEstados() << " estados alcancaveis)\n";
if (limpo.quantidadeDeEstados() > 0) {
particionar(limpo, limpo.simbolosUsados(), &trilha);
}
return trilha.str();
}
bool isomorfos(const Afd& a, const Afd& b) {
if (a.quantidadeDeEstados() != b.quantidadeDeEstados()) {
return false;
}
if (a.simbolosUsados() != b.simbolosUsados()) {
return false;
}
if (a.quantidadeDeEstados() == 0) {
return true;
}
if (a.inicial() == kSemEstado || b.inicial() == kSemEstado) {
return a.inicial() == b.inicial();
}
// Percurso em largura simultâneo nos dois autômatos, visitando os símbolos
// em ordem. Se em algum ponto um tem transição e o outro não, ou as
// finalidades divergem, não há isomorfismo.
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
std::map<Estado, Estado> par;
std::queue<std::pair<Estado, Estado>> fila;
par[a.inicial()] = b.inicial();
fila.push({a.inicial(), b.inicial()});
while (!fila.empty()) {
const std::pair<Estado, Estado> atual = fila.front();
fila.pop();
if (a.ehFinal(atual.first) != b.ehFinal(atual.second)) {
return false;
}
for (const Simbolo s : alfabeto) {
const Estado da = a.transicao(atual.first, s);
const Estado db = b.transicao(atual.second, s);
if ((da == kSemEstado) != (db == kSemEstado)) {
return false;
}
if (da == kSemEstado) {
continue;
}
const auto it = par.find(da);
if (it == par.end()) {
par[da] = db;
fila.push({da, db});
} else if (it->second != db) {
return false;
}
}
}
return par.size() == a.quantidadeDeEstados();
}
} // namespace peneiraO algoritmo de Moore parte da suposição mais otimista possível — só existem duas classes de estados, finais e não finais — e vai separando enquanto encontrar motivo. O motivo é a assinatura: dois estados no mesmo bloco que, com o mesmo símbolo, levam a blocos diferentes são distinguíveis e precisam ser separados. Quando uma rodada inteira não produz separação nova, chegamos ao ponto fixo.
Vale ver o refinamento acontecendo sobre o autômato determinizado do número, que tem quarenta e três estados:
rodada 0: 2 bloco(s)
{q0, q1, q12}
{q2, ..., q42} final
rodada 1: 4 bloco(s)
{q0}
{q1, q12}
{q2, ..., q22} final
{q23, ..., q42} final
rodada 2: 5 bloco(s)
{q0}
{q1}
{q2, ..., q22} final
{q12}
{q23, ..., q42} final
nenhuma separacao nova: ponto fixo alcancadoTrês rodadas, quarenta e três estados, cinco blocos. A rodada 1 é a mais instrutiva: ela separa os finais em dois grupos, e o que os distingue é que um aceita ponto adiante e o outro não — são a parte inteira e a parte fracionária, que o desenho à mão do módulo 3 já tinha separado por intuição. O algoritmo redescobre a distinção sem saber nada sobre números.
Duas decisões de implementação merecem defesa.
A ordem importa: inalcançáveis saem antes. Um estado que ninguém alcança pode ficar sozinho num bloco e inflar o resultado sem que isso signifique nada sobre a linguagem. A construção de subconjuntos já produz só estados alcançáveis, mas um autômato escrito à mão pode ter órfãos, e a função é escrita para servir aos dois casos.
O bloco morto é descartado no fim. O refinamento trabalha sobre a forma completa, com estado de erro explícito, porque a assinatura precisa de um destino definido para cada símbolo. Ao reconstruir, descarto o bloco morto e volto à representação esparsa. Isso merece uma ressalva honesta: o autômato mínimo da teoria, com função de transição total, é este mais o estado morto de volta. Mesma linguagem, uma escolha de representação de diferença — e a unicidade vale nas duas formas.
Onde é fácil errar aqui. Comparar estados apenas pela finalidade e pelos símbolos que aceitam, sem olhar para onde levam. Dois estados finais que aceitam os mesmos símbolos podem ser distinguíveis se um deles leva a um estado morto e o outro não. A assinatura precisa incluir o bloco de destino, não o símbolo.
Como verificar. O menor autômato encontrado precisa aceitar exatamente as mesmas cadeias que o de partida. A verificação está na tarefa 3, e ela é mais forte do que parece.
1.4 Tarefa 3: A verificação, e o teorema em ação
A atividade — a tabela de contagem nas três etapas e a confirmação de que o resultado equivale ao autômato manual do módulo 3.
A tabela das seis categorias, com a redução de cada uma:
categoria Thompson det. minimo reducao
IDENTIFICADOR 250 64 2 99.2%
NUMERO 168 43 5 97.0%
TEXTO 392 100 3 99.2%
PADRAO 392 100 3 99.2%
PONTUACAO 64 16 5 92.2%
ESPACO 30 9 2 93.3%
TOTAL 1296 332 20Mil duzentos e noventa e seis estados viram vinte. O identificador, que a construção de Thompson expandiu para duzentos e cinquenta estados porque [a-z] vira vinte e seis uniões, reduz-se aos dois estados que qualquer pessoa desenharia à mão. O texto entre aspas, com seus trezentos e noventa e dois, cabe em três.
Vale entender por que a queda é tão grande, porque o número sozinho não ensina. Pegue o identificador. A expressão [a-z][a-z0-9_]* tem duas classes, e Thompson expande cada uma em uma cadeia de uniões: vinte e seis fragmentos para a primeira, trinta e sete para a segunda, cada um com dois estados, mais dois estados por operador de união. Daí os duzentos e cinquenta.
Só que esses vinte e seis caminhos paralelos são indistinguíveis para o autômato. Depois de ler um a ou um q, o conjunto de estados alcançados é o mesmo conjunto — o fecho vazio das saídas dos respectivos fragmentos converge para a entrada do fragmento seguinte. A construção de subconjuntos percebe isso naturalmente: consulta o mapa, encontra o conjunto já registrado e reutiliza o estado em vez de criar outro. Sessenta e quatro estados sobrevivem, e a minimização depois observa que quase todos aceitam exatamente o mesmo daí para a frente, fundindo tudo em dois.
Essa é a lição prática por trás dos números: a expansão de Thompson é redundante por construção, e as duas etapas seguintes existem para desfazer redundância que ninguém quis criar. A construção não é ingênua — é uniforme, e a uniformidade cobra em tamanho o que entrega em simplicidade.
Agora a parte que vale o módulo inteiro. Temos dois caminhos completamente independentes até o autômato do número: o desenho que fiz à mão no módulo 3, e a expressão regular passada por Thompson, determinização e minimização. Nenhum dos dois sabe da existência do outro. O teorema da unicidade diz que os dois mínimos têm de ser o mesmo autômato, a menos de renomeação dos estados.
caminho 1 — desenhado a mao no modulo 3: 5 estados, minimizado para 5
caminho 2 — expressao regular via Thompson: 168 estados,
determinizado para 43, minimizado para 5
os dois minimos sao isomorfos? SIMDuas coisas nesse resultado. A primeira é que o desenho à mão já era mínimo — os cinco estados que projetei no módulo 3 não tinham gordura, e o algoritmo confirma. A segunda, mais importante, é o isomorfismo: partindo de lugares diferentes, por processos diferentes, chegamos ao mesmo objeto.
O teste de isomorfismo não é comparação de contagem. Ele numera os dois autômatos canonicamente, por percurso em largura a partir do inicial visitando os símbolos em ordem, e exige que finalidade e estrutura de transições casem em cada passo. Dois autômatos com cinco estados cada podem ter contagens iguais e formas diferentes; este teste recusaria.
Além da estrutura, confiro o comportamento sobre o corpus do módulo 2, e os dois mínimos passam nos treze casos. São verificações independentes: uma olha a forma, outra olha o que o autômato faz. Passar nas duas é bem mais convincente que passar em qualquer uma.
O que isso destrava. No módulo 2, comparei expressões regulares gerando as linguagens que elas denotam até um comprimento dado, e registrei que aquilo era evidência e não demonstração — duas expressões podem coincidir até o comprimento dez e divergir no onze. Agora existe o procedimento de verdade: converta as duas em autômatos, minimize, teste isomorfismo. A resposta é exata e vale para cadeias de qualquer comprimento. Foi para poder dizer isto que o módulo 2 deixou a lacuna explícita.
Onde é fácil errar aqui. Aceitar a igualdade de contagem como prova de equivalência. Dois autômatos mínimos com o mesmo número de estados podem reconhecer linguagens diferentes; é preciso comparar a estrutura, e é por isso que a função de isomorfismo existe em vez de um simples confronto de tamanhos.
1.5 Tarefa 4: A exportação para visualização
A atividade — exportar o autômato para um formato de visualização gráfica e salvar os diagramas.
Esta é a tarefa que os grupos apressados tratam como acessória. Não é. A partir deste módulo os autômatos deixam de ser desenhados por pessoas e passam a ser produzidos por algoritmo, com dezenas ou centenas de estados. Conferir um resultado desses lendo tabela de transição é inviável; olhando o desenho, é imediato.
05_dot.cpp
#include "05_dot.h"
#include <fstream>
#include <map>
#include <sstream>
#include <vector>
namespace peneira {
namespace {
// Escapa o que o DOT trata como especial dentro de um rótulo entre aspas.
std::string escaparDot(Simbolo s) {
switch (s) {
case '"':
return "\\\"";
case '\\':
return "\\\\";
case ' ':
return "esp";
case '\t':
return "tab";
case '\n':
return "nl";
case '\r':
return "cr";
default:
break;
}
if (s >= 33 && s <= 126) {
return std::string(1, static_cast<char>(s));
}
std::ostringstream saida;
saida << '#' << static_cast<unsigned int>(s);
return saida.str();
}
} // namespace
std::string exportarDot(const Afd& a) {
std::ostringstream saida;
saida << "digraph automato {\n";
saida << " rankdir=LR;\n";
saida << " labelloc=\"t\";\n";
saida << " label=\"" << a.nome() << " (" << a.quantidadeDeEstados()
<< " estados)\";\n";
// Nó invisível apontando para o inicial: é a convenção usual para marcar
// o estado de partida num diagrama de autômato.
saida << " inicio [shape=point];\n";
if (a.inicial() != kSemEstado) {
saida << " inicio -> q" << a.inicial() << ";\n";
}
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
saida << " q" << e << " [shape="
<< (a.ehFinal(e) ? "doublecircle" : "circle") << "];\n";
}
// Agrupa por destino e, dentro do destino, colapsa símbolos consecutivos
// em faixa, para que o rótulo da aresta caiba no desenho.
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
std::map<Estado, std::vector<Simbolo>> porDestino;
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
if (destino != kSemEstado) {
porDestino[destino].push_back(s);
}
}
for (const auto& par : porDestino) {
std::ostringstream rotulo;
const std::vector<Simbolo>& simbolos = par.second;
std::size_t i = 0;
bool primeiro = true;
while (i < simbolos.size()) {
std::size_t j = i;
while (j + 1 < simbolos.size() &&
simbolos[j + 1] == static_cast<Simbolo>(simbolos[j] + 1)) {
++j;
}
if (!primeiro) rotulo << ",";
if (i == j) {
rotulo << escaparDot(simbolos[i]);
} else {
rotulo << escaparDot(simbolos[i]) << "-"
<< escaparDot(simbolos[j]);
}
primeiro = false;
i = j + 1;
}
saida << " q" << e << " -> q" << par.first << " [label=\""
<< rotulo.str() << "\"];\n";
}
}
saida << "}\n";
return saida.str();
}
bool salvarDot(const Afd& a, const std::string& caminho, std::string& erro) {
std::ofstream arquivo(caminho, std::ios::binary);
if (!arquivo) {
erro = "nao foi possivel abrir para escrita: " + caminho;
return false;
}
arquivo << exportarDot(a);
if (!arquivo) {
erro = "falha ao escrever: " + caminho;
return false;
}
erro.clear();
return true;
}
} // namespace peneiraO formato adotado é o DOT, do Graphviz, por ser texto simples e ter ferramenta madura de desenho. O arquivo gerado para o autômato mínimo do número sai assim:
digraph automato {
rankdir=LR;
label="NUMERO (5 estados)";
inicio [shape=point];
inicio -> q0;
q0 [shape=circle];
q2 [shape=doublecircle];
q0 -> q1 [label="-"];
q0 -> q2 [label="0-9"];
q2 -> q2 [label="0-9"];
q2 -> q3 [label="."];
...
}Duas convenções que valem seguir: o estado final é círculo duplo, e um nó invisível aponta para o inicial. São as convenções dos livros, e usá-las faz o diagrama gerado pela ferramenta parecer com o do material teórico.
Os símbolos consecutivos com o mesmo destino são agrupados em faixa, pelo mesmo motivo que a tabela do módulo 3 agrupa: sem isso, o autômato do identificador teria trinta e sete arestas paralelas entre os mesmos dois estados, e o desenho ficaria ilegível.
Um defeito real que só o diagrama revelou. Ao olhar o arquivo gerado para a categoria do espaço em branco, o rótulo da aresta saiu como esp,n,r,t — o autômato estava reconhecendo as letras n, r e t, além do espaço. A causa estava no analisador da notação, escrito no módulo 4: diante de \t, ele removia o significado especial da barra invertida e devolvia a letra t, em vez de traduzir para o caractere de tabulação.
O defeito é do tipo pior: o autômato ficava bem formado, a determinização e a minimização funcionavam sobre ele, os testes de estrutura passavam — e a linguagem reconhecida estava errada. Nenhuma verificação anterior o teria pego, porque o corpus da categoria de espaço não distingue tabulação de letra t sem que alguém olhe. O diagrama olhou.
A correção foi acrescentar a tradução das três sequências de controle no ponto em que a barra invertida é consumida, nos três lugares onde ela aparece: no átomo, no membro de classe e no extremo de faixa. Depois dela, o rótulo sai como tab-nl,cr,esp. Vale como argumento a favor de tratar a visualização como ferramenta de trabalho, e não como entrega decorativa.
Como verificar. Gerar os seis diagramas e abrir pelo menos um. Se o Graphviz não estiver instalado, o arquivo DOT continua sendo texto legível e a conferência pode ser feita nele mesmo — que foi exatamente como o defeito acima apareceu.
1.6 Referência teórica: o pior caso da determinização
O módulo enuncia que a construção de subconjuntos pode produzir um autômato com número de estados exponencial no do original. Enunciar isso e mostrar a tabela do projeto, em que os estados caem, deixa o resultado parecendo teoria desconectada. Implementei a família que exibe o crescimento.
A linguagem é a das cadeias sobre a e b cujo k-ésimo símbolo antes do fim é a. Um autômato não determinístico a reconhece adivinhando qual ocorrência de a é a certa. Um determinístico não pode adivinhar: precisa lembrar os últimos k+1 símbolos lidos, e há 2^{k+1} combinações possíveis.
k Thompson determinizado minimo
1 16 5 4
2 22 9 8
3 28 17 16
4 34 33 32
5 40 65 64
6 46 129 128
7 52 257 256A coluna do determinizado dobra a cada incremento de k, e vale exatamente 2^{k+1} + 1; a do mínimo vale 2^{k+1}. O expoente é k+1, e não k, porque a família implementada aqui conta o k-ésimo símbolo antes do fim, o que obriga o determinístico a lembrar k+1 símbolos — a formulação canônica do teorema, que numera o último símbolo como o primeiro, chega a 2^k pela mesma razão. A minimização não ajuda — o autômato já é mínimo. Não há desperdício a cortar: a linguagem exige mesmo essa memória, e nenhum algoritmo poderia fazer melhor.
O contraste com a tabela das categorias reais é o ponto pedagógico. Lá, a determinização encolhe; aqui, explode. O pior caso é real, é atingível, e expressões de uso prático raramente se parecem com ele. Saber os dois lados é o que separa quem entende o algoritmo de quem decorou que “pode ser exponencial”.
1.7 Referência teórica: o refinamento de Hopcroft
O módulo menciona o algoritmo de Hopcroft como refinamento do de Moore, com complexidade menor. Não o implementei, e registro o motivo.
O de Moore, que implementei, recalcula a assinatura de todos os estados a cada rodada; seu custo é da ordem de O(k n^2) para n estados e k símbolos. O de Hopcroft trabalha com uma fila de blocos a processar e escolhe sempre o menor lado de cada separação, chegando a O(k n \log n). Para os quarenta e três estados do maior autômato deste projeto, a diferença é imperceptível; ela passa a importar em ordens de grandeza que este compilador não vai alcançar.
Implementar Hopcroft aqui custaria complexidade de código sem ganho observável, e obscureceria justamente o que a versão de Moore deixa visível: a partição refinando rodada a rodada, que é o conceito do módulo. A troca é consciente e está comentada no código.
1.8 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Determinização | Trata transições vazias; reduz 1296 para 332 estados | Atende |
| Eliminação de inalcançáveis | Executada antes do refinamento | Atende |
| Minimização | Refinamento até ponto fixo; 332 para 20 estados | Atende |
| Contagem nas três etapas | Tabela por categoria, com redução percentual | Atende |
| Equivalência com o manual | Isomorfismo com o autômato do módulo 3 | Confirmado, e os corpora passam nos dois |
| Exportação visual | Seis arquivos DOT gerados | Atende |
| Pior caso demonstrado | Família com crescimento exponencial medido | 2^{k+1}+1 determinizado, 2^{k+1} mínimo |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação e execução |
O que quero deixar registrado sobre esta entrega é que ela fecha o primeiro bloco da disciplina com uma ferramenta que funciona: expressão regular entra, autômato mínimo sai, e há como provar que o resultado está certo. O módulo 6 vai mostrar o que essa ferramenta não consegue fazer, e o módulo 7 a transformará em analisador léxico. Mas o motor está pronto, e ele tem vinte estados onde a construção ingênua tinha mil duzentos e noventa e seis.