%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["afdIdentificador()"] --> B["faixa('a', 'z') e faixa('0', '9'): o alfabeto de 37 simbolos"]
B --> C["Afd(letras + digitos + '_', 2, 0)"]
C --> D["erro_(quantidadeDeEstados): o estado de erro fica com o indice 2"]
D --> E{"coluna < alfabeto_.size()"}
E -- "sim" --> F["colunaDoByte_[byte] = coluna"]
F --> E
E -- "nao: as 37 colunas mapeadas" --> G["tabela_.assign((quantidadeDeEstados + 1) * alfabeto_.size(), erro_)"]
G --> H["111 posicoes, todas apontando para erro_"]
H --> I["nomearEstado(0, 'inicio') e nomearEstado(1, 'corpo')"]
I --> J{"estado < nomes_.size()"}
J -- "sim" --> K["nomes_[estado] = std::move(nome)"]
J -- "nao" --> L["a chamada nao registra nada"]
K --> M["definirTransicoes(origem, simbolos, destino)"]
L --> M
M --> N{"para cada simbolo de simbolos"}
N -- "proximo simbolo" --> O["definirTransicao(origem, simbolo, destino)"]
O --> P{"coluna == kSemColuna #124;#124; origem >= aceitacao_.size()"}
P -- "sim" --> Q["retorna sem escrever: o par continua indo para erro_"]
P -- "nao" --> R["tabela_[origem * alfabeto_.size() + coluna] = destino"]
Q --> N
R --> N
N -- "os simbolos acabaram" --> S["marcarAceitacao(1)"]
S --> T{"estado < aceitacao_.size()"}
T -- "sim" --> U["aceitacao_[1] = 1"]
T -- "nao" --> V["a marca nao se registra"]
U --> W["63 das 111 posicoes deixaram de apontar para erro_"]
V --> W
1 Autômatos finitos determinísticos — Projeto do Professor
Aqui estão as tarefas do Projeto Integrador deste módulo resolvidas pelo professor, do começo ao fim, com cada decisão justificada. É o projeto de referência: o modelo do que o seu grupo vai produzir no próprio projeto, para estudar, e não para copiar. A representação que você escolhe, as máquinas que projeta e a conta que registra são suas. Daqui se leva o acabamento e o hábito de medir antes de afirmar.
1.1 Visão Geral
Até aqui a Peneira sabia descrever conjuntos de cadeias, mas não lia nenhuma. Neste módulo ela ganha a máquina que lê: recebe valor_2, consome um caractere por vez e responde se a cadeia pertence à linguagem. São duas tarefas, e a ordem entre elas importa. A primeira decide como guardar a função de transição, e é a primeira decisão do projeto cujo custo sai medido em memória, e não estimado. A segunda executa, sobre uma cadeia, uma máquina descrita à mão, e diz se ela aceita ou recusa.
Por que à mão, se o módulo seguinte traz um gerador? Justamente por causa dele. Quando a construção de Thompson começar a produzir máquinas sozinha e uma cadeia válida for recusada, a culpa pode ser da máquina ou de quem a executa. Com um executor já testado contra máquinas conhecidas, metade dessa dúvida está resolvida antes de aparecer.
A teoria do módulo também tem código aqui, e cada peça dela tem endereço. A quíntupla da definição formal vira a estrutura da classe. A função de transição total vira um estado de erro do qual não se sai. A configuração e o passo de computação viram o traço que a execução guarda. Projetar um autômato a partir de uma especificação vira as três máquinas escritas no fim do arquivo. Por baixo de tudo corre o tratamento da entrada inválida, que decide se o sistema recusa a cadeia ou termina de um jeito que ninguém sabe prever.
O código compila com avisos tratados como erro e roda no binário desta etapa do percurso, ao lado dos binários das três anteriores, que continuam sendo construídos e executados. Se os três seguem passando, a peça nova entrou sem quebrar o que já funcionava, e ninguém precisou reler tudo para saber.
1.2 Tarefa 1: Decidir a representação da função de transição
O que a tarefa pede
Escolher como armazenar a função de transição da máquina e justificar a escolha por escrito, dizendo quanto a representação ocupa em função do tamanho do alfabeto e do número de estados, e qual alternativa foi descartada e por quê. É a primeira decisão do percurso que cobra preço mensurável, e o hábito de registrar a conta será exigido de novo, em escala maior, no fecho do sistema.
Ficamos com a matriz densa e descartamos o mapa esparso. O documento de decisão traz a conta completa, as duas razões do descarte (o custo de cada consulta e a forma do que o sistema emite no fim) e a parte da decisão que ficou adiada.
docs/03_representacao_transicao.md
# A representação da função de transição — decisão e a conta
Guardar a função de transição é a primeira escolha da Peneira cujo custo se mede
em bytes. Ela vem com a conta escrita, e não com uma preferência.
## O que foi escolhido
**Matriz densa**, indexada por estado e por coluna de símbolo. A coluna sai de um
mapeamento byte → coluna, calculado uma vez no construtor, e consultar uma
transição custa uma multiplicação, uma soma e um acesso a vetor.
A função é **total**. Existe um estado de erro absorvente, e toda posição da
tabela nasce apontando para ele. Quem monta a máquina declara só as transições que
existem, cada uma sobrescrevendo uma posição, e nunca precisa preencher o resto.
## A conta
Seja `n` o número de estados úteis e `m` o tamanho do alfabeto declarado. A
tabela tem `(n + 1) × m` posições, cada uma de `sizeof(Estado)` bytes:
bytes = (n + 1) × m × sizeof(Estado)
O `+ 1` é o estado de erro. Com `Estado` de 8 bytes nesta plataforma, os três
autômatos projetados à mão ocupam:
| Autômato | Estados úteis | Alfabeto | Posições | Bytes | Transições não-erro |
| ----------------- | ------------: | -------: | -------: | ----: | ------------------: |
| identificador | 2 | 37 | 111 | 888 | 63 |
| número com sinal | 4 | 13 | 65 | 520 | 43 |
| comentário | 3 | 28 | 112 | 896 | 30 |
Os números saem da própria demonstração, que chama `bytesDaTabela()` e
`transicoesDefinidas()` para cada máquina e imprime o resultado. Copiada à mão, a
tabela poderia divergir do código sem que nada acusasse, e uma conta errada com
cara de medida engana mais do que conta nenhuma.
**A coluna não é o byte.** Indexar a tabela pelo código do caractere daria 256
colunas por estado. Para o autômato de número, seriam 256 colunas em vez de 13,
quase vinte vezes mais memória para a mesma máquina. O mapeamento byte → coluna
custa um vetor de 256 entradas **por autômato**, e não por estado, e deixa de
pesar assim que a máquina passa de um punhado de estados.
## A alternativa descartada
**Mapa esparso**: uma tabela de dispersão que leva `(estado, símbolo)` ao destino
e guarda só as transições que existem.
Em memória, ele ganha, e a última coluna da tabela acima diz por quanto. O
autômato de comentário tem 112 posições e só 30 transições que não vão para o
erro: três quartos da tabela guardam o mesmo valor. O de número é o menos
desperdiçado dos três, com 43 de 65, e ainda assim um terço das posições dele vai
para o erro. As máquinas que a determinização vai produzir, dois módulos adiante,
são maiores, e nelas a proporção piora.
Descartamos o mapa mesmo assim, por duas razões que a memória não mede.
A primeira é o custo por símbolo consumido. O reconhecimento faz **uma** consulta
de transição para cada símbolo do texto de entrada, e a Peneira processa texto
inteiro. Trocar o acesso a vetor por um cálculo de hash multiplica o custo da
operação mais frequente do sistema por uma constante que não é pequena, e o
reconhecimento deixa de ser previsivelmente linear.
A segunda é a que o enunciado da tarefa antecipa, e pesa mais: **a tabela de
transição não é só estrutura interna do reconhecedor**. É também a forma do que o
sistema emite no fim, quando o objeto produzido tiver de carregar as máquinas
construídas a partir da descrição lida. Uma matriz densa é um bloco contíguo de
inteiros, que se grava e se carrega como está. Um mapa esparso teria de ser
serializado, e a escolha do formato voltaria no módulo de geração de código,
quando já não há tempo de refazer.
## O que fica em aberto, e onde volta
A escolha vale para as máquinas de agora. Quando a determinização produzir
máquinas com muitos estados sobre alfabetos largos, o desperdício da matriz densa
fica visível, e há uma saída intermediária conhecida: a **compressão por linhas
equivalentes**, em que estados com linhas de transição idênticas passam a
compartilhar uma linha só. O acesso continua em tempo constante, e boa parte da
memória volta.
A decisão fica adiada, com lugar marcado, e não esquecida. A conta se refaz no
módulo da minimização, com os números daquelas máquinas, e não com os destas três.O documento começa admitindo que a matriz perde em memória, e perde feio. Na máquina de comentário, 82 das 112 posições guardam o mesmo destino, o erro: três quartos da tabela existem para dizer que não. Uma justificativa que só listasse as vantagens da opção escolhida seria propaganda. Descartamos o mapa esparso sabendo quanto ele economizaria.
O que decidiu foi o custo de cada consulta, e não o total de memória. O reconhecimento consulta a tabela uma vez por símbolo do texto de entrada, e a Peneira processa texto inteiro. Na matriz, a consulta é uma multiplicação, uma soma e um acesso a vetor. No mapa, entra um cálculo de hash justo na operação que o sistema mais repete, e o tempo do reconhecimento deixa de ser previsivelmente linear no tamanho do texto.
Nenhum número da tabela foi copiado à mão. Todos saem de bytesDaTabela() e transicoesDefinidas(), chamadas pela demonstração para cada máquina. Uma tabela de decisão que divergisse do que o código imprime seria pior que tabela nenhuma, porque teria cara de verificada.
Um detalhe da conta escapa a quase todo mundo: a coluna não é o código do caractere. Indexada pelo byte, a máquina de número teria 256 colunas por estado em vez de treze, quase vinte vezes a memória, para representar a mesma máquina. O vetor que traduz byte em coluna custa 256 entradas por autômato, e não por estado, e deixa de pesar assim que a máquina passa de um punhado de estados.
Adiar e omitir deixam o mesmo silêncio no código, e só o registro separa um do outro. A matriz densa começa a desperdiçar de forma visível quando a determinização produzir máquinas com muitos estados sobre alfabetos largos. Para esse momento existe uma saída intermediária conhecida: estados com linhas de transição idênticas passam a compartilhar uma linha só, o que devolve boa parte da memória sem perder o acesso em tempo constante. Não a implementamos agora porque a conta que a justificaria é a das máquinas daquele módulo, e não a destas três, mas o documento diz onde refazê-la. Decisão registrada como adiada volta à mesa; a que não foi registrada vira, alguns módulos depois, “sempre foi assim”.
Onde é fácil errar. Escolher a representação mais cômoda de escrever hoje e só descobrir o custo quando a determinização entregar a primeira máquina com centenas de estados. Como conferir. Escreva a fórmula do consumo em função do número de estados e do tamanho do alfabeto, calcule-a para as suas máquinas atuais e faça o programa imprimir o mesmo valor. Se os dois números não baterem, o erro está na fórmula, e é com ela, e não com a medição, que você vai decidir daqui em diante.
1.3 Tarefa 2: Executar uma máquina descrita à mão
O que a tarefa pede
Implementar a execução de uma máquina de estados, descrita à mão, sobre uma cadeia de entrada, reportando aceitação ou recusa. E tratar explicitamente o símbolo para o qual não há transição prevista — o caso que a definição formal costuma resolver com uma frase e que, no código, decide se o sistema recusa a cadeia ou termina de forma imprevisível diante de uma entrada que ninguém antecipou.
03_afd.h
// 03_afd.h — o autômato finito determinístico: a quíntupla como classe, e a
// execução que guarda o traço de configurações.
//
// A função de transição é total: um estado de erro absorvente, criado no
// construtor, é o destino de todo par (estado, símbolo) que ninguém declarou, e
// a execução nunca pergunta se a transição existe. A tabela é uma matriz densa
// indexada por estado e coluna; a coluna vem de um mapeamento byte -> coluna, e
// não do código do caractere, que daria 256 colunas por estado. A conta que
// sustenta a matriz está em docs/03_representacao_transicao.md.
#ifndef PENEIRA_03_AFD_H
#define PENEIRA_03_AFD_H
#include <cstddef>
#include <string>
#include <vector>
namespace peneira {
using Estado = std::size_t;
// Uma configuração é o par (estado corrente, posição na cadeia). A execução
// guarda a sequência delas, que é como a definição descreve o reconhecimento.
struct Configuracao {
Estado estado = 0;
std::size_t posicao = 0;
char simboloLido = '\0'; // o símbolo que levou a esta configuração
};
struct Execucao {
bool aceitou = false;
std::vector<Configuracao> passos;
// Posição do primeiro símbolo que levou ao erro; `std::string::npos` quando
// a execução nunca caiu nele.
std::size_t posicaoDaQueda = std::string::npos;
bool simboloForaDoAlfabeto = false;
};
class Afd {
public:
// `quantidadeDeEstados` conta só os estados úteis; o de erro recebe o índice
// seguinte. Toda posição da tabela nasce apontando para ele, e definir uma
// transição é sobrescrever uma dessas posições.
Afd(std::string alfabeto, std::size_t quantidadeDeEstados, Estado inicial);
// Autômato degenerado: só o estado de erro, alfabeto vazio, recusa tudo.
// Permite que um Afd seja membro de uma struct de resultado e receba o valor
// depois; a alternativa seria ponteiro ou optional em quem o devolve.
Afd();
void definirTransicao(Estado origem, char simbolo, Estado destino);
void definirTransicoes(Estado origem, const std::string& simbolos, Estado destino);
void marcarAceitacao(Estado estado);
void nomearEstado(Estado estado, std::string nome);
Estado estadoDeErro() const;
// Usados pela determinização (módulo 05): construir um AFD a partir de outro
// exige percorrer o alfabeto e saber onde a execução começa.
Estado estadoInicial() const;
const std::string& alfabeto() const;
Estado transicao(Estado origem, char simbolo) const;
bool ehDeAceitacao(Estado estado) const;
const std::string& nomeDoEstado(Estado estado) const;
// Consome a cadeia inteira e diz se parou em estado de aceitação.
bool aceita(const std::string& cadeia) const;
// O mesmo reconhecimento, guardando a configuração alcançada a cada símbolo.
Execucao executar(const std::string& cadeia) const;
// (estados + 1) x |alfabeto| x sizeof(Estado).
std::size_t bytesDaTabela() const;
// Posições cujo destino não é o erro. O que falta para o total é o que a
// matriz densa guarda a mais que um mapa esparso.
std::size_t transicoesDefinidas() const;
std::size_t quantidadeDeEstados() const;
std::size_t tamanhoDoAlfabeto() const;
std::string formatarTabela() const;
std::string formatarExecucao(const std::string& cadeia, const Execucao& execucao) const;
private:
std::size_t colunaDe(char simbolo) const;
static constexpr std::size_t kSemColuna = static_cast<std::size_t>(-1);
// recorte:inicio quintupla-como-estrutura
std::string alfabeto_;
std::vector<std::size_t> colunaDoByte_; // 256 entradas: byte -> coluna
std::vector<Estado> tabela_; // (estados+1) x |alfabeto|
// `char`, e não `bool`: vector<bool> empacota bits e não devolve referência
// de verdade.
std::vector<char> aceitacao_;
std::vector<std::string> nomes_;
Estado inicial_ = 0;
Estado erro_ = 0;
// recorte:fim quintupla-como-estrutura
};
// Três autômatos projetados à mão, cada um a partir de uma especificação em
// prosa. O gerador só chega no módulo 04; um executor já testado contra máquinas
// conhecidas separa, ali, erro de construção de erro de execução.
Afd afdIdentificador();
Afd afdNumeroComSinal();
Afd afdComentarioDeLinha();
} // namespace peneira
#endif // PENEIRA_03_AFD_H03_afd.cpp
#include "03_afd.h"
namespace peneira {
namespace {
std::string preencher(const std::string& texto, const std::size_t largura) {
std::string resultado = texto;
while (resultado.size() < largura) {
resultado += ' ';
}
return resultado;
}
// Os símbolos de `inicio` a `fim`, pelo código do caractere; monta os alfabetos
// das três máquinas.
std::string faixa(const char inicio, const char fim) {
std::string simbolos;
for (int codigo = static_cast<unsigned char>(inicio); codigo <= static_cast<unsigned char>(fim);
++codigo) {
simbolos += static_cast<char>(codigo);
}
return simbolos;
}
} // namespace
Afd::Afd(std::string alfabeto, const std::size_t quantidadeDeEstados, const Estado inicial)
: alfabeto_(std::move(alfabeto)),
colunaDoByte_(256, kSemColuna),
aceitacao_(quantidadeDeEstados + 1, 0),
nomes_(quantidadeDeEstados + 1),
inicial_(inicial),
erro_(quantidadeDeEstados) {
// recorte:inicio coluna-nao-e-o-byte
for (std::size_t coluna = 0; coluna < alfabeto_.size(); ++coluna) {
const std::size_t byte = static_cast<unsigned char>(alfabeto_[coluna]);
colunaDoByte_[byte] = coluna;
}
// recorte:fim coluna-nao-e-o-byte
// recorte:inicio transicao-total-por-construcao
// Toda posição nasce apontando para o erro: quem monta a máquina declara só
// as transições que existem, e a função já sai total.
tabela_.assign((quantidadeDeEstados + 1) * alfabeto_.size(), erro_);
// recorte:fim transicao-total-por-construcao
for (std::size_t estado = 0; estado <= quantidadeDeEstados; ++estado) {
nomes_[estado] = "q" + std::to_string(estado);
}
nomes_[erro_] = "erro";
}
Afd::Afd()
: colunaDoByte_(256, kSemColuna), aceitacao_(1, 0), nomes_(1, "erro"), inicial_(0), erro_(0) {}
std::size_t Afd::colunaDe(const char simbolo) const {
return colunaDoByte_[static_cast<unsigned char>(simbolo)];
}
void Afd::definirTransicao(const Estado origem, const char simbolo, const Estado destino) {
const std::size_t coluna = colunaDe(simbolo);
if (coluna == kSemColuna || origem >= aceitacao_.size()) {
// Símbolo fora do alfabeto ou estado inexistente: retorna sem escrever, e
// o par continua indo para o erro. Lançar pegaria o erro de digitação na
// hora, mas obrigaria cada chamada de construção a tratar a falha.
return;
}
tabela_[origem * alfabeto_.size() + coluna] = destino;
}
void Afd::definirTransicoes(const Estado origem, const std::string& simbolos,
const Estado destino) {
for (const char simbolo : simbolos) {
definirTransicao(origem, simbolo, destino);
}
}
void Afd::marcarAceitacao(const Estado estado) {
if (estado < aceitacao_.size()) {
aceitacao_[estado] = 1;
}
}
void Afd::nomearEstado(const Estado estado, std::string nome) {
if (estado < nomes_.size()) {
nomes_[estado] = std::move(nome);
}
}
Estado Afd::estadoDeErro() const { return erro_; }
Estado Afd::estadoInicial() const { return inicial_; }
const std::string& Afd::alfabeto() const { return alfabeto_; }
// recorte:inicio tabela-densa-indexada
Estado Afd::transicao(const Estado origem, const char simbolo) const {
const std::size_t coluna = colunaDe(simbolo);
if (coluna == kSemColuna) {
return erro_;
}
return tabela_[origem * alfabeto_.size() + coluna];
}
// recorte:fim tabela-densa-indexada
bool Afd::ehDeAceitacao(const Estado estado) const { return aceitacao_[estado] != 0; }
const std::string& Afd::nomeDoEstado(const Estado estado) const { return nomes_[estado]; }
// diagrama:adiado quem só precisa do sim ou não é a bateria do AFN (04), a equivalência da determinização (05) e o marco 06; o marco 03 percorre pela executar(), a mesma travessia com o traço registrado
// recorte:inicio aceita-em-quatro-linhas
bool Afd::aceita(const std::string& cadeia) const {
Estado atual = inicial_;
for (const char simbolo : cadeia) {
atual = transicao(atual, simbolo);
}
return ehDeAceitacao(atual);
}
// recorte:fim aceita-em-quatro-linhas
// recorte:inicio queda-registrada-sem-parar
Execucao Afd::executar(const std::string& cadeia) const {
Execucao execucao;
Estado atual = inicial_;
execucao.passos.push_back(Configuracao{atual, 0, '\0'});
for (std::size_t i = 0; i < cadeia.size(); ++i) {
const char simbolo = cadeia[i];
const bool foraDoAlfabeto = colunaDe(simbolo) == kSemColuna;
const Estado proximo = transicao(atual, simbolo);
execucao.passos.push_back(Configuracao{proximo, i + 1, simbolo});
// Registra só a primeira queda e segue lendo. Parar daria a mesma
// resposta, mas o traço terminaria antes da cadeia e não mostraria o erro
// absorvendo o resto dela.
if (proximo == erro_ && execucao.posicaoDaQueda == std::string::npos) {
execucao.posicaoDaQueda = i;
execucao.simboloForaDoAlfabeto = foraDoAlfabeto;
}
atual = proximo;
}
execucao.aceitou = ehDeAceitacao(atual);
return execucao;
}
// recorte:fim queda-registrada-sem-parar
// recorte:inicio bytes-da-tabela
std::size_t Afd::bytesDaTabela() const { return tabela_.size() * sizeof(Estado); }
std::size_t Afd::transicoesDefinidas() const {
std::size_t total = 0;
for (const Estado destino : tabela_) {
if (destino != erro_) {
++total;
}
}
return total;
}
// recorte:fim bytes-da-tabela
std::size_t Afd::quantidadeDeEstados() const { return aceitacao_.size(); }
std::size_t Afd::tamanhoDoAlfabeto() const { return alfabeto_.size(); }
std::string Afd::formatarTabela() const {
// Por faixa de colunas com o mesmo destino, e não coluna a coluna: o
// alfabeto do identificador daria trinta e sete colunas por linha. Cada
// estado lista os destinos que não são o erro e os símbolos que levam a eles.
std::string texto;
texto += preencher("ESTADO", 14) + preencher("ACEITA", 8) + "TRANSICOES\n";
for (std::size_t estado = 0; estado < aceitacao_.size(); ++estado) {
texto += preencher(nomes_[estado], 14);
texto += preencher(aceitacao_[estado] != 0 ? "sim" : "nao", 8);
bool primeiro = true;
for (std::size_t coluna = 0; coluna < alfabeto_.size(); ++coluna) {
const Estado destino = tabela_[estado * alfabeto_.size() + coluna];
if (destino == erro_) {
continue;
}
// Estende a faixa enquanto a coluna seguinte levar ao mesmo destino:
// os dez dígitos saem numa entrada só.
std::size_t fimDaFaixa = coluna;
while (fimDaFaixa + 1 < alfabeto_.size() &&
tabela_[estado * alfabeto_.size() + fimDaFaixa + 1] == destino) {
++fimDaFaixa;
}
if (!primeiro) {
texto += ", ";
}
const std::size_t quantidade = fimDaFaixa - coluna + 1;
if (quantidade <= 3) {
// Até três símbolos, um a um: `+ -` escrito como faixa sugeriria
// um intervalo de códigos que não existe.
for (std::size_t i = coluna; i <= fimDaFaixa; ++i) {
if (i > coluna) {
texto += ' ';
}
texto += alfabeto_[i];
}
} else {
// A faixa é por posição no alfabeto declarado, não por código do
// caractere. A contagem entre colchetes impede que `a.._ [37]`
// seja lido como intervalo ASCII.
texto += alfabeto_[coluna];
texto += "..";
texto += alfabeto_[fimDaFaixa];
texto += " [" + std::to_string(quantidade) + "]";
}
texto += " -> " + nomes_[destino];
primeiro = false;
coluna = fimDaFaixa;
}
if (primeiro) {
texto += "(todas para erro)";
}
texto += '\n';
}
return texto;
}
std::string Afd::formatarExecucao(const std::string& cadeia, const Execucao& execucao) const {
std::string texto = " cadeia: \"" + cadeia + "\"\n";
texto += " configuracoes: ";
for (std::size_t i = 0; i < execucao.passos.size(); ++i) {
const Configuracao& passo = execucao.passos[i];
if (i > 0) {
texto += " -";
texto += passo.simboloLido;
texto += "-> ";
}
texto += nomes_[passo.estado];
}
texto += '\n';
texto += std::string(" resultado: ") + (execucao.aceitou ? "ACEITA" : "RECUSA");
if (!execucao.aceitou && execucao.posicaoDaQueda != std::string::npos) {
texto += " — caiu no erro na posicao " + std::to_string(execucao.posicaoDaQueda);
texto += execucao.simboloForaDoAlfabeto ? " (simbolo fora do alfabeto declarado)"
: " (simbolo valido, transicao inexistente)";
} else if (!execucao.aceitou) {
texto += " — consumiu a cadeia inteira e parou em estado nao final";
}
texto += '\n';
return texto;
}
// --- os três autômatos projetados à mão --------------------------------------
// Especificação: uma letra minúscula seguida de qualquer número de letras
// minúsculas, dígitos ou sublinhados. Dois estados: nada lido ainda, e a
// primeira letra já lida.
Afd afdIdentificador() {
const std::string letras = faixa('a', 'z');
const std::string digitos = faixa('0', '9');
Afd afd(letras + digitos + "_", 2, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "corpo");
afd.definirTransicoes(0, letras, 1);
afd.definirTransicoes(1, letras, 1);
afd.definirTransicoes(1, digitos, 1);
afd.definirTransicao(1, '_', 1);
afd.marcarAceitacao(1);
return afd;
}
// Especificação: sinal opcional, ao menos um dígito e, opcionalmente, um ponto
// seguido de ao menos um dígito. Cada estado é uma resposta diferente a "o que
// falta para a cadeia ser válida?". `apos_ponto` não aceita: um número não
// termina em ponto.
Afd afdNumeroComSinal() {
const std::string digitos = faixa('0', '9');
Afd afd(digitos + "+-.", 4, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "inteiro");
afd.nomearEstado(2, "apos_ponto");
afd.nomearEstado(3, "fracao");
afd.definirTransicao(0, '+', 0);
afd.definirTransicao(0, '-', 0);
afd.definirTransicoes(0, digitos, 1);
afd.definirTransicoes(1, digitos, 1);
afd.definirTransicao(1, '.', 2);
afd.definirTransicoes(2, digitos, 3);
afd.definirTransicoes(3, digitos, 3);
afd.marcarAceitacao(1);
afd.marcarAceitacao(3);
return afd;
}
// Especificação: duas barras e qualquer coisa até o fim da linha. O alfabeto é
// estreito (barra, espaço e minúsculas) para que a demonstração possa recusar
// por símbolo fora dele, e não só por transição inexistente.
Afd afdComentarioDeLinha() {
const std::string letras = faixa('a', 'z');
Afd afd("/ " + letras, 3, 0);
afd.nomearEstado(0, "inicio");
afd.nomearEstado(1, "uma_barra");
afd.nomearEstado(2, "no_comentario");
afd.definirTransicao(0, '/', 1);
afd.definirTransicao(1, '/', 2);
afd.definirTransicao(2, '/', 2);
afd.definirTransicao(2, ' ', 2);
afd.definirTransicoes(2, letras, 2);
afd.marcarAceitacao(2);
return afd;
}
} // namespace peneiraA classe Afd é a quíntupla da definição escrita como estrutura de dados, com um campo para cada componente matemático. O símbolo sem transição prevista, que a tarefa manda tratar, deixa de ser caso especial porque a função é total por construção. O construtor enche a tabela inteira com o estado de erro, e cada transição declarada sobrescreve uma posição. Quando chega um símbolo que ninguém previu, a consulta devolve o erro como devolveria qualquer outro destino, e a execução segue. A alternativa seria perguntar a cada passo se a transição existe. Isso põe um teste na operação que o sistema mais repete e deixa para cada ponto de chamada a decisão sobre o que fazer quando a resposta é não.
Do estado de erro não se sai, e por isso ele se chama absorvente. É a única parte da máquina que nunca muda de ideia. Daí vem uma escolha que soa estranha na execução: ao cair no erro, ela anota a posição e continua lendo a cadeia até o fim. Parando ali, a resposta seria a mesma, mas o traço não mostraria o autômato preso no erro, símbolo após símbolo, que é o que “absorvente” quer dizer.
O reconhecimento existe em duas versões. aceita() devolve só o sim ou o não, e é a que o resto do sistema vai usar. executar() percorre a mesma cadeia guardando cada configuração, o par de estado corrente e posição na cadeia, e é a que a demonstração chama para imprimir a sequência que a definição descreve.
A demonstração separa duas coisas que muita implementação mistura: há duas maneiras de uma cadeia cair no erro, e elas pedem mensagens diferentes. 2valor cai porque o dígito, embora pertença ao alfabeto declarado, não tem transição a partir do estado inicial, já que identificador não começa com número. //OK cai porque as maiúsculas nem constam do alfabeto daquela máquina. As duas terminam no erro, e o relatório diz qual foi qual, porque quem lê a mensagem precisa saber se escreveu algo inválido ou algo que a máquina nem sabe ler.
E há uma terceira recusa, que não passa pelo erro. 42. é lida até o fim sem nenhuma queda e, mesmo assim, é recusada: a máquina para num estado que não é de aceitação, porque número não termina em ponto. Quem implementa esquece esse caso mais que os outros dois, e o esquecimento produz o defeito clássico de aceitar cadeias pela metade.
Onde é fácil errar. Responder ao símbolo sem transição com uma exceção, ou encerrando o programa. O reconhecedor vai receber, mais tarde, texto arbitrário escrito por quem usa a linguagem, e para esse texto recusar é uma resposta; abortar, não. Como conferir. Submeta à sua máquina três cadeias: uma que ela aceita, uma que cai no erro e uma que é lida inteira e para em estado não final. Se as duas últimas produzem a mesma mensagem, falta uma distinção; se alguma derruba o programa, a sua função de transição ainda não é total.
1.4 Da quíntupla ao código, campo a campo
A definição formal de um autômato finito determinístico é a quíntupla
M = (Q, \Sigma, \delta, q_0, F)
em que Q é o conjunto finito de estados, \Sigma o alfabeto, \delta : Q \times \Sigma \to Q a função de transição, q_0 \in Q o estado inicial e F \subseteq Q o conjunto de estados de aceitação. Com 03_afd.h aberto ao lado, a correspondência se lê campo a campo. Q são os índices de estado, \Sigma é a cadeia alfabeto_ declarada no construtor, \delta é o vetor tabela_, q_0 é o campo inicial_ e F é o vetor de marcas aceitacao_. Nada no código fica sem par na definição.
A seta de \delta carrega uma exigência que a notação quase esconde: \delta é uma função total, com destino para todo par de estado e símbolo, sem exceção. Muitos livros desenham autômatos com transições faltando e resolvem a lacuna numa frase, dizendo que ali o autômato rejeita. Acontece que em código essa frase não existe. Ou a lacuna é preenchida, ou toda consulta precisa devolver algo que signifique “não há”. Nós preenchemos, e o preenchimento tem nome: o estado sumidouro, que a literatura também chama de estado morto e que aqui se chama erro.
A totalidade custa memória, e a conta já está feita: de um terço a três quartos da tabela de cada máquina aponta para o erro. É o desperdício que a Tarefa 1 mediu, visto agora como consequência de uma exigência da definição, e não como escolha de estrutura.
Formalmente, uma configuração é o par (q, w) do estado corrente com o sufixo ainda não lido da cadeia. O passo de computação leva (q, aw) a (\delta(q, a), w): consome um símbolo e muda de estado. A cadeia w é reconhecida quando a sequência de passos que parte de (q_0, w) chega a (q, \varepsilon) com q \in F.
No código, a configuração guarda a posição em vez do sufixo. A informação é a mesma, porque o sufixo é tudo o que vem depois da posição, e guardar um índice evita alocar uma cadeia nova a cada passo. A demonstração imprime essa sequência inteira: em vez de afirmar que a máquina aceita valor_2, ela mostra as oito configurações por onde a leitura passou. Um traço que termina em estado de aceitação é uma prova; um resultado sem traço é só um resultado.
1.5 Projetar a máquina a partir da especificação em prosa
Até aqui as máquinas chegaram prontas. Projetar é o caminho inverso: partir de uma frase como “uma letra minúscula seguida de letras, dígitos ou sublinhados” e chegar aos estados. As três máquinas do fim de 03_afd.cpp foram construídas com uma pergunta só: qual é a menor distinção que a especificação obriga a lembrar?
A pergunta funciona porque um estado é uma memória, e não um lugar no desenho. O autômato não guarda o que leu, só a situação em que a leitura o deixou, e projetar é descobrir quantas situações diferentes a especificação exige.
No identificador, a primeira posição aceita letra e as seguintes aceitam letra, dígito ou sublinhado. São duas situações: nada lido ainda, ou a primeira letra já lida. Dois estados, nenhum a mais. A segunda posição e a quinta aceitam exatamente o mesmo conjunto de símbolos, e nas duas a cadeia lida até ali já é válida; não há o que as distinga.
O número com sinal pede quatro estados, e o que merece cuidado é apos_ponto. Depois do ponto e antes de qualquer dígito, a cadeia não é válida, mas ainda pode vir a ser. Essa situação difere tanto de “li dígitos, posso parar” quanto de “li dígitos depois do ponto, posso parar”. Quem projeta pela primeira vez costuma esquecer esse estado, e a máquina que resulta aceita 42., justamente o caso negativo que a demonstração executa. O sinal, ao contrário, não cria estado nenhum: a transição de + ou - volta ao próprio estado inicial, porque ler um sinal não muda nada no que ainda falta. Um estado a mais ali seria estado sem distinção, o tipo de excesso que a minimização, dois módulos adiante, remove sozinha.
A máquina de comentário de linha tem alfabeto estreito de propósito, e vale menos pelo que reconhece do que pelo contraste que permite. Com poucos símbolos no alfabeto, fica fácil submeter uma cadeia com um que nem consta dele e ver acontecer a segunda forma de recusa.
Onde é fácil errar. Criar um estado por posição da cadeia, e não por situação distinta. A máquina passa nos exemplos testados, mas cresce sem limite conforme as cadeias ficam maiores: ela está descrevendo entradas, e não a linguagem. Como conferir. Para cada par de estados da sua máquina, procure uma cadeia aceita a partir de um e recusada a partir do outro. Se algum par não tiver essa cadeia, os dois são o mesmo estado escrito duas vezes. A minimização vai fundi-los mais adiante, o que confirma o diagnóstico, mas não conserta o projeto.
1.6 Por dentro da implementação
Falta ver o percurso: quem chama quem, em que ordem, e com que valores no instante em que o código decide. Tudo o que segue sai de execuções reais do binário desta etapa.
A costura com o que já existia é curta: 03_afd.cpp não chama nada dos módulos anteriores. A máquina recebe uma cadeia e devolve uma resposta, e nem as operações sobre cadeias e linguagens nem o analisador de expressões participam disso. O contato acontece no sentido oposto, e mais tarde: aceita() nasce aqui, mas só passa a ser chamada de fora na determinização, quando duas máquinas precisarem ser comparadas cadeia a cadeia. Por isso ela não aparece nos diagramas abaixo. A demonstração desta etapa executa a máquina por executar(), e desenhar um cenário para uma função que este binário não chama seria desenhar uma execução imaginada.
Quem abrir o arquivo do encadeamento de fases ao lado vai encontrar outra preencher(). São duas funções, cada uma fechada no seu arquivo; as duas completam um texto com espaços, e nenhuma enxerga a outra.
1.6.1 As alterações deste módulo
O módulo acrescenta um arquivo, e nele quatro percursos que não existiam. Cada um tem, a seguir, uma execução própria e um par de diagramas, o fluxo e a sequência. Nenhum traz pilha de chamadas: o arquivo não tem recursão nem aninhamento, o percurso mais fundo tem três quadros e é linear, e uma pilha desenhada ali sugeriria uma verificação que não houve.
| Alteração | O que passou a acontecer |
|---|---|
tabela-total-por-construcao |
A tabela passa a nascer inteira apontando para o estado de erro, e declarar uma transição passa a ser sobrescrever uma posição que já tinha destino. |
queda-registrada-sem-parar |
A execução passa a guardar a configuração alcançada a cada símbolo, e a primeira queda no erro passa a ser registrada sem interromper a leitura. |
duas-formas-de-recusar |
A recusa passa a carregar, no próprio resultado, qual das três formas de recusar aconteceu. |
custo-da-matriz-densa |
A tabela passa a ser impressa por faixa de colunas com o mesmo destino, e o desperdício da matriz passa a sair medido ao lado dela. |
1.6.2 tabela-total-por-construcao — a tabela que já nasce correta
A primeira máquina que o binário constrói é a do identificador, e a linha que ele imprime abaixo da tabela resume o que a construção deixou pronto:
afdIdentificador() monta o alfabeto com duas chamadas a faixa(), vinte e seis letras e dez dígitos, acrescenta o sublinhado e entrega tudo ao construtor. Lá dentro, a ordem importa. Primeiro erro_ recebe o índice seguinte ao último estado útil; depois colunaDoByte_ ganha uma coluna por símbolo do alfabeto; só então tabela_ é preenchida com o próprio erro_ nas 111 posições. O preenchimento precisa do tamanho do alfabeto e do índice do erro já definidos, e por isso vem por último.
Em seguida, as três chamadas a definirTransicoes() e a chamada avulsa a definirTransicao() escrevem 63 das 111 posições. As outras 48 ficam com o valor que o construtor pôs, e é isso que “função total” quer dizer em código: 43% da tabela do identificador guarda o mesmo destino, o erro.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
autonumber
participant D as demos/03_demo.cpp
participant F as 03_afd.cpp
participant A as Afd
D->>F: afdIdentificador()
F->>F: faixa('a', 'z')
F-->>F: 26 simbolos, de 'a' a 'z'
F->>F: faixa('0', '9')
F-->>F: 10 simbolos, de '0' a '9'
F->>A: Afd(alfabeto de 37 simbolos, 2, 0)
A->>A: colunaDoByte_[byte] = coluna, uma vez por simbolo
A->>A: tabela_.assign(111, erro_)
A-->>F: maquina com erro_ = 2 e 111 posicoes no erro
F->>A: nomearEstado(0, "inicio")
F->>A: nomearEstado(1, "corpo")
F->>A: definirTransicoes(0, letras, 1)
A->>A: definirTransicao(0, 'a', 1), e mais 25 vezes
A-->>F: 26 posicoes escritas
F->>A: definirTransicoes(1, letras, 1)
A-->>F: mais 26 posicoes escritas
F->>A: definirTransicoes(1, digitos, 1)
A-->>F: mais 10 posicoes escritas
F->>A: definirTransicao(1, '_', 1)
A-->>F: a 63a posicao escrita
F->>A: marcarAceitacao(1)
A-->>F: aceitacao_[1] = 1
F-->>D: Afd com 3 estados (o de erro incluido), 111 posicoes e 63 transicoes nao-erro
definirTransicao() confere se o símbolo tem coluna e se o estado existe, e retorna sem escrever quando um dos dois falha. Poderia, em vez disso, devolver um sinal de falha ou lançar uma exceção, e obrigar quem monta a máquina a tratá-la. O erro de digitação seria pego na hora, e essa vantagem é real. Mas as três funções de construção somam dezesseis chamadas, que virariam dezesseis testes, e definirTransicoes() teria de decidir o que fazer depois de meia faixa escrita. Com o retorno silencioso, uma máquina montada com um símbolo fora do alfabeto recusa as cadeias que passariam por ele, e o traço da execução mostra exatamente onde. Como diagnóstico, isso diz mais que uma exceção no momento da construção.
1.6.3 queda-registrada-sem-parar — a execução que continua depois de cair
A cadeia é //OK, a última da demonstração, submetida à máquina de comentário:
A cada símbolo, o laço de executar() faz três coisas: pergunta a colunaDe() se o símbolo consta do alfabeto, chama transicao() para obter o destino e empilha a configuração alcançada. A ordem entre as duas primeiras é o que sustenta a alteração seguinte. O O maiúsculo não tem coluna, transicao() devolve erro_, e a guarda de posicaoDaQueda está aberta pela primeira vez: grava 2 e se fecha. No símbolo seguinte a guarda já está fechada; o K também cai no erro, e nada se sobrescreve.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["executar(cadeia), com cadeia = //OK"] --> B["passos.push_back(Configuracao{inicial_, 0, 0}): a configuracao de partida, no estado inicio"]
B --> C{"i < cadeia.size()"}
C -- "sim" --> D["foraDoAlfabeto = colunaDe(simbolo) == kSemColuna"]
D --> E["proximo = transicao(atual, simbolo)"]
E --> F{"coluna == kSemColuna"}
F -- "sim: 'O' nao consta do alfabeto declarado" --> G["devolve erro_"]
F -- "nao: '/' esta na coluna 0" --> H["devolve tabela_[origem * alfabeto_.size() + coluna]"]
G --> I["passos.push_back(Configuracao{proximo, i + 1, simbolo})"]
H --> I
I --> J{"proximo == erro_ && execucao.posicaoDaQueda == std::string::npos"}
J -- "sim: primeira queda, em i = 2" --> K["posicaoDaQueda = 2, simboloForaDoAlfabeto = true"]
J -- "nao: em i = 3 a queda ja estava registrada" --> L["nada se sobrescreve, e a leitura segue"]
K --> M["atual = proximo"]
L --> M
M --> C
C -- "nao: a cadeia acabou, com 5 configuracoes guardadas" --> N["execucao.aceitou = ehDeAceitacao(atual)"]
N --> O["aceitacao_[erro_] vale 0: RECUSA, com a queda na posicao 2"]
A sequência deixa à vista um detalhe que o fonte não destaca: transicao() é chamada também depois da queda, com o próprio erro_ como origem. É essa chamada que produz o segundo erro do traço. Com ela, a absorvência aparece na saída em vez de ficar só afirmada: a máquina foi consultada de novo e devolveu o mesmo estado.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
autonumber
participant D as demos/03_demo.cpp
participant A as Afd
D->>A: executar("//OK")
A->>A: transicao(inicio, '/')
A-->>A: uma_barra
A->>A: transicao(uma_barra, '/')
A-->>A: no_comentario
A->>A: colunaDe('O')
A-->>A: kSemColuna, simbolo fora do alfabeto declarado
A->>A: transicao(no_comentario, 'O')
A-->>A: erro_, e posicaoDaQueda passa a valer 2
A->>A: colunaDe('K')
A-->>A: kSemColuna, e a leitura continua assim mesmo
A->>A: transicao(erro_, 'K')
A-->>A: erro_, com posicaoDaQueda intacta em 2
A->>A: ehDeAceitacao(erro_)
A-->>A: false
A-->>D: Execucao com 5 passos, aceitou = false, posicaoDaQueda = 2, simboloForaDoAlfabeto = true
Interromper o laço na primeira queda seria a escolha óbvia, já que a resposta está decidida ali. O vetor de configurações deixaria então de ter sempre um passo a mais que o comprimento da cadeia, e o traço impresso acabaria antes da entrada. Quem lesse a linha de configurações teria dois motivos possíveis para ela terminar, a cadeia acabou ou a leitura foi abandonada, e só contando caracteres à mão saberia qual. A escolha feita gasta a leitura do resto da cadeia depois de a resposta estar decidida. Esse gasto só existe na versão com traço, que roda na demonstração e fica fora do reconhecimento que o resto do sistema usa.
1.6.4 duas-formas-de-recusar — a recusa que diz qual foi
Na mesma máquina de comentário, /x é recusada pelo outro motivo:
O x consta do alfabeto daquela máquina: ocupa a coluna 25, já que o alfabeto começa pela barra e pelo espaço e segue pelas vinte e seis minúsculas. colunaDe() devolve essa coluna, simboloForaDoAlfabeto fica falso, e a queda acontece assim mesmo, porque a posição da tabela para uma_barra e x nunca foi escrita. É essa diferença que o relatório precisa carregar, e ela se decide dentro de executar(), na linha anterior à consulta.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["formatarExecucao(cadeia, execucao), com cadeia = /x"] --> B{"i < execucao.passos.size()"}
B -- "sim" --> C{"i > 0"}
C -- "nao: a configuracao de partida" --> D["escreve nomes_[passo.estado]: inicio"]
C -- "sim" --> E["escreve o simbolo entre setas, e depois nomes_[passo.estado]: -x-> erro"]
D --> B
E --> B
B -- "nao: as 3 configuracoes escritas" --> F{"execucao.aceitou"}
F -- "sim" --> G["resultado: ACEITA"]
F -- "nao" --> H{"execucao.posicaoDaQueda != std::string::npos"}
H -- "nao: consumiu tudo e parou fora de aceitacao_" --> I["consumiu a cadeia inteira e parou em estado nao final"]
H -- "sim: caiu no erro na posicao 1" --> J{"execucao.simboloForaDoAlfabeto"}
J -- "false: 'x' consta do alfabeto, e nao ha transicao a partir de uma_barra" --> K["(simbolo valido, transicao inexistente)"]
J -- "true" --> L["(simbolo fora do alfabeto declarado)"]
formatarExecucao() só lê o que já foi decidido. Os dois testes encadeados no fim dela põem as três formas de recusar em ordem. Sem posição de queda, a cadeia foi lida inteira e parou fora do conjunto de aceitação; com posição de queda, o sinalizador escolhe entre as outras duas. Nenhum dos três ramos volta a consultar a máquina.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
autonumber
participant D as demos/03_demo.cpp
participant A as Afd
D->>A: executar("/x")
A->>A: transicao(inicio, '/')
A-->>A: uma_barra
A->>A: colunaDe('x')
A-->>A: coluna 25, simbolo declarado no alfabeto
A->>A: transicao(uma_barra, 'x')
A-->>A: erro_, porque a posicao da tabela nunca foi escrita
A-->>D: Execucao com posicaoDaQueda = 1 e simboloForaDoAlfabeto = false
D->>A: formatarExecucao("/x", execucao)
A-->>D: "configuracoes: inicio -/-> uma_barra -x-> erro"
A-->>D: "RECUSA — caiu no erro na posicao 1 (simbolo valido, transicao inexistente)"
O sinalizador é gravado durante a execução, e não deduzido na hora de imprimir. formatarExecucao() poderia refazer o trabalho: pegar o símbolo na posição da queda e perguntar a colunaDe() se ele tem coluna. A resposta seria a mesma e, de quebra, a estrutura teria um campo a menos. Mas o resultado deixaria de se bastar: quem recebesse a execução precisaria da cadeia e da máquina juntas para saber por qual das três formas a recusa aconteceu, e só a função de imprimir saberia responder. Com o campo gravado, a distinção viaja com o resultado e serve a qualquer um que o receba.
1.6.5 custo-da-matriz-densa — a conta impressa ao lado da tabela
A máquina de comentário é a mais desperdiçada das três, e o resumo que o binário imprime para ela é este:
comentario de linha — duas barras e o que vier depois
ESTADO ACEITA TRANSICOES
inicio nao / -> uma_barra
uma_barra nao / -> no_comentario
no_comentario sim /..z [28] -> no_comentario
erro nao (todas para erro)
estados (com o de erro): 4 | alfabeto: 28 | posicoes: 112 | bytes: 896 | transicoes nao-erro: 30formatarTabela() tem dois laços aninhados e um terceiro dentro do segundo, e é o terceiro que produz a linha do meio. Para cada coluna cujo destino não é o erro, ele avança enquanto a coluna seguinte levar ao mesmo lugar e fecha a faixa quando isso deixa de valer. Em no_comentario, a faixa cobre o alfabeto inteiro: 28 colunas numa entrada só. Nos dois primeiros estados a faixa tem um símbolo só, o teste de até três símbolos manda para o outro ramo, e a barra sai listada. O estado de erro não entra em ramo nenhum, e a marca primeiro continua verdadeira até o fim da linha, o que produz o (todas para erro).
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
flowchart TD
A["formatarTabela(), sobre a maquina de comentario"] --> B["preencher('ESTADO', 14) e preencher('ACEITA', 8): o cabecalho"]
B --> C{"estado < aceitacao_.size()"}
C -- "sim" --> D["preencher(nomes_[estado], 14), e sim ou nao conforme aceitacao_[estado]"]
D --> E{"coluna < alfabeto_.size()"}
E -- "sim" --> F{"destino == erro_"}
F -- "sim" --> E
F -- "nao" --> G{"tabela_[estado * alfabeto_.size() + fimDaFaixa + 1] == destino"}
G -- "sim: a coluna seguinte leva ao mesmo destino" --> G
G -- "nao: a faixa fechou" --> H{"quantidade <= 3"}
H -- "sim: so '/' sai de inicio" --> I["lista os simbolos um a um"]
H -- "nao: as 28 colunas de no_comentario" --> J["escreve /..z [28], a faixa por posicao no alfabeto declarado"]
I --> K["acrescenta ' -> ' e nomes_[destino]"]
J --> K
K --> E
E -- "nao" --> L{"primeiro"}
L -- "sim: nenhuma coluna de erro_ sai dele" --> M["escreve (todas para erro)"]
L -- "nao" --> C
M --> C
C -- "nao: as 4 linhas escritas" --> N["bytesDaTabela(): tabela_.size() * sizeof(Estado) = 896"]
N --> O["transicoesDefinidas()"]
O --> P{"destino != erro_"}
P -- "sim" --> Q["++total"]
Q --> O
P -- "nao" --> R["30 de 112 posicoes levam a destino diferente de erro_"]
Com a tabela impressa, bytesDaTabela() multiplica as 112 posições pelos 8 bytes de cada destino, e transicoesDefinidas() varre a tabela contando as que apontam para outro lugar. São 30 de 112: as outras 82, três quartos da tabela desta máquina, existem para dizer que não. Nas outras duas a fração é bem menor, 48 de 111 no identificador e 22 de 65 no número, e por isso ela sempre aparece com o nome da máquina ao lado.
%%{init: {"flowchart": {"useMaxWidth": false}, "sequence": {"useMaxWidth": false}, "class": {"useMaxWidth": false}, "state": {"useMaxWidth": false}, "er": {"useMaxWidth": false}}}%%
sequenceDiagram
autonumber
participant D as demos/03_demo.cpp
participant A as Afd
D->>A: formatarTabela()
A->>A: preencher("ESTADO", 14)
A-->>A: "ESTADO" seguido de oito espacos
A->>A: agrupa as colunas do estado inicio
A-->>A: "/ -> uma_barra", com quantidade igual a 1
A->>A: agrupa as colunas do estado no_comentario
A-->>A: "/..z [28] -> no_comentario", 28 colunas numa faixa so
A->>A: nenhuma coluna de erro_ leva a destino diferente dele
A-->>A: "(todas para erro)"
A-->>D: quatro linhas, uma por estado
D->>A: quantidadeDeEstados()
A-->>D: 4, com o estado de erro incluido
D->>A: tamanhoDoAlfabeto()
A-->>D: 28
D->>A: bytesDaTabela()
A-->>D: 896, que sao 112 posicoes a 8 bytes cada
D->>A: transicoesDefinidas()
A-->>D: 30, e as 82 restantes guardam erro_
transicoesDefinidas() percorre a tabela inteira a cada chamada. Um contador incrementado dentro de definirTransicao() responderia em tempo constante, e erraria a conta do jeito mais silencioso: contaria escritas, e nada na interface impede duas chamadas de escrever na mesma posição. Nenhuma das três máquinas daqui faz isso, e é por isso mesmo que a divergência passaria despercebida até a primeira que fizesse. A varredura conta posições, que é o que a decisão de representação precisa saber. Ela gasta uma passada pela tabela de cada máquina, uma vez na demonstração, enquanto a consulta que importa acontece uma vez por símbolo de texto.