1 Módulo 03: Projeto do Professor — O Primeiro Autômato, Projetado à Mão
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. A categoria que você vai escolher é outra, e o autômato que sair dela também.
1.1 Visão Geral do Módulo 03
O módulo 3 pede duas coisas ao grupo, e a ordem entre elas importa. Primeiro, projetar à mão o autômato finito determinístico de uma das categorias léxicas especificadas no módulo anterior, entregando o diagrama de estados e a tabela de transição derivada dele. Depois, implementar o reconhecedor: um programa que, dada a descrição de um autômato e uma cadeia, decide se a cadeia é aceita — e verificá-lo contra os corpora escritos no módulo 2.
Projetar à mão é trabalho que a construção automática do módulo 4 vai eliminar por completo. Isso não é desperdício: é o ponto. Quem desenhou cinco estados no papel e descobriu, ao desenhar, que precisava de um sexto, entende o que a construção de Thompson faz por ele. Quem pulou direto para a ferramenta aprende a ferramenta.
Resolvi a atividade escolhendo a categoria NUMERO, que é a menos trivial da especificação, e acrescentei a IDENTIFICADOR como contraste — dois estados contra cinco, para deixar visível de onde vem a dificuldade. Em torno das duas, construí a estrutura de autômato que o projeto vai carregar até o último módulo, e é nas decisões de representação dela que está a parte cara deste módulo.
Uma promessa do módulo 2 se cumpre aqui: os corpora de aceitação e rejeição, escritos antes de existir qualquer implementação, deixam de ser contrato e passam a ser executáveis.
1.2 Tarefa 1: Projetar o autômato à mão
A atividade — escolher uma categoria léxica não trivial, projetar o autômato determinístico que a reconhece e derivar a tabela de transição.
Escolhi NUMERO, cuja expressão é -?[0-9]+(\.[0-9]+)?. Escolhi porque ela tem três pontos de decisão — o sinal opcional, a fronteira entre parte inteira e ponto, e a parte fracionária opcional — e porque os casos de fronteira do corpus do módulo 2 batem exatamente nesses pontos.
O desenho saiu assim. O estado inicial precisa aceitar duas coisas: um sinal, que leva a um estado onde ainda não vi dígito nenhum, ou um dígito, que já me põe na parte inteira. Da parte inteira, mais dígitos me mantêm nela e um ponto me leva para um estado onde vi o ponto mas ainda não vi dígito depois dele. Desse estado, um dígito me leva à parte fracionária, onde mais dígitos me mantêm.
São cinco estados, e dois deles são não finais no meio do caminho: o que fica depois do sinal e o que fica depois do ponto. Foi ao desenhar que percebi que precisava dos dois separados. A tentação é economizar estados e deixar o autômato ir do sinal direto para a parte inteira, ou do ponto direto para a fracionária — e aí - sozinho e 5. passariam a ser aceitos, que é exatamente o que o corpus do módulo 2 proíbe. Os dois estados intermediários existem para exigir “pelo menos um dígito depois disto”.
Descrevendo a tabela de transição por extenso: do estado inicial, o sinal leva ao segundo estado e qualquer dígito leva ao terceiro; do segundo, qualquer dígito leva ao terceiro; o terceiro é final, qualquer dígito o mantém e o ponto leva ao quarto; do quarto, qualquer dígito leva ao quinto; o quinto é final e qualquer dígito o mantém. Nenhuma outra transição existe.
Para contraste, projetei também IDENTIFICADOR, de expressão [a-z][a-z0-9_]*. Dois estados: o inicial exige uma letra minúscula, e o segundo, final, aceita letra, dígito ou sublinhado indefinidamente. A expressão não é mais curta que a do número, e o autômato tem menos da metade dos estados. A diferença não vem do tamanho da expressão — vem de quantas vezes a decisão depende do que já foi lido.
03_reconhecedores.h
#ifndef PENEIRA_03_RECONHECEDORES_H
#define PENEIRA_03_RECONHECEDORES_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// Autômatos projetados à mão, a partir das categorias léxicas especificadas no
// módulo 2. São dois de propósito: um trivial e um com pontos de decisão, para
// que a diferença de esforço fique visível.
//
// Construí-los à mão é trabalho que a construção automática do módulo 4 vai
// eliminar. O ponto de fazê-lo agora é sentir o custo que ela poupa.
Afd afdNumero();
Afd afdIdentificador();
// Resultado da verificação de um autômato contra os corpora do módulo 2.
struct ResultadoVerificacao {
std::string categoria;
std::size_t aceitasEsperadas = 0;
std::size_t aceitasObtidas = 0;
std::size_t rejeitadasEsperadas = 0;
std::size_t rejeitadasObtidas = 0;
std::vector<std::string> divergencias;
bool passou() const;
};
// Roda o autômato contra os dois corpora da categoria de mesmo nome na
// especificação léxica. É aqui que os corpora escritos no módulo 2 deixam de
// ser contrato e passam a ser executáveis.
ResultadoVerificacao verificar(const Afd& automato, const std::string& categoria);
} // namespace peneira
#endif // PENEIRA_03_RECONHECEDORES_H03_reconhecedores.cpp
#include "03_reconhecedores.h"
#include "02_lexico.h"
namespace peneira {
Afd afdNumero() {
// Reconhece -?[0-9]+(\.[0-9]+)?
//
// q0 inicial: aceita sinal ou entra direto na parte inteira
// q1 depois do sinal: exige pelo menos um digito
// q2 parte inteira, FINAL: mais digitos, ou o ponto
// q3 depois do ponto: exige pelo menos um digito
// q4 parte fracionaria, FINAL
//
// Os dois estados não finais no meio (q1 e q3) são o que impede "-" e "5."
// de serem aceitos. Foi ao desenhar que percebi que precisava deles
// separados de q2 e q4.
Afd a("NUMERO");
const Estado q0 = a.novoEstado(false);
const Estado q1 = a.novoEstado(false);
const Estado q2 = a.novoEstado(true);
const Estado q3 = a.novoEstado(false);
const Estado q4 = a.novoEstado(true);
a.definirInicial(q0);
a.adicionarTransicao(q0, '-', q1);
a.adicionarFaixa(q0, '0', '9', q2);
a.adicionarFaixa(q1, '0', '9', q2);
a.adicionarFaixa(q2, '0', '9', q2);
a.adicionarTransicao(q2, '.', q3);
a.adicionarFaixa(q3, '0', '9', q4);
a.adicionarFaixa(q4, '0', '9', q4);
return a;
}
Afd afdIdentificador() {
// Reconhece [a-z][a-z0-9_]*
//
// q0 inicial: exige letra minuscula
// q1 FINAL: letra, digito ou sublinhado, indefinidamente
//
// Dois estados bastam. O contraste com o autômato do número mostra que a
// dificuldade não vem do tamanho da expressão, e sim da quantidade de
// pontos em que a decisão depende do que já foi lido.
Afd a("IDENTIFICADOR");
const Estado q0 = a.novoEstado(false);
const Estado q1 = a.novoEstado(true);
a.definirInicial(q0);
a.adicionarFaixa(q0, 'a', 'z', q1);
a.adicionarFaixa(q1, 'a', 'z', q1);
a.adicionarFaixa(q1, '0', '9', q1);
a.adicionarTransicao(q1, '_', q1);
return a;
}
bool ResultadoVerificacao::passou() const {
return divergencias.empty() && aceitasObtidas == aceitasEsperadas &&
rejeitadasObtidas == rejeitadasEsperadas;
}
ResultadoVerificacao verificar(const Afd& automato,
const std::string& categoria) {
ResultadoVerificacao resultado;
resultado.categoria = categoria;
for (const CategoriaLexica& c : especificacaoLexica()) {
if (c.nome != categoria) {
continue;
}
resultado.aceitasEsperadas = c.aceitas.size();
resultado.rejeitadasEsperadas = c.rejeitadas.size();
for (const Cadeia& cadeia : c.aceitas) {
if (automato.aceita(cadeia)) {
++resultado.aceitasObtidas;
} else {
resultado.divergencias.push_back(
"deveria aceitar e rejeitou: \"" + cadeia + "\"");
}
}
for (const Cadeia& cadeia : c.rejeitadas) {
if (!automato.aceita(cadeia)) {
++resultado.rejeitadasObtidas;
} else {
resultado.divergencias.push_back(
"deveria rejeitar e aceitou: \"" + cadeia + "\"");
}
}
return resultado;
}
resultado.divergencias.push_back("categoria ausente na especificacao: " +
categoria);
return resultado;
}
} // namespace peneiraRepare que o código de construção é praticamente a transcrição do desenho: um estado por linha, com a marca de final, e uma transição por linha depois. O comentário no topo de cada função carrega o desenho em texto, porque é o desenho que explica o código, e não o contrário.
Onde é fácil errar aqui. Marcar como final o estado errado. É tentador marcar o estado que vem depois do ponto — afinal, 3. “parece” um número. Se você marcar, o corpus acusa na hora. Foi para isso que ele foi escrito antes.
Como verificar. A tabela de transição é impressa pelo próprio programa, com os símbolos consecutivos que levam ao mesmo destino agrupados em faixa. Sem esse agrupamento, a tabela do identificador teria trinta e sete linhas, uma por símbolo aceito, e seria ilegível — com ele, tem três. Os símbolos saem entre aspas simples porque o hífen é ele próprio um símbolo do alfabeto do número: sem as aspas, a faixa que vai do hífen ao ponto sairia como --. e ninguém conseguiria ler.
1.3 Tarefa 2: Implementar o reconhecedor
A atividade — implementar o programa que, dada a descrição de um autômato e uma cadeia, decide se a cadeia é aceita.
Esta é a peça que fica. O autômato construído aqui é o mesmo tipo de objeto que a construção de Thompson vai produzir no módulo 4, que a determinização vai transformar no módulo 5 e que o analisador léxico vai executar no módulo 7. As decisões de representação tomadas agora custam caro se forem revistas depois.
03_afd.h
#ifndef PENEIRA_03_AFD_H
#define PENEIRA_03_AFD_H
#include <cstddef>
#include <map>
#include <string>
#include <vector>
#include "02_cadeia.h"
namespace peneira {
// Estados são índices num vetor, nunca ponteiros. Um autômato é um grafo com
// ciclos, e grafo cíclico manipulado por ponteiro é a origem mais comum de
// defeito de memória num projeto como este. Com índice, copiar o autômato é
// copiar dois vetores, e comparar estados é comparar inteiros.
using Estado = std::size_t;
// O símbolo é sem sinal de propósito. Com `char` simples, um byte acima de 127
// vira valor negativo na plataforma e desordena o mapa de transições — defeito
// que só aparece com entrada acentuada e é difícil de rastrear.
using Simbolo = unsigned char;
// Ausência de estado. Usado como resultado de uma transição não definida e
// como marcador de autômato ainda sem estado inicial.
inline constexpr Estado kSemEstado = static_cast<Estado>(-1);
// Autômato finito determinístico: a quíntupla da definição formal, com os
// estados numerados de zero a n-1.
//
// A função de transição é representada por um mapa esparso por estado, e não
// por matriz densa. O alfabeto tem 256 símbolos e um estado típico define
// transição para uns poucos; a matriz densa gastaria 256 posições por estado
// para usar meia dúzia.
class Afd {
public:
explicit Afd(std::string nome);
Estado novoEstado(bool final);
void definirInicial(Estado e);
void adicionarTransicao(Estado de, Simbolo simbolo, Estado para);
// Atalho para declarar uma faixa contígua de símbolos com o mesmo destino,
// como `[0-9]`. Evita vinte e seis chamadas para declarar as letras.
void adicionarFaixa(Estado de, Simbolo inicio, Simbolo fim, Estado para);
const std::string& nome() const noexcept;
std::size_t quantidadeDeEstados() const noexcept;
Estado inicial() const noexcept;
bool ehFinal(Estado e) const;
// A função de transição da definição formal. Devolve kSemEstado quando não
// há transição declarada — é o estado de erro implícito.
Estado transicao(Estado de, Simbolo simbolo) const;
// Função de transição estendida a cadeias, definida por indução: a cadeia
// vazia leva ao próprio estado, e uma cadeia com um símbolo a mais leva ao
// resultado de aplicar a transição ao estado alcançado pelo prefixo.
Estado deltaEstendido(Estado de, const Cadeia& s) const;
// A cadeia é aceita quando a função estendida, partindo do inicial, chega
// a um estado final.
bool aceita(const Cadeia& s) const;
// Símbolos que aparecem em alguma transição. É o alfabeto efetivamente
// usado, que não precisa ser o alfabeto inteiro da linguagem.
std::vector<Simbolo> simbolosUsados() const;
// A definição formal exige função de transição TOTAL. A representação
// esparsa deixa o estado de erro implícito; este método o torna explícito,
// acrescentando um estado não final que absorve tudo que não estava
// declarado. O autômato resultante reconhece a mesma linguagem.
bool ehCompleto() const;
Afd completado() const;
// Tabela de transição em texto, com símbolos consecutivos de mesmo destino
// agrupados em faixa. Sem o agrupamento, a tabela do identificador teria
// trinta e sete colunas e seria ilegível.
std::string tabelaDeTransicao() const;
// Sequência de configurações instantâneas ao processar a cadeia: em que
// estado o autômato está e o que falta ler, passo a passo.
std::string tracar(const Cadeia& s) const;
private:
std::string nome_;
Estado inicial_ = kSemEstado;
std::vector<bool> finais_;
std::vector<std::map<Simbolo, Estado>> transicoes_;
};
} // namespace peneira
#endif // PENEIRA_03_AFD_H03_afd.cpp
#include "03_afd.h"
#include <set>
#include <sstream>
#include <stdexcept>
#include <utility>
namespace peneira {
namespace {
// Representação legível de um símbolo dentro da tabela e do traçado.
std::string mostrarSimbolo(Simbolo s) {
switch (s) {
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();
}
std::string mostrarEstado(Estado e) {
if (e == kSemEstado) {
return "-";
}
return "q" + std::to_string(e);
}
} // namespace
Afd::Afd(std::string nome) : nome_(std::move(nome)) {}
Estado Afd::novoEstado(bool final) {
finais_.push_back(final);
transicoes_.emplace_back();
return finais_.size() - 1;
}
void Afd::definirInicial(Estado e) {
if (e >= finais_.size()) {
throw std::out_of_range("estado inicial inexistente");
}
inicial_ = e;
}
void Afd::adicionarTransicao(Estado de, Simbolo simbolo, Estado para) {
if (de >= finais_.size() || para >= finais_.size()) {
throw std::out_of_range("transicao entre estados inexistentes");
}
transicoes_[de][simbolo] = para;
}
void Afd::adicionarFaixa(Estado de, Simbolo inicio, Simbolo fim, Estado para) {
for (unsigned int s = inicio; s <= fim; ++s) {
adicionarTransicao(de, static_cast<Simbolo>(s), para);
}
}
const std::string& Afd::nome() const noexcept { return nome_; }
std::size_t Afd::quantidadeDeEstados() const noexcept { return finais_.size(); }
Estado Afd::inicial() const noexcept { return inicial_; }
bool Afd::ehFinal(Estado e) const {
return e < finais_.size() && finais_[e];
}
Estado Afd::transicao(Estado de, Simbolo simbolo) const {
if (de >= transicoes_.size()) {
return kSemEstado;
}
const auto it = transicoes_[de].find(simbolo);
return (it == transicoes_[de].end()) ? kSemEstado : it->second;
}
Estado Afd::deltaEstendido(Estado de, const Cadeia& s) const {
Estado atual = de;
for (const char c : s) {
if (atual == kSemEstado) {
return kSemEstado;
}
atual = transicao(atual, static_cast<Simbolo>(c));
}
return atual;
}
bool Afd::aceita(const Cadeia& s) const {
if (inicial_ == kSemEstado) {
return false;
}
return ehFinal(deltaEstendido(inicial_, s));
}
std::vector<Simbolo> Afd::simbolosUsados() const {
std::set<Simbolo> distintos;
for (const auto& porEstado : transicoes_) {
for (const auto& par : porEstado) {
distintos.insert(par.first);
}
}
return std::vector<Simbolo>(distintos.begin(), distintos.end());
}
bool Afd::ehCompleto() const {
const std::vector<Simbolo> alfabeto = simbolosUsados();
for (std::size_t e = 0; e < transicoes_.size(); ++e) {
for (const Simbolo s : alfabeto) {
if (transicao(e, s) == kSemEstado) {
return false;
}
}
}
return true;
}
Afd Afd::completado() const {
Afd resultado(nome_ + " (completo)");
for (std::size_t e = 0; e < finais_.size(); ++e) {
resultado.novoEstado(finais_[e]);
}
// O estado de erro é não final e absorvente: uma vez nele, o autômato não
// sai mais. É exatamente o estado que a representação esparsa mantinha
// implícito.
const Estado erro = resultado.novoEstado(false);
resultado.definirInicial(inicial_);
const std::vector<Simbolo> alfabeto = simbolosUsados();
for (std::size_t e = 0; e < finais_.size(); ++e) {
for (const Simbolo s : alfabeto) {
const Estado destino = transicao(e, s);
resultado.adicionarTransicao(e, s,
destino == kSemEstado ? erro : destino);
}
}
for (const Simbolo s : alfabeto) {
resultado.adicionarTransicao(erro, s, erro);
}
return resultado;
}
std::string Afd::tabelaDeTransicao() const {
std::ostringstream saida;
saida << "tabela de transicao de " << nome_ << " (" << finais_.size()
<< " estados)\n";
for (std::size_t e = 0; e < transicoes_.size(); ++e) {
saida << " " << mostrarEstado(e);
if (e == inicial_) saida << " inicial";
if (finais_[e]) saida << " final";
saida << '\n';
if (transicoes_[e].empty()) {
saida << " (sem transicoes: estado morto)\n";
continue;
}
// Agrupa símbolos consecutivos que levam ao mesmo destino. A tabela do
// identificador passa de 37 linhas para 3.
auto it = transicoes_[e].begin();
while (it != transicoes_[e].end()) {
const Simbolo inicio = it->first;
const Estado destino = it->second;
Simbolo fim = inicio;
auto proximo = std::next(it);
while (proximo != transicoes_[e].end() &&
proximo->second == destino &&
proximo->first == static_cast<Simbolo>(fim + 1)) {
fim = proximo->first;
++proximo;
}
// Os símbolos vão entre aspas simples porque o próprio hífen é um
// símbolo do alfabeto: sem as aspas, a faixa de '-' até '.' sairia
// como "--." e ninguém saberia ler.
saida << " ";
if (inicio == fim) {
saida << '\'' << mostrarSimbolo(inicio) << '\'';
} else {
saida << '\'' << mostrarSimbolo(inicio) << "'..'"
<< mostrarSimbolo(fim) << '\'';
}
saida << " -> " << mostrarEstado(destino) << '\n';
it = proximo;
}
}
return saida.str();
}
std::string Afd::tracar(const Cadeia& s) const {
std::ostringstream saida;
Estado atual = inicial_;
saida << " (" << mostrarEstado(atual) << ", \"" << s << "\")";
for (std::size_t i = 0; i < s.size(); ++i) {
if (atual == kSemEstado) {
break;
}
atual = transicao(atual, static_cast<Simbolo>(s[i]));
saida << "\n |- (" << mostrarEstado(atual) << ", \""
<< s.substr(i + 1) << "\")";
if (atual == kSemEstado) {
saida << " transicao nao definida";
break;
}
}
saida << "\n resultado: ";
if (atual == kSemEstado) {
saida << "rejeita (caiu no estado de erro)";
} else if (ehFinal(atual)) {
saida << "aceita (" << mostrarEstado(atual) << " e final)";
} else {
saida << "rejeita (" << mostrarEstado(atual) << " nao e final)";
}
saida << '\n';
return saida.str();
}
} // namespace peneiraTrês decisões de representação sustentam tudo o que vem depois, e vale defender cada uma.
Estados são índices num vetor, nunca ponteiros. Um autômato é um grafo dirigido com ciclos — o estado da parte inteira aponta para si mesmo. Grafo cíclico manipulado por ponteiro é a fonte mais comum de defeito de memória num projeto deste tipo: quem é dono de quem, quem libera o quê, e o que acontece quando dois estados apontam um para o outro. Com índices, o problema desaparece por construção. Copiar o autômato é copiar dois vetores. Comparar dois estados é comparar dois inteiros. E, no módulo 5, quando a determinização precisar de conjuntos de estados, esses conjuntos serão conjuntos de inteiros, que é a coisa mais barata que existe.
O símbolo é do tipo sem sinal. Parece detalhe e não é. Com o tipo de caractere simples da linguagem, um byte acima de 127 vira valor negativo nesta plataforma, e o mapa de transições passa a ordenar errado — defeito que só aparece diante de entrada acentuada e que é penoso de rastrear. Fixar o tipo sem sinal na definição do alias resolve de uma vez, e a conversão fica num único ponto, na fronteira em que a cadeia é lida.
A tabela de transição é um mapa esparso por estado, não uma matriz densa. O alfabeto tem 256 símbolos e um estado típico do nosso autômato define transição para dez ou trinta. Uma matriz densa reservaria 256 posições por estado para usar uma fração delas. Com cinco estados isso é irrelevante; a partir da determinização, no módulo 5, o número de estados cresce e a diferença deixa de ser acadêmica. A escolha tem um custo, e é honesto declará-lo: a consulta passa a ser logarítmica no número de transições do estado, em vez de constante. Para o tamanho deste projeto, é troca vantajosa.
1.3.1 A função de transição estendida
A definição formal distingue a função de transição, que vai de estado e símbolo para estado, da sua extensão a cadeias, definida por indução: a cadeia vazia leva ao próprio estado, e uma cadeia com um símbolo a mais leva ao resultado de aplicar a transição ao estado alcançado pelo prefixo.
Implementei a extensão iterativamente, e não recursivamente, por uma razão prática: a recursão sobre o comprimento da cadeia estouraria a pilha em entradas grandes, e o analisador léxico do módulo 7 vai rodar isto sobre arquivos inteiros. A correspondência com a definição indutiva se mantém — o laço é a indução desenrolada — e anotei isso no comentário para que a diferença não pareça descuido.
A aceitação é então uma linha: a cadeia é aceita quando a função estendida, partindo do estado inicial, chega a um estado final.
Onde é fácil errar aqui. Esquecer de tratar o caso em que a transição não existe no meio da cadeia. Se a função estendida continuar processando depois de cair fora do autômato, ou o programa acessa posição inválida ou, pior, a leitura acidental de um estado válido faz uma cadeia inválida ser aceita. Resolvi com um valor sentinela que representa a ausência de estado, verificado no topo de cada iteração.
Como verificar. O traçado das configurações instantâneas mostra exatamente onde cada cadeia para. Sobre a entrada -0.5, o autômato percorre os cinco estados e termina em final. Sobre 5., para no estado depois do ponto, que não é final. Sobre 1e10, a letra não tem transição definida e o traçado registra a queda. São os três desfechos possíveis, e a distinção entre os dois últimos importa: um é “cheguei ao fim da entrada num lugar que não vale”, o outro é “encontrei um símbolo que não pertence”, e o analisador léxico do módulo 7 vai reportá-los de formas diferentes.
1.4 Tarefa 3: Verificar contra os corpora do módulo 2
A atividade — rodar o reconhecedor sobre os conjuntos de cadeias aceitas e rejeitadas escritos no módulo 2 e documentar as divergências.
No módulo 2 escrevi os corpora e admiti que eles não eram executáveis: faltava o reconhecedor. Agora existe.
A verificação percorre a especificação léxica, encontra a categoria de mesmo nome, roda o autômato sobre cada cadeia dos dois conjuntos e conta. Toda cadeia do conjunto de aceitação que for rejeitada, e toda cadeia do conjunto de rejeição que for aceita, entra na lista de divergências com a descrição do que aconteceu.
O resultado da execução:
NUMERO: 6/6 aceitas, 7/7 rejeitadas -> confere
IDENTIFICADOR: 6/6 aceitas, 5/5 rejeitadas -> confereTreze casos para o número, onze para o identificador, nenhuma divergência. Vale olhar quais casos passaram, porque não são todos triviais. Em NUMERO, foram rejeitados .5 e 5., que só falham por causa dos dois estados intermediários; 1.2.3, que falha por não haver transição de ponto saindo da parte fracionária; 1e10, que falha na letra; +3, que falha porque só o sinal negativo tem transição; e a cadeia vazia e o hífen sozinho, que falham por parar em estado não final. E foi aceito 007, que é a decisão consciente sobre zeros à esquerda registrada no módulo 2.
Em IDENTIFICADOR, o caso que mais vale é Email: rejeitado porque o alfabeto da categoria não inclui maiúsculas. Não é limitação acidental, é a restrição da linguagem, e o corpus a documenta.
O que a verificação ainda não cobre. Quatro das seis categorias da especificação — TEXTO, PADRAO, PONTUACAO e ESPACO — continuam sem autômato. Não é esquecimento: construí-las à mão seria trabalho jogado fora, porque a partir do módulo 4 a construção passa a ser automática a partir da expressão regular. Escolhi as duas que ensinam mais por unidade de esforço e parei. Quando os grupos perguntarem por que não fiz as seis, esta é a resposta.
Onde é fácil errar aqui. Escrever a verificação de modo que ela conte apenas acertos. Um relatório que diz “13 de 13 passaram” e não tem como reportar falha não prova nada — pode ser que sempre diga isso. A estrutura de resultado carrega a lista de divergências e a comparação entre esperado e obtido separadamente, de modo que uma contagem inconsistente apareça mesmo que a lista esteja vazia.
1.5 Referência teórica: o estado de erro e a completude da função de transição
Um tópico do módulo é a exigência, na definição formal, de que a função de transição seja total: para todo par de estado e símbolo, tem de haver um destino. A representação esparsa que escolhi viola isso à primeira vista — o mapa simplesmente não tem entrada para os pares indefinidos.
A conciliação é que existe um estado de erro implícito. A transição indefinida devolve o sentinela de ausência, e o processamento da cadeia termina em rejeição. Comportamento idêntico ao de um estado morto explícito; representação diferente.
Para que a diferença não fique só no discurso, implementei a conversão. O método que completa o autômato cria um estado novo, não final, e o faz absorvente: todas as transições indefinidas passam a apontar para ele, e todas as transições que saem dele apontam para ele mesmo. O autômato do número passa de cinco para seis estados e a função de transição passa a ser total.
A demonstração roda a verificação nos dois — o esparso e o completo — sobre os mesmos corpora, e os dois dão o mesmo resultado. É a evidência de que a completude é escolha de representação, e não mudança de linguagem.
Vale registrar por que não deixei o autômato completo como representação padrão, já que ele é o que a teoria descreve. Completar exige fixar o alfabeto, e o alfabeto natural aqui seria os 256 símbolos possíveis, o que faria cada estado carregar 256 transições. Para o autômato do número isso significa passar de dezesseis transições declaradas para mil e quinhentas. A representação esparsa guarda o mínimo e devolve o mesmo comportamento; a completa existe como transformação, para quando for pedagogicamente útil exibi-la.
1.6 Referência teórica: das duas representações
O módulo trata da equivalência entre diagrama de estados e tabela de transição, e da conversão de uma para a outra. O diagrama serve ao raciocínio humano; a tabela serve à máquina. Projetei no diagrama e implementei da tabela, que é o caminho normal.
A direção inversa — da tabela para o diagrama — está no código como a impressão da tabela agrupada por faixas. Não é o diagrama desenhado, mas é a informação dele em forma legível, e é o que permite conferir a olho se o autômato construído é o que foi projetado. A visualização gráfica de verdade chega no módulo 5, quando o número de estados passar a crescer por algoritmo e a conferência a olho deixar de ser viável.
1.7 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Autômato projetado à mão | Diagrama descrito e tabela derivada, com justificativa dos estados | NUMERO, cinco estados, mais IDENTIFICADOR como contraste |
| Estados não finais intermediários | O autômato rejeita entradas truncadas | Dois estados exigindo “pelo menos um dígito depois” |
| Reconhecedor implementado | Decide aceitação para qualquer autômato e cadeia | Função de transição estendida, iterativa |
| Verificação contra o módulo 2 | Contagens e lista de divergências | 13/13 e 11/11, nenhuma divergência |
| Divergências documentadas | Relatório distingue esperado de obtido | Estrutura carrega ambos, separadamente |
| Completude tratada | Estado de erro explícito disponível | Conversão implementada e verificada |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação |
A tabela de transição do autômato do número, tal como o programa a imprime, com os símbolos consecutivos agrupados em faixa:
tabela de transicao de NUMERO (5 estados)
q0 inicial
'-' -> q1
'0'..'9' -> q2
q1
'0'..'9' -> q2
q2 final
'.' -> q3
'0'..'9' -> q2
q3
'0'..'9' -> q4
q4 final
'0'..'9' -> q4Cinco estados, oito linhas. Sem o agrupamento em faixa seriam trinta e duas linhas, uma por dígito. E é aqui que as aspas simples se pagam: no autômato completado, o estado de erro recebe a faixa que vai do hífen ao ponto, e ela sai como '-'..'.' — sem as aspas seria --., que ninguém consegue ler.
O que quero deixar registrado sobre esta entrega é que ela é a última em que se constrói autômato à mão. A partir do módulo 4 a expressão regular vira autômato por algoritmo, e o trabalho manual feito aqui passa a servir de gabarito: o autômato que o algoritmo produzir para -?[0-9]+(\.[0-9]+)? deve reconhecer exatamente as mesmas cadeias que este, e é contra este que ele será conferido.