1 O lema do bombeamento e os limites do reconhecimento regular — 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: o padrão que excede o seu reconhecedor e o texto que explica a falha são seus, e dependem do domínio que você escolheu. O que se copia daqui é o nível de acabamento e a exigência de que o limite seja demonstrado sobre o próprio código, e não citado.
1.1 Visão Geral
Este é o único módulo do percurso que não acrescenta capacidade ao sistema. Ele acrescenta uma prova sobre o sistema, e o que se produz aqui é a explicação da falha. As duas tarefas são exatamente isso: construir o caso que quebra o reconhecedor, e sustentar por escrito que a quebra era necessária.
A ordem importa e é contraintuitiva. Primeiro roda-se o caso que falha, no artefato que já existe e que funcionou nos cinco módulos anteriores; só então se formaliza por que ele tinha de falhar. A surpresa vem antes da prova, e é ela que sustenta a atenção durante a prova.
O que torna este módulo diferente de uma aula sobre o lema é que a maquinaria construída até aqui vira ferramenta. A leitura de patterns, a construção de Thompson, a determinização e a minimização deixam de ser o assunto e passam a ser o instrumento: compilamos duas tentativas de descrever delimitadores balanceados, medimos onde cada uma erra, e depois executamos o argumento de bombeamento sobre o autômato determinístico real que o sistema produziu — encontrando o estado repetido, decompondo a cadeia e vendo a máquina aceitar o que não deveria.
Todo o conteúdo teórico do módulo é coberto: a intuição do limite aparece como a memória finita esbarrando na profundidade da entrada, o enunciado do lema tem a estrutura lógica registrada por extenso com quem escolhe o quê, o caso dos delimitadores balanceados é conduzido por inteiro, e o documento fecha com o que o resultado não autoriza a concluir — que é onde mora a maior parte dos erros de quem acabou de aprender o lema.
1.2 Tarefa 1: Construir o padrão que excede o reconhecedor
O que a tarefa pede
Escrever, na linguagem definida no projeto, um padrão que exija contagem irrestrita — delimitadores balanceados é o caso canônico, e construções aninhadas dentro de construções do mesmo tipo servem igualmente. Submetê-lo ao reconhecedor e observar o que acontece. O caso precisa ser reproduzível por outra pessoa a partir do que está escrito no repositório: um resultado que só aparece na máquina de quem o produziu não demonstra nada.
Escrevemos duas tentativas, e não uma, porque a falha tem duas direções e mostrar só uma delas deixa aberta a suspeita de que a outra funcionaria.
06_bombeamento.h
// 06_bombeamento.h — O limite do reconhecimento regular, demonstrado no artefato.
//
// Este arco não acrescenta capacidade ao sistema: acrescenta uma PROVA sobre
// ele. O que se produz aqui não é a falha — é a explicação dela, e o código
// existe para que a explicação seja executável em vez de afirmada.
//
// A peça central é a decomposição de bombeamento aplicada a um AFD REAL, o que
// a Peneira construiu. Dada uma cadeia pelo menos tão longa quanto o número de
// estados, o princípio da casa dos pombos garante que algum estado se repete no
// caminho; achar essa repetição é achar o pedaço que pode ser repetido à vontade
// sem que a máquina perceba. O código encontra esse pedaço, e a demonstração
// bombeia e mostra a máquina aceitando o que não deveria.
//
// NÃO REMOVA ESTE ARQUIVO NEM O SEU TESTE. Ele é o único do percurso que
// demonstra o sistema ERRANDO de propósito, e continua rodando a cada
// reconstrução junto com os que demonstram acerto. Se um dia ele parar de
// acusar a contradição, não será porque o sistema melhorou: será porque alguma
// peça anterior mudou de comportamento e a demonstração deixou de demonstrar.
//
// Isso é diferente de testar e ver falhar. Testar mostra que ESTA máquina falha;
// a decomposição mostra POR QUE qualquer máquina daquela classe falharia — o
// argumento não depende de qual AFD foi construído, só de ele ter um número
// finito de estados.
#ifndef PENEIRA_06_BOMBEAMENTO_H
#define PENEIRA_06_BOMBEAMENTO_H
#include <cstddef>
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// A decomposição x y z exigida pelo lema, obtida por observação direta do
// caminho percorrido no autômato.
struct Decomposicao {
bool encontrou = false;
std::string x;
std::string y; // o trecho bombeável — nunca vazio, e é isso que dá a prova
std::string z;
Estado estadoRepetido = 0;
std::size_t primeiraVisita = 0;
std::size_t segundaVisita = 0;
std::size_t comprimentoDeBombeamento = 0;
};
// Percorre a cadeia no autômato registrando o estado a cada posição e devolve a
// primeira repetição encontrada. É a casa dos pombos aplicada: se a cadeia tem
// comprimento maior ou igual ao número de estados, a repetição existe — não é
// possível visitar n+1 posições em n estados sem repetir.
Decomposicao decompor(const Afd& afd, const std::string& cadeia);
// A cadeia com o trecho bombeável repetido `vezes` vezes. `vezes == 0` remove o
// trecho, o que também é bombeamento e às vezes é o caso mais revelador.
std::string bombear(const Decomposicao& decomposicao, std::size_t vezes);
// O reconhecedor CORRETO de delimitadores balanceados, para contraste. Um
// contador, e não um autômato — e é exatamente esse contador que a classe
// regular não tem como manter, porque ele precisa crescer sem limite.
bool balanceada(const std::string& cadeia);
// A profundidade máxima de aninhamento de uma cadeia, usada no relatório para
// mostrar qual profundidade cada tentativa regular alcança antes de falhar.
std::size_t profundidade(const std::string& cadeia);
// Gera a cadeia com `n` aberturas seguidas de `n` fechamentos.
std::string balanceadaComProfundidade(std::size_t n);
// A tentativa regular que enumera profundidades até `maxima`: um pattern que
// aceita exatamente as cadeias balanceadas de aninhamento simples até aquele
// limite. Cada profundidade a mais custa um ramo de alternância — e nenhum
// pattern finito cobre todas.
std::string patternPorEnumeracao(std::size_t maxima);
} // namespace peneira
#endif // PENEIRA_06_BOMBEAMENTO_H06_bombeamento.cpp
#include "06_bombeamento.h"
#include <algorithm>
namespace peneira {
Decomposicao decompor(const Afd& afd, const std::string& cadeia) {
Decomposicao decomposicao;
decomposicao.comprimentoDeBombeamento = afd.quantidadeDeEstados();
// recorte:inicio caminho-de-estados-por-prefixo
// O caminho: estado após cada prefixo, incluindo o prefixo vazio. São
// cadeia.size() + 1 posições visitadas.
std::vector<Estado> caminho;
Estado atual = afd.estadoInicial();
caminho.push_back(atual);
for (const char simbolo : cadeia) {
atual = afd.transicao(atual, simbolo);
caminho.push_back(atual);
}
// recorte:fim caminho-de-estados-por-prefixo
// recorte:inicio repeticao-dentro-do-prefixo
// Procura a primeira repetição de estado. Restringimos a busca ao prefixo de
// comprimento igual ao número de estados, porque é isso que o lema garante:
// a repetição acontece DENTRO dos primeiros p símbolos, e é por isso que o
// lema pode exigir que `xy` seja curto. Uma repetição encontrada mais
// adiante também serviria para bombear, mas provaria uma afirmação mais
// fraca do que a do enunciado.
const std::size_t limite =
std::min(caminho.size(), decomposicao.comprimentoDeBombeamento + 1);
// recorte:fim repeticao-dentro-do-prefixo
for (std::size_t i = 0; i < limite; ++i) {
for (std::size_t j = i + 1; j < limite; ++j) {
if (caminho[i] != caminho[j]) {
continue;
}
// recorte:inicio decompor-em-xyz
decomposicao.encontrou = true;
decomposicao.estadoRepetido = caminho[i];
decomposicao.primeiraVisita = i;
decomposicao.segundaVisita = j;
decomposicao.x = cadeia.substr(0, i);
decomposicao.y = cadeia.substr(i, j - i);
decomposicao.z = cadeia.substr(j);
// recorte:fim decompor-em-xyz
return decomposicao;
}
}
return decomposicao;
}
// recorte:inicio bombear-o-miolo
std::string bombear(const Decomposicao& decomposicao, const std::size_t vezes) {
std::string resultado = decomposicao.x;
for (std::size_t i = 0; i < vezes; ++i) {
resultado += decomposicao.y;
}
resultado += decomposicao.z;
return resultado;
}
// recorte:fim bombear-o-miolo
// recorte:inicio contador-sem-limite-superior
bool balanceada(const std::string& cadeia) {
// Um contador, e é aqui que mora toda a diferença. O contador não tem limite
// superior declarado: ele cresce com a profundidade da entrada. Um autômato
// finito precisaria de um estado por valor possível do contador, e como não
// há limite, não há número finito de estados que sirva.
long long abertos = 0;
for (const char simbolo : cadeia) {
if (simbolo == '(') {
++abertos;
} else if (simbolo == ')') {
--abertos;
if (abertos < 0) {
return false; // fechou o que nunca foi aberto
}
}
}
return abertos == 0;
}
// recorte:fim contador-sem-limite-superior
std::size_t profundidade(const std::string& cadeia) {
long long atual = 0;
long long maxima = 0;
for (const char simbolo : cadeia) {
if (simbolo == '(') {
++atual;
if (atual > maxima) {
maxima = atual;
}
} else if (simbolo == ')') {
--atual;
}
}
return static_cast<std::size_t>(maxima < 0 ? 0 : maxima);
}
std::string balanceadaComProfundidade(const std::size_t n) {
std::string cadeia;
for (std::size_t i = 0; i < n; ++i) {
cadeia += '(';
}
for (std::size_t i = 0; i < n; ++i) {
cadeia += ')';
}
return cadeia;
}
std::string patternPorEnumeracao(const std::size_t maxima) {
// Um ramo de alternância por profundidade: \(\) | \(\(\)\) | ...
// O parêntese precisa de escape porque na nossa notação ele agrupa.
std::string expressao;
for (std::size_t n = 1; n <= maxima; ++n) {
if (!expressao.empty()) {
expressao += '|';
}
for (std::size_t i = 0; i < n; ++i) {
expressao += "\\(";
}
for (std::size_t i = 0; i < n; ++i) {
expressao += "\\)";
}
}
return expressao;
}
} // namespace peneiraA primeira tentativa é a larga: aberturas seguidas de fechamentos, sem casar as quantidades. O autômato mínimo tem três estados, aceita todas as cadeias balanceadas que testamos — e aceita também três aberturas sozinhas, quatro fechamentos sozinhos e um par desemparelhado. É um reconhecedor que nunca recusa um caso legítimo e recusa quase nada, o que o torna inútil de um jeito específico: ele erra por excesso.
A segunda é a por enumeração: um ramo de alternância por profundidade, listando os casos um a um até um limite. Oito estados, correta até a profundidade listada, e recusa a primeira cadeia acima dela. Ela erra por falta. Acrescentar mais um ramo empurra o limite em um, e não o remove — cada profundidade a mais custa estados, e a profundidade não tem teto.
A tarefa exige reprodutibilidade, e é por isso que nada aqui é digitado por fora. Os patterns são gerados por função, o reconhecedor de referência é um contador escrito ao lado, e a comparação entre o que o pattern aceita e o que de fato é balanceado é feita e marcada pelo próprio programa — as linhas que discordam saem com a marca de erro. Quem clonar o repositório e rodar o subcomando vê exatamente a mesma saída.
Repare no reconhecedor correto que serve de contraste: um contador. Ele cabe em dez linhas e não é um autômato — a variável que ele mantém não tem limite superior declarado, cresce com a profundidade da entrada, e é exatamente isso que a classe regular não tem como fazer. Tê-lo ao lado no mesmo arquivo é o que impede a conclusão errada de que a linguagem é difícil: ela é reconhecida pela coisa mais barata que existe.
Onde é fácil errar. Escolher um caso que a máquina finita também não reconhece, mas por outra razão — comprimento máximo, por exemplo. O caso precisa exigir contagem irrestrita, e não apenas ser longo. Como verificar que está correta: pergunte se existe um número que, se você o soubesse de antemão, tornaria o caso reconhecível por um autômato. Se existe, o caso é o errado — é a profundidade ilimitada que quebra a classe, não o tamanho.
1.3 Tarefa 2: Explicar por que a falha é necessária
O que a tarefa pede
Escrever um texto curto que acompanhe o caso e sustente a afirmação difícil: a falha observada não é defeito da implementação, e nenhuma correção dentro daquela classe de máquinas a resolveria. É o argumento que separa uma limitação teórica de um erro de programação, e a diferença entre os dois não é visível na tela — os dois se manifestam como uma entrada que deveria ser aceita e não é.
docs/06_limite_regular.md
# Por que a falha é necessária
Texto que acompanha o caso de delimitadores balanceados. A afirmação a sustentar
é desconfortável: **a falha observada não é defeito desta implementação, e
nenhuma correção dentro da classe das máquinas finitas a resolveria.**
A diferença entre uma limitação teórica e um erro de programação não é visível na
tela — os dois se manifestam do mesmo jeito, como uma entrada que deveria ser
aceita e não é. O que separa os dois é o argumento, e ele é este.
## O que o caso mostra, e o que ele ainda não prova
A demonstração exibe duas tentativas de descrever delimitadores balanceados com
um pattern, e ambas falham, de maneiras opostas.
A tentativa **larga** — aberturas seguidas de fechamentos, sem casar quantidades —
aceita tudo o que é balanceado e aceita também o que não é: `(((` seguido de um
único `)` passa. É um reconhecedor que nunca recusa um caso legítimo e recusa
pouquíssimo, o que o torna inútil.
A tentativa **por enumeração** — listar as profundidades uma a uma — é correta
até o limite listado e recusa o primeiro caso acima dele. Acrescentar mais um
ramo empurra o limite em um, e não o remove. A cada profundidade a mais, o
autômato ganha estados; e a profundidade não tem limite.
Nenhuma das duas prova coisa alguma sozinha. Elas mostram que **estas** duas
tentativas falharam, e alguém poderia razoavelmente supor que uma terceira, mais
esperta, funcionaria.
## O argumento que fecha a questão
Suponha, para efeito de refutação, que exista um autômato finito determinístico
`M` que aceite exatamente as cadeias de delimitadores balanceados. Seja `p` o
número de estados de `M`.
Tome a cadeia `s` com `p` aberturas seguidas de `p` fechamentos. Ela é
balanceada, logo `M` a aceita.
Ao consumir os primeiros `p` símbolos, `M` visita `p + 1` posições do caminho —
a inicial mais uma por símbolo. Como `M` tem apenas `p` estados, **duas dessas
posições estão no mesmo estado**. Isso não é hipótese: é o princípio da casa dos
pombos, e não há autômato finito que escape dele.
Chame de `x` o trecho antes da primeira dessas posições, de `y` o trecho entre as
duas e de `z` o resto. Por construção, `y` não é vazio e é feito só de aberturas,
porque as duas posições estão dentro dos primeiros `p` símbolos.
Agora o passo que decide tudo: **`M` não distingue `xz`, `xyz`, `xyyz`, e assim
por diante**. Depois de `x`, ele está num estado; consumir `y` o devolve ao mesmo
estado; consumir `y` de novo, idem. O que `M` faz com `z` a partir dali é
idêntico nos três casos. Como `M` aceita `xyz`, ele aceita `xyyz`.
Mas `xyyz` tem mais aberturas do que fechamentos — não é balanceada. Então `M`
aceita uma cadeia que não pertence à linguagem, contradizendo a suposição de que
`M` a reconhece exatamente.
Logo não existe tal `M`. A falha não é desta implementação; é da classe.
## O que o resultado autoriza e o que não autoriza
**Autoriza** concluir que nenhum autômato finito, nenhuma expressão regular e
nenhum reconhecedor construído pela maquinaria dos arcos anteriores reconhece
delimitadores balanceados. É o que motiva a subida à classe seguinte, e a subida
passa a ser consequência provada em vez de escolha de organização do assunto.
**Não autoriza** três conclusões que costumam ser tiradas dele.
Primeira: não autoriza dizer que a linguagem é "difícil" ou "cara". Ela é
reconhecida por um **contador**, que é a coisa mais barata que existe — o que
falta ao autômato finito não é potência, é memória sem limite declarado.
Segunda: não autoriza aplicar o argumento ao contrário. O lema é uma condição
**necessária** para ser regular, não suficiente: encontrar uma decomposição que
bombeia bem **não** prova que a linguagem é regular. Existem linguagens não
regulares que satisfazem a propriedade de bombeamento, e usar o lema como
certificado de regularidade é o erro mais comum de quem acabou de aprendê-lo.
Terceira: não autoriza tratar o limite como limite prático. Na prática, quase
todo texto tem profundidade pequena, e um reconhecedor por enumeração até
profundidade vinte serviria à maioria dos usos reais. O que o argumento diz é que
ele nunca estaria **correto** — e a diferença entre "funciona nos casos que vejo"
e "está correto" é justamente o que muda quando o caso não visto aparece.
## Quem escolhe o quê
O enunciado do lema tem uma alternância de quantificadores, e a ordem dela é o
que se erra ao reproduzi-lo de memória. Vale registrar quem escolhe o quê:
- O **adversário** escolhe `p`, e não podemos supor nada sobre o valor.
- **Nós** escolhemos a cadeia `s`, e escolhemos bem: `p` aberturas e `p`
fechamentos, longa o bastante e com a propriedade que queremos quebrar.
- O **adversário** escolhe a decomposição `x`, `y`, `z`, respeitando `y` não
vazio e `xy` curto. Não podemos escolher a decomposição conveniente.
- **Nós** escolhemos quantas vezes bombear, e uma vez a mais já basta.
Escolher a cadeia é onde o argumento se ganha ou se perde. Uma cadeia mal
escolhida — todas as aberturas, por exemplo — bomba sem contradição, e o
argumento não conclui nada. A escolha só é boa se **toda** decomposição possível
que o adversário fizer levar à contradição, e é por isso que `p` aberturas
seguidas de `p` fechamentos funciona: a restrição de que `xy` é curto obriga `y`
a cair inteiramente dentro das aberturas.O texto sozinho não bastaria, e a decisão de projeto deste módulo é essa: o argumento é executado, e não apenas escrito. O subcomando toma o autômato determinístico da tentativa larga, lê dele o número de estados, constrói a cadeia com aquele número de aberturas e fechamentos, percorre o caminho registrando o estado em cada posição, e encontra a repetição que o princípio da casa dos pombos garante existir.
A saída mostra o estado zero visitado nas posições zero e um, o que dá a decomposição com o trecho bombeável sendo uma única abertura. Repetir esse trecho duas e três vezes produz cadeias que o autômato aceita e que não são balanceadas; removê-lo produz outra. Três contradições numa execução.
Uma restrição da busca merece explicação, porque ela distingue provar o enunciado do lema de provar algo mais fraco. Procuramos a repetição apenas dentro dos primeiros símbolos, até o número de estados — e não em qualquer ponto da cadeia. Uma repetição encontrada mais adiante também permitiria bombear, mas o enunciado do lema exige que o prefixo mais o trecho bombeável sejam curtos, e é essa exigência que força o trecho a cair inteiramente dentro das aberturas. Sem ela, o adversário poderia escolher um trecho que contém aberturas e fechamentos em igual número, e bombeá-lo preservaria o balanceamento — o argumento não concluiria nada.
O que separa esta demonstração de “testei e falhou” é que nada no argumento depende de qual autômato foi construído. Usamos exatamente uma propriedade dele: ter um número finito de estados. Trocar a tentativa larga por qualquer outra, mais esperta, muda o número e não muda a conclusão — e é por isso que o resultado vale para a classe inteira, e não para este código.
O documento fecha com a parte que costuma ser omitida e que é onde moram os erros: o que o resultado não autoriza. Não autoriza chamar a linguagem de difícil, porque um contador a reconhece. Não autoriza usar o lema ao contrário — encontrar uma decomposição que bombeia bem não prova regularidade, e usá-lo como certificado é o erro mais frequente de quem acabou de aprendê-lo. E não autoriza tratar o limite como limite prático: um reconhecedor por enumeração até profundidade vinte serviria à maioria dos usos reais, e ainda assim nunca estaria correto. A diferença entre “funciona nos casos que vejo” e “está correto” é justamente o que muda no dia em que o caso não visto aparece.
Onde é fácil errar. Escolher mal a cadeia. Ela é a única coisa que nós escolhemos no argumento — o adversário escolhe o número de estados e escolhe a decomposição —, e uma escolha ruim faz o argumento não concluir. Só aberturas, por exemplo, bomba sem contradição alguma. Como verificar que está correta: confira que toda decomposição possível, e não apenas a que o seu código encontrou, leva à contradição. Se existir uma que bomba sem quebrar nada, a cadeia escolhida não serve, e o argumento precisa de outra.
1.4 A intuição, o enunciado e os erros que a ordem dos quantificadores provoca
A intuição do limite cabe em uma frase, e a demonstração deste módulo é essa frase virada código: uma máquina com memória finita, lendo uma cadeia suficientemente longa, é obrigada a repetir um estado — e a partir do momento em que repete, ela perdeu a capacidade de distinguir o que aconteceu entre as duas visitas.
O “suficientemente longa” é preciso, e é o número de estados. Um autômato de três estados que consome seis símbolos visita sete posições no caminho: a inicial e uma por símbolo. Sete posições em três estados não cabem sem repetição, e é isso que a execução mostra — a busca encontra a primeira repetição já entre as posições zero e um. Nada de probabilístico, nada de “tende a repetir”: é aritmética.
O que a repetição custa é a memória do trecho consumido entre as duas visitas. Depois de voltar ao mesmo estado, a máquina não tem como saber se aquele trecho ocorreu uma vez, nenhuma ou dez — o comportamento dela dali em diante é idêntico nos três casos. Se a linguagem exige essa distinção, e a linguagem dos balanceados exige (uma abertura a mais muda tudo), então a máquina não a reconhece.
O enunciado do lema é a formalização disso, e a ordem dos quantificadores é o que se erra ao reproduzi-lo de memória. Vale ler a estrutura como um jogo com dois lados, porque é assim que ela funciona: o adversário escolhe o comprimento de bombeamento, sem que possamos supor nada sobre o valor; nós escolhemos a cadeia, e escolhemos bem; o adversário escolhe a decomposição, respeitando as duas restrições; e nós escolhemos quantas vezes bombear. Quem escolhe por último, ganha — e nós escolhemos por último.
Isso torna o lema um argumento de refutação, e não um teste. Ele não serve para mostrar que uma linguagem é regular; serve para supor que é e derivar contradição. A forma lógica é a de uma negação: se fosse regular, existiria o autômato; existindo o autômato, a repetição é forçada; forçada a repetição, o bombeamento produz cadeia aceita fora da linguagem; logo não existe o autômato.
Daí decorrem os dois erros de aplicação que valem ser nomeados, porque a demonstração deste módulo protege contra um e não contra o outro.
O primeiro é escolher mal a cadeia. Ela é a única peça que escolhemos antes do adversário, e uma escolha ruim entrega o argumento. Tome, no caso dos balanceados, a cadeia formada só por aberturas: ela não é balanceada, então nem entra no argumento. Tome uma alternância de pares — abre, fecha, abre, fecha —, e o adversário pode escolher um trecho bombeável com uma abertura e um fechamento, cujo bombeamento preserva o balanceamento. Nenhuma contradição, argumento perdido. O que faz a cadeia com todas as aberturas primeiro funcionar é a restrição de comprimento sobre o prefixo mais o trecho: ela obriga o trecho a cair inteiramente dentro das aberturas, e qualquer decomposição que o adversário escolha desequilibra.
O segundo erro é usar o lema ao contrário, e é o mais comum entre quem acabou de aprendê-lo. Encontrar uma decomposição que bomba bem não prova que a linguagem é regular. O lema é condição necessária, não suficiente — e a diferença tem consequência: existem linguagens comprovadamente não regulares que satisfazem a propriedade de bombeamento, e a mais conhecida delas é a que aceita cadeias de três símbolos em que ou o primeiro bloco é vazio, ou os dois últimos blocos têm o mesmo tamanho. Toda cadeia dela admite decomposição que bomba, e ainda assim nenhum autômato finito a reconhece. Quem usa o lema como certificado de regularidade conclui o oposto do verdadeiro, e conclui com confiança.
Registrar os dois erros no diário da construção vale mais do que parece: o primeiro custa uma tarde de argumento que não fecha, e o segundo custa uma afirmação errada num relatório que ninguém revisa.
1.5 O limite como consequência, e a subida que ele obriga
Esta prova compra alguma coisa para o resto do percurso, e o que ela compra é uma mudança de estatuto no que vem depois.
Sem o limite provado, a subida à classe seguinte seria uma escolha de organização do assunto: primeiro autômatos finitos, depois gramáticas livres de contexto, porque é assim que os livros ordenam. Com o limite provado sobre o próprio código, ela vira consequência necessária. Vamos construir um analisador com pilha porque foi demonstrado que nenhuma quantidade de trabalho dentro da classe anterior resolve o problema que temos.
E o problema que temos é concreto. A gramática da Peneira, fixada no primeiro módulo, tem expressões com parênteses aninhados sem limite de profundidade — o requisito de aninhamento que o projeto exige desde o começo. Reconhecer a linguagem de patterns já era regular; reconhecer a linguagem hospedeira não é, e a demonstração deste módulo é a prova de que o reconhecedor de símbolos, sozinho, jamais dará conta dela.
Há uma consequência prática que o percurso vai explorar e que convém antecipar: o reconhecedor regular não é descartado. Ele continua sendo a peça que identifica os símbolos individuais, e o analisador com pilha o consome. As duas classes convivem no mesmo sistema, em alturas diferentes, e cada uma faz o que a outra não faz — a finita, rapidamente e sem memória; a de pilha, com memória e mais devagar. O limite provado aqui diz onde a maquinaria dos cinco módulos anteriores para, e é saber onde ela para que permite usá-la sem medo em tudo o que vem antes desse ponto.
Há ainda um efeito colateral do módulo que só se colhe adiante, e vale nomeá-lo. A partir daqui existe, no repositório, um caso documentado em que o sistema erra de propósito — e ele é o único do percurso com essa propriedade. Todos os demais casos guardados afirmam que alguma coisa funciona; este afirma que alguma coisa não pode funcionar, e continuará rodando junto com os outros a cada reconstrução. Se um dia ele parar de acusar a contradição, será porque alguma peça anterior mudou de comportamento e a demonstração deixou de demonstrar. Um caso que falha por design é o tipo de coisa que se apaga por engano numa limpeza de repositório, e o comentário no topo do arquivo existe para impedir isso.
Vale dizer, por fim, o que este módulo entrega ao estudante que o percorre com o próprio projeto. Ele entrega a experiência de ver o próprio código recusar uma entrada correta e saber, com argumento e não com suspeita, que a culpa não é dele. Essa distinção — entre o defeito que se conserta e o limite que se contorna mudando de classe — é a que separa quem depura de quem reescreve, e ela não se aprende lendo o enunciado do lema. Aprende-se tendo construído a máquina que falha.