1 Autômatos finitos determinísticos — Projeto do Professor
Este é o projeto de referência do professor — as tarefas do Projeto Integrador deste módulo resolvidas do começo ao fim, com as decisões justificadas uma a uma. É o modelo do que cada grupo deve produzir no próprio projeto, e existe para ser estudado, não copiado: a representação que você escolhe, as máquinas que projeta e a conta que registra são suas. O que se copia daqui é o nível de acabamento e o hábito de medir antes de afirmar.
1.1 Visão Geral
Entra em cena a máquina, e com ela a primeira decisão do percurso que cobra preço em memória — mensurável, não estimado. As duas tarefas deste módulo são complementares e a ordem entre elas importa: a primeira decide como a função de transição é armazenada, e a segunda executa uma máquina descrita à mão sobre uma cadeia, reportando aceitação ou recusa.
As máquinas são escritas à mão em vez de geradas, e o enunciado da segunda tarefa diz por quê: o gerador só existe no módulo seguinte, e chegar lá com o executor já verificado separa dois erros que, juntos, são difíceis de distinguir. Quando a construção de Thompson começar a produzir máquinas automaticamente e uma cadeia for recusada indevidamente, a pergunta será se a máquina está errada ou se a execução está — e ter um executor já testado contra máquinas conhecidas responde metade dela de graça.
Além das duas tarefas, o módulo tem conteúdo teórico que pede código próprio, e ele está aqui inteiro: a definição formal como quíntupla vira a estrutura da classe, a função de transição total vira o estado de erro absorvente, a configuração e o passo de computação viram o traço que a execução guarda, e o projeto de autômatos para especificações dadas vira as três máquinas construídas à mão no fim do arquivo. O tratamento da entrada inválida atravessa tudo, porque é ele que decide se o sistema recusa a cadeia ou termina de forma imprevisível.
O código compila com avisos tratados como erro e roda pelo binário deste ponto do percurso, ao lado dos três anteriores, que continuam sendo construídos e executados. Que os três continuem passando é a evidência de que a peça nova entrou sem quebrar o que já funcionava, e é a única forma de saber disso sem reler tudo.
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.
Escolhemos a matriz densa e descartamos o mapa esparso. O documento de decisão traz a conta completa, e as três razões — uma de custo por operação, uma de forma do artefato emitido, uma de decisão adiada.
docs/03_representacao_transicao.md
# A representação da função de transição — decisão e a conta
Decisão do terceiro arco da Peneira. É a primeira do percurso que cobra preço
mensurável, e por isso 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, com a coluna
obtida de um mapeamento byte → coluna calculado no construtor. Uma consulta de
transição é 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. Definir uma transição é abrir exceção a essa
regra — o contrário de exigir que quem monta a máquina preencha tudo.
## 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 deste capítulo 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 são impressos pela própria demonstração, e não copiados à mão: o
programa calcula `bytesDaTabela()` e exibe. Uma tabela nesta seção que
divergisse do que o código reporta seria pior do que não ter tabela alguma.
**A coluna não é o byte.** Indexar diretamente pelo código do caractere daria
256 colunas por estado — para o autômato de número, 256 em vez de 13, quase vinte
vezes mais memória para representar exatamente a mesma máquina. O mapeamento
byte → coluna custa um vetor de 256 entradas **por autômato**, e não por estado,
o que o torna irrelevante assim que há mais de um punhado de estados.
## A alternativa descartada
**Mapa esparso** — uma tabela de dispersão de `(estado, símbolo)` para destino,
guardando só as transições que existem.
Ela ganha em memória, e a última coluna da tabela acima diz quanto: o autômato de
comentário tem 112 posições e apenas 30 transições não-erro — três quartos da
tabela guardam o mesmo valor. O de identificador é o menos desperdiçado dos três,
com 63 de 111, e ainda assim desperdiça mais de quarenta por cento. Em máquinas
grandes, produzidas pela determinização do arco seguinte, a proporção piora.
Descartamos assim mesmo, por duas razões que a memória não cobre.
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 acesso a vetor por 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 é a mais importante: **a
tabela de transição não é apenas estrutura interna do reconhecedor**. Ela é
também a forma daquilo que o sistema emite no fim, quando o objeto produzido
precisar carregar as máquinas construídas a partir da descrição lida. Uma matriz
densa é um bloco contíguo de inteiros — grava-se e carrega-se como está. Um mapa
esparso teria de ser serializado, e a decisão sobre o formato de serialização
voltaria no arco de geração de código, quando já não há tempo de refazer.
## O que fica em aberto, e onde volta
A troca não é definitiva. Quando a determinização produzir máquinas com muitos
estados e alfabeto largo, a matriz densa passa a desperdiçar de forma visível, e
existe uma saída intermediária conhecida: **compressão por linhas equivalentes**
— estados cujas linhas de transição são idênticas compartilham a mesma linha.
Ela preserva o acesso em tempo constante e recupera boa parte da memória.
Fica registrado aqui como decisão adiada, e não como omissão. O arco da
minimização é onde a conta muda, e é lá que ela deve ser refeita — com os
números daquelas máquinas, não com os destas três.Três pontos do documento merecem comentário, e o primeiro é uma honestidade que a tarefa exige.
O mapa esparso ganha em memória, e ganha muito. A última coluna da tabela mostra o desperdício: o autômato de comentário tem 112 posições e apenas 30 transições que não vão para o erro — três quartos da tabela guardam o mesmo valor. Registrar isso é parte de escolher: uma justificativa que só enumera as vantagens da opção vencedora é propaganda. Descartamos apesar da vantagem, não por ignorá-la.
O que decidiu foi o custo por símbolo consumido, não o total de memória. O reconhecimento faz uma consulta de transição para cada símbolo do texto de entrada, e a Peneira processa texto inteiro. Trocar um acesso a vetor por um cálculo de hash multiplica o custo da operação mais frequente do sistema, e o reconhecimento deixa de ser previsivelmente linear no tamanho do texto.
A conta é impressa pelo programa, não copiada à mão. Os números da tabela do documento saem de bytesDaTabela() e transicoesDefinidas(), executados na demonstração. Uma tabela num documento de decisão que divergisse do que o código reporta seria pior do que documento nenhum, porque teria a aparência de verificada.
A conta expõe um detalhe que quase ninguém antecipa: a coluna não é o código do símbolo. Indexar a tabela diretamente pelo byte daria 256 colunas por estado — para o autômato de número, 256 em vez de treze, quase vinte vezes mais memória para representar exatamente a mesma máquina. O mapeamento de byte para coluna custa um vetor de 256 entradas por autômato, e não por estado, o que o torna irrelevante assim que há mais de um punhado de estados.
O documento fecha registrando uma decisão adiada, e essa distinção vale ser feita, porque adiar e omitir produzem o mesmo silêncio no código. A matriz densa passa a desperdiçar de forma visível quando a determinização produzir máquinas com muitos estados sobre alfabetos largos, e existe uma saída intermediária conhecida: estados cujas linhas de transição são idênticas podem compartilhar a mesma linha, o que recupera boa parte da memória sem perder o acesso em tempo constante. Não implementamos isso agora porque a conta que a justificaria é a das máquinas daquele módulo, e não a destas três — mas deixamos escrito onde ela deve ser refeita. Uma decisão registrada como adiada é revisitada; uma decisão não registrada vira, alguns módulos depois, “sempre foi assim”.
Onde é fácil errar. Escolher a representação pelo que é confortável de escrever agora, e descobrir o preço quando a determinização produzir a primeira máquina com centenas de estados. Como verificar que está correta: 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 valor. Se os dois números não baterem, a fórmula está errada — e é a fórmula que você vai usar para decidir, não a medição.
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: representação e execução.
//
// A definição formal é uma quíntupla — conjunto de estados, alfabeto, função de
// transição, estado inicial e conjunto de estados de aceitação. Esta classe é
// essa quíntupla virada estrutura de dados, e cada campo abaixo corresponde a um
// componente dela.
//
// Duas decisões de projeto atravessam o arquivo inteiro e valem ser lidas antes
// do código:
//
// 1) A função de transição é TOTAL. A definição matemática exige que exista
// destino para todo par (estado, símbolo); em código, isso vira um estado de
// erro absorvente, criado no construtor e do qual não se sai. Sem ele, a
// execução teria de perguntar "existe transição?" a cada passo, e o símbolo
// imprevisto viraria comportamento indefinido em vez de recusa.
//
// 2) A tabela é uma MATRIZ DENSA indexada por estado e por coluna de símbolo,
// e não um mapa esparso. O custo dessa escolha é medido em `bytesDaTabela`,
// e a razão está no documento de decisão deste capítulo: a Peneira consulta a
// transição uma vez por símbolo de entrada, e o acesso em tempo constante
// sem hash é o que mantém o reconhecimento linear no tamanho do texto.
//
// A coluna não é o código do símbolo: os símbolos do alfabeto são mapeados para
// colunas consecutivas. Uma tabela indexada pelo byte teria 256 colunas por
// estado para um alfabeto de dez símbolos, e é justamente essa conta que o
// documento de decisão registra.
#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 é a
// sequência de configurações, e é assim que a definição descreve o
// reconhecimento — não como "rodar o autômato", mas como percorrer configurações
// até a entrada acabar.
struct Configuracao {
Estado estado = 0;
std::size_t posicao = 0;
char simboloLido = '\0'; // o símbolo que produziu ESTA configuração
};
struct Execucao {
bool aceitou = false;
std::vector<Configuracao> passos;
// Posição do primeiro símbolo que levou ao estado de erro, quando houve.
// Vale `std::string::npos` se a cadeia foi consumida inteira.
std::size_t posicaoDaQueda = std::string::npos;
bool simboloForaDoAlfabeto = false;
};
class Afd {
public:
// Cria a máquina com `quantidadeDeEstados` estados úteis mais o estado de
// erro, que recebe o índice imediatamente seguinte. Toda transição começa
// apontando para o erro: definir uma transição é abrir uma exceção a essa
// regra, e não o contrário.
Afd(std::string alfabeto, std::size_t quantidadeDeEstados, Estado inicial);
// Automato degenerado — so o estado de erro, alfabeto vazio, recusa tudo.
// Existe para que um Afd possa ser membro de uma struct de resultado e
// atribuido depois; sem ele, quem devolve um Afd construido em duas etapas
// precisaria de ponteiro ou de optional, e os dois custam mais do que valem.
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;
// Acrescentados no arco da determinizacao: quem constroi um AFD a partir de
// outro precisa percorrer o alfabeto e saber onde a execucao comeca.
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;
// Reconhecimento: consome a cadeia inteira e diz se parou em aceitação.
bool aceita(const std::string& cadeia) const;
// O mesmo reconhecimento, guardando cada configuração pelo caminho. É o que
// permite mostrar o passo de computação em vez de afirmá-lo.
Execucao executar(const std::string& cadeia) const;
// A conta que a decisão de representação exige por escrito: quanto a tabela
// ocupa em função do número de estados e do tamanho do alfabeto.
std::size_t bytesDaTabela() const;
// Quantas posições da tabela apontam para algo que não é o erro. É a medida
// do desperdício da matriz densa, e o argumento a favor do 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`: a especialização de vetor de bool empacota bits e não
// devolve referência de verdade, o que surpreende quem lê o código adiante.
std::vector<char> aceitacao_;
std::vector<std::string> nomes_;
Estado inicial_ = 0;
Estado erro_ = 0;
// recorte:fim quintupla-como-estrutura
};
// Os três autômatos projetados à mão neste capítulo, cada um a partir de uma
// especificação em prosa. Construí-los à mão é deliberado: o gerador só existe
// no capítulo seguinte, e chegar lá com o executor já verificado separa dois
// erros que, juntos, são difíceis de distinguir.
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;
}
// Faixa de símbolos, usada só para montar os alfabetos dos exemplos.
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 transição nasce apontando para o erro. É o que torna a função total
// sem exigir que quem monta a máquina preencha a tabela inteira: ele declara
// as transições que existem, e as demais já estão corretas.
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 declarado ou estado inexistente: a transição
// simplesmente não é registrada, e o par continua indo para o erro.
// Falhar em silêncio aqui é preferível a aceitar uma tabela inconsistente.
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]; }
// 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});
// A primeira queda no erro é registrada, mas a execução CONTINUA. Parar
// aqui daria a mesma resposta e esconderia o fato de o estado de erro ser
// absorvente — que é justamente o que o traço precisa evidenciar.
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 {
// A tabela é impressa por CLASSE de coluna, e não coluna a coluna: um
// alfabeto de sessenta e três símbolos produziria sessenta e três colunas
// ilegíveis. Para cada estado, listamos os destinos distintos e quais
// símbolos levam a cada um.
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;
}
// Agrupa símbolos consecutivos que vão para o mesmo destino, para
// que uma faixa de dez dígitos apareça como faixa e não como dez
// entradas iguais.
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) {
// Poucos simbolos: liste todos. Abreviar `+ -` como faixa
// sugeriria um intervalo de codigos que nao existe.
for (std::size_t i = coluna; i <= fimDaFaixa; ++i) {
if (i > coluna) {
texto += ' ';
}
texto += alfabeto_[i];
}
} else {
// A faixa e por POSICAO no alfabeto declarado, nao por codigo do
// caractere: os simbolos entre os extremos sao os que estao entre
// eles na string do alfabeto. A contagem entre colchetes esta ai
// para que ninguem leia `a.._ [37]` 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 bastam, e é a pergunta que o
// projeto de autômato sempre faz: qual é a menor distinção que a especificação
// obriga a lembrar? Aqui, apenas "ainda não li nada" e "já li a primeira letra".
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. Quatro estados, e a distinção que obriga cada
// um deles é sempre a mesma pergunta: o que ainda falta para a cadeia ser
// válida? Repare que `q_apos_ponto` NAO 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 seguidas de qualquer coisa até o fim da linha.
// O alfabeto aqui é reduzido de propósito — barra, letras e espaço —, e a
// demonstração usa esta máquina para mostrar a diferença entre recusar por
// transição inexistente e recusar por símbolo fora do alfabeto declarado.
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 é a quíntupla da definição virada estrutura de dados, e cada componente dela está lá: os estados são os índices, o alfabeto é a cadeia declarada no construtor, a função de transição é a tabela, o estado inicial é um campo e o conjunto de aceitação é um vetor de marcas. Ler a definição formal ao lado do cabeçalho é o exercício que este módulo pede, e ele funciona porque não há nada no cabeçalho que a definição não preveja.
A decisão que resolve a segunda metade da tarefa é a função total por construção. Toda posição da tabela nasce apontando para o estado de erro, e definir uma transição é abrir exceção a essa regra. A consequência é que o símbolo imprevisto nunca chega ao código como caso especial: ele simplesmente transita para o erro, como qualquer outro. A alternativa — perguntar “existe transição?” a cada passo — coloca um teste na operação mais frequente do sistema e transfere para cada ponto de chamada a obrigação de decidir o que fazer quando a resposta é não.
O estado de erro é absorvente: dele não se sai. É a única parte da máquina que nunca muda de ideia. Isso permite uma escolha que parece contraintuitiva na execução: ao cair no erro, registramos a posição e continuamos consumindo a cadeia. A resposta final é a mesma, e o traço mostra o autômato permanecendo no erro até o fim — que é exatamente o que “absorvente” quer dizer, e o que uma parada antecipada esconderia.
O reconhecimento é implementado duas vezes. A versão simples devolve apenas a decisão e é a que o resto do sistema usará; a versão com traço guarda cada configuração pelo caminho e existe para a demonstração. A definição descreve o reconhecimento como uma sequência de configurações — o par estado corrente e posição na cadeia —, e a demonstração imprime essa sequência em vez de afirmá-la.
Repare no que a demonstração distingue, e que a maioria das implementações confunde. Há duas maneiras de uma cadeia ser recusada, e elas pedem mensagens diferentes. A cadeia 2valor é recusada porque o dígito, embora pertença ao alfabeto declarado, não tem transição a partir do estado inicial — o identificador não pode começar com número. Já //OK é recusada porque as maiúsculas nem constam do alfabeto daquela máquina. As duas param 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.
Um terceiro caso completa o quadro, e é o mais sutil: a cadeia 42. consome-se inteira sem jamais cair no erro, e mesmo assim é recusada — ela para em estado não final, porque um número não termina em ponto. Recusar sem erro é o caso que quem implementa esquece, e o que produz o defeito clássico de aceitar cadeias incompletas.
As três máquinas projetadas à mão cobrem o tópico de projeto de autômatos para especificações dadas, e cada uma responde à mesma pergunta: qual é a menor distinção que a especificação obriga a lembrar? O identificador precisa de dois estados, porque só há duas situações — ainda não li nada, já li a primeira letra. O número com sinal precisa de quatro, e o quarto existe porque “li o ponto mas ainda não li dígito nenhum depois dele” é uma situação em que a cadeia não é válida e ainda pode vir a ser.
Onde é fácil errar. Tratar o símbolo sem transição prevista com uma exceção ou um encerramento do programa. O reconhecedor será chamado adiante sobre texto arbitrário, escrito por quem usa a linguagem, e recusar é resposta — abortar não é. Como verificar que está correta: submeta à sua máquina três cadeias, uma que aceita, uma que cai no erro e uma que consome tudo e para em estado não final. Se as duas últimas produzem a mesma mensagem, falta distinção; se alguma delas derruba o programa, a função de transição não está 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. Abra o cabeçalho ao lado dessa linha: a correspondência é direta e nada no código sobra — Q são os índices até o número de estados, \Sigma é a cadeia declarada no construtor, \delta é a tabela, q_0 é o campo do estado inicial e F é o vetor de marcas de aceitação.
O ponto que a notação esconde, e que o código não pode esconder, está na seta de \delta. Ela é uma função total — para todo par de estado e símbolo existe um destino, sem exceção. Livros costumam apresentar autômatos com transições faltando e resolver a lacuna com uma frase, dizendo que o autômato “rejeita” ali. Em código essa frase não existe: ou a lacuna é preenchida, ou cada consulta precisa devolver algo que signifique “não há”. Preenchemos, e o preenchimento tem nome — o estado sumidouro, que a literatura chama estado morto e que aqui chamamos de erro.
A totalidade custa memória, e o quanto está medido: para as três máquinas deste arquivo, a maior parte da tabela guarda o mesmo destino. É o mesmo desperdício que a Tarefa 1 mediu, visto por outro ângulo — não como escolha de estrutura, mas como consequência de uma exigência da definição.
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. E a cadeia w é reconhecida quando a sequência de passos que parte de (q_0, w) chega a (q, \varepsilon) com q \in F.
Na implementação, a configuração guarda a posição em vez do sufixo — a informação é a mesma, já que o sufixo é o que vem depois da posição, e guardar índices em vez de cópias de string evita alocar uma cadeia nova por passo. O que a demonstração imprime é exatamente essa sequência, e imprimi-la muda a natureza do que se afirma: em vez de dizer que a máquina aceita valor_2, mostramos os oito estados pelos quais ela passou. Um traço que termina em estado de aceitação é uma prova; um resultado sem traço é um resultado.
1.5 Projetar a máquina a partir da especificação em prosa
O objetivo deste módulo pede projetar um autômato para uma especificação dada, e não apenas simular um autômato pronto. As três máquinas do fim do arquivo existem para isso, e cada uma foi construída respondendo à mesma pergunta: qual é a menor distinção que a especificação obriga a lembrar?
Essa pergunta é o método inteiro, e ela funciona porque um estado é uma memória, e não um lugar no desenho. O autômato não guarda o que leu; guarda apenas em qual situação isso o deixou. Projetar é descobrir quantas situações distintas a especificação exige.
No identificador, a especificação diz que a primeira posição aceita letra e as seguintes aceitam letra, dígito ou sublinhado. Há, portanto, duas situações: ainda não li nada, e já li a primeira letra. Dois estados, e nenhum a mais — não há razão para distinguir a segunda posição da quinta, porque as duas aceitam exatamente o mesmo conjunto de símbolos e ambas encerram uma cadeia válida.
O número com sinal exige quatro, e o interessante é o quarto. Após o ponto e antes de qualquer dígito, a cadeia não é válida, mas ainda pode vir a ser — e essa situação é diferente tanto de “li dígitos, posso parar” quanto de “li dígitos depois do ponto, posso parar”. Esse é o estado que quem projeta pela primeira vez esquece, e o esquecimento produz uma máquina que aceita 42., que é justamente o caso negativo que a demonstração executa. Repare que o sinal não cria estado: a transição de sinal volta ao próprio estado inicial, porque ler um sinal não muda em nada o 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, removeria automaticamente.
O comentário de linha tem alfabeto estreito, e existe menos pelo que reconhece do que pelo contraste que permite: com um alfabeto estreito, é fácil submeter uma cadeia com símbolo que nem consta dele e ver a segunda forma de recusa acontecer.
Onde é fácil errar. Criar um estado por posição da cadeia, em vez de por situação distinta. A máquina resultante funciona para os exemplos testados e cresce sem limite conforme as cadeias ficam maiores — sintoma de que o projeto está descrevendo entradas, e não a linguagem. Como verificar que está correta: para cada par de estados da sua máquina, procure uma cadeia que seja aceita a partir de um e recusada a partir do outro. Se não encontrar para algum par, os dois estados são o mesmo estado escrito duas vezes — e a minimização vai fundi-los adiante, o que confirma o diagnóstico em vez de resolvê-lo.