1 Módulo 06: Projeto do Professor — Onde a Ferramenta Para
Este é o projeto de referência resolvido pelo professor: a mesma atividade que cada grupo vai executar neste módulo, feita por inteiro, com as decisões justificadas uma a uma. A construção não regular da sua linguagem será outra, mas a forma de demonstrar e de confrontar é a mesma.
1.1 Visão Geral do Módulo 06
Cinco módulos construindo um motor de reconhecimento de padrões, e este serve para descobrir o que ele não consegue fazer. Não é um módulo de recuo: é o que justifica tudo que vem depois. Sem a impossibilidade demonstrada aqui, o autômato de pilha do módulo 9 e o analisador sintático do módulo 10 seriam técnicas alternativas em vez de necessidades.
A atividade pede três coisas encadeadas. Uma demonstração formal de que alguma construção da própria linguagem não é regular. Um experimento com a ferramenta do módulo 5, documentando exatamente como ela falha. E a articulação entre as duas — que é o que se avalia, porque o experimento sozinho é anedota e a prova sozinha é abstração.
A construção que escolhi é a que o contrato de capacidades exige de toda linguagem do projeto: o aninhamento de profundidade arbitrária. Na Peneira, ela aparece nas condições compostas do where, em que uma comparação pode conter outra entre parênteses sem limite de profundidade. Reduzida ao essencial, é a linguagem dos parênteses balanceados.
Além da atividade, o módulo tem um tópico teórico que admite implementação e que resolvi tratar como código de primeira classe: as propriedades de fechamento. Elas não são curiosidade — são ferramenta de prova, e implementá-las dá ao projeto a capacidade de decidir inclusão e equivalência entre linguagens, coisa que nenhum módulo anterior conseguia.
1.2 Tarefa 1: As propriedades de fechamento
O tópico — a classe das linguagens regulares é fechada sob união, interseção, complemento e diferença, e cada afirmação vem com a construção que a demonstra.
Implementei as quatro. A razão de fazê-lo antes do lema do bombeamento, e não depois, é que elas são instrumento de demonstração: mostrar que uma linguagem não é regular passa, com frequência, por combiná-la com uma regular conhecida e chegar a um absurdo.
06_fechamento.h
#ifndef PENEIRA_06_FECHAMENTO_H
#define PENEIRA_06_FECHAMENTO_H
#include <string>
#include <vector>
#include "03_afd.h"
namespace peneira {
// Propriedades de fechamento da classe das linguagens regulares, na forma das
// construções que as demonstram.
//
// Não são curiosidade teórica: são ferramenta de prova. Demonstrar que uma
// linguagem não é regular passa, com frequência, por combiná-la com uma
// regular conhecida — se a combinação resultasse regular e sabemos que não é,
// a hipótese cai. É por isso que estas construções aparecem antes do lema do
// bombeamento, e não depois.
//
// Todas recebem o alfabeto explicitamente. Complemento e união dependem de
// função de transição TOTAL, e totalizar exige saber sobre quais símbolos.
// Deixar o alfabeto implícito aqui produziria resultados errados de um jeito
// difícil de notar: o complemento sairia certo para os símbolos que o autômato
// já usava e errado para os demais.
// Torna a função de transição total, acrescentando um estado de erro
// absorvente quando necessário.
Afd completar(const Afd& a, const std::vector<Simbolo>& alfabeto,
std::string nome);
// Complemento: mesma estrutura, finalidade invertida. Só funciona sobre
// autômato completo — sem o estado de erro explícito, as cadeias que caíam
// fora do autômato continuariam caindo fora em vez de passarem a ser aceitas.
Afd complementar(const Afd& a, const std::vector<Simbolo>& alfabeto,
std::string nome);
// Interseção pela construção do produto: os estados do resultado são pares de
// estados dos dois autômatos, e a cadeia é aceita quando os dois aceitam.
Afd interseccao(const Afd& a, const Afd& b,
const std::vector<Simbolo>& alfabeto, std::string nome);
// União, também pelo produto: mesma construção, aceita quando qualquer um dos
// dois aceita.
Afd uniaoAfd(const Afd& a, const Afd& b, const std::vector<Simbolo>& alfabeto,
std::string nome);
// Diferença: interseção com o complemento do segundo.
Afd diferencaAfd(const Afd& a, const Afd& b,
const std::vector<Simbolo>& alfabeto, std::string nome);
// Alfabeto formado pela união dos símbolos usados pelos dois autômatos.
std::vector<Simbolo> alfabetoComum(const Afd& a, const Afd& b);
// A linguagem reconhecida é vazia? Verdadeiro quando nenhum estado final é
// alcançável. Combinado com a diferença, decide inclusão de linguagens; com a
// diferença simétrica, decide equivalência.
bool linguagemVazia(const Afd& a);
} // namespace peneira
#endif // PENEIRA_06_FECHAMENTO_H06_fechamento.cpp
#include "06_fechamento.h"
#include <map>
#include <set>
#include <utility>
#include <vector>
namespace peneira {
namespace {
using ParDeEstados = std::pair<Estado, Estado>;
// Produto de dois autômatos. O predicado decide, a partir da finalidade de
// cada lado, se o estado do produto é final — é o único ponto em que interseção
// e união diferem, e por isso a construção é escrita uma vez só.
Afd produto(const Afd& a, const Afd& b, const std::vector<Simbolo>& alfabeto,
std::string nome, bool exigirAmbos) {
const Afd ca = completar(a, alfabeto, a.nome());
const Afd cb = completar(b, alfabeto, b.nome());
Afd resultado(std::move(nome));
if (ca.inicial() == kSemEstado || cb.inicial() == kSemEstado) {
return resultado;
}
std::map<ParDeEstados, Estado> conhecidos;
std::vector<ParDeEstados> fila;
const ParDeEstados inicio{ca.inicial(), cb.inicial()};
const bool inicioFinal =
exigirAmbos ? (ca.ehFinal(inicio.first) && cb.ehFinal(inicio.second))
: (ca.ehFinal(inicio.first) || cb.ehFinal(inicio.second));
conhecidos[inicio] = resultado.novoEstado(inicioFinal);
resultado.definirInicial(conhecidos[inicio]);
fila.push_back(inicio);
// Só os pares alcançáveis são criados. O produto completo teria o produto
// dos tamanhos; na prática a parte alcançável costuma ser bem menor.
for (std::size_t i = 0; i < fila.size(); ++i) {
const ParDeEstados atual = fila[i];
const Estado origem = conhecidos[atual];
for (const Simbolo s : alfabeto) {
const Estado da = ca.transicao(atual.first, s);
const Estado db = cb.transicao(atual.second, s);
if (da == kSemEstado || db == kSemEstado) {
continue;
}
const ParDeEstados destino{da, db};
const auto it = conhecidos.find(destino);
Estado indice;
if (it == conhecidos.end()) {
const bool final =
exigirAmbos ? (ca.ehFinal(da) && cb.ehFinal(db))
: (ca.ehFinal(da) || cb.ehFinal(db));
indice = resultado.novoEstado(final);
conhecidos[destino] = indice;
fila.push_back(destino);
} else {
indice = it->second;
}
resultado.adicionarTransicao(origem, s, indice);
}
}
return resultado;
}
} // namespace
Afd completar(const Afd& a, const std::vector<Simbolo>& alfabeto,
std::string nome) {
Afd resultado(std::move(nome));
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
resultado.novoEstado(a.ehFinal(e));
}
const Estado erro = resultado.novoEstado(false);
if (a.inicial() != kSemEstado) {
resultado.definirInicial(a.inicial());
} else {
resultado.definirInicial(erro);
}
for (std::size_t e = 0; e < a.quantidadeDeEstados(); ++e) {
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(e, s);
resultado.adicionarTransicao(e, s,
destino == kSemEstado ? erro : destino);
}
}
for (const Simbolo s : alfabeto) {
resultado.adicionarTransicao(erro, s, erro);
}
return resultado;
}
Afd complementar(const Afd& a, const std::vector<Simbolo>& alfabeto,
std::string nome) {
const Afd completo = completar(a, alfabeto, a.nome());
Afd resultado(std::move(nome));
for (std::size_t e = 0; e < completo.quantidadeDeEstados(); ++e) {
// A inversão acontece aqui, e só faz sentido porque o autômato está
// completo: o estado de erro, que era não final, passa a ser final, e
// é ele que aceita as cadeias que o original rejeitava por falta de
// transição.
resultado.novoEstado(!completo.ehFinal(e));
}
resultado.definirInicial(completo.inicial());
for (std::size_t e = 0; e < completo.quantidadeDeEstados(); ++e) {
for (const Simbolo s : alfabeto) {
const Estado destino = completo.transicao(e, s);
if (destino != kSemEstado) {
resultado.adicionarTransicao(e, s, destino);
}
}
}
return resultado;
}
Afd interseccao(const Afd& a, const Afd& b,
const std::vector<Simbolo>& alfabeto, std::string nome) {
return produto(a, b, alfabeto, std::move(nome), true);
}
Afd uniaoAfd(const Afd& a, const Afd& b, const std::vector<Simbolo>& alfabeto,
std::string nome) {
return produto(a, b, alfabeto, std::move(nome), false);
}
Afd diferencaAfd(const Afd& a, const Afd& b,
const std::vector<Simbolo>& alfabeto, std::string nome) {
const Afd naoB = complementar(b, alfabeto, "complemento");
return interseccao(a, naoB, alfabeto, std::move(nome));
}
std::vector<Simbolo> alfabetoComum(const Afd& a, const Afd& b) {
std::set<Simbolo> juntos;
for (const Simbolo s : a.simbolosUsados()) juntos.insert(s);
for (const Simbolo s : b.simbolosUsados()) juntos.insert(s);
return std::vector<Simbolo>(juntos.begin(), juntos.end());
}
bool linguagemVazia(const Afd& a) {
if (a.inicial() == kSemEstado) {
return true;
}
const std::vector<Simbolo> alfabeto = a.simbolosUsados();
std::set<Estado> vistos{a.inicial()};
std::vector<Estado> pilha{a.inicial()};
while (!pilha.empty()) {
const Estado atual = pilha.back();
pilha.pop_back();
if (a.ehFinal(atual)) {
return false;
}
for (const Simbolo s : alfabeto) {
const Estado destino = a.transicao(atual, s);
if (destino != kSemEstado && vistos.insert(destino).second) {
pilha.push_back(destino);
}
}
}
return true;
}
} // namespace peneiraTrês decisões de projeto sustentam essas construções.
O alfabeto é parâmetro explícito, não inferido. Esta foi a decisão mais importante e a menos óbvia. Complemento e união dependem de função de transição total, e totalizar exige saber sobre quais símbolos. Se eu deixasse o alfabeto implícito, tomando os símbolos que o autômato já usa, o complemento sairia certo para esses símbolos e errado para todos os outros — a cadeia xyz sobre um autômato que só conhece a e b deveria ser aceita pelo complemento e não seria. Erro silencioso, do tipo que passa em qualquer teste que use apenas o alfabeto original.
A união e a interseção são o mesmo código. As duas são a construção do produto, e diferem em uma linha: o estado do produto é final quando os dois lados são finais, ou quando qualquer um é. Escrevi a construção uma vez, com um parâmetro decidindo o predicado. Duplicar seria convidar as duas versões a divergirem na primeira manutenção.
Só os pares alcançáveis são criados. O produto completo teria o produto dos tamanhos — quatro estados de um lado e cinco do outro dariam vinte. Construindo por percurso a partir do par inicial, só nascem os pares que o autômato realmente atinge. Nos exemplos deste módulo, a interseção de um autômato de três estados com um de dois resulta em três, não em seis.
A demonstração confere as quatro construções contra as definições, cadeia por cadeia:
cadeia L1 L2 L1 e L2 L1 ou L2 nao L1 L2-L1
ab sim sim sim sim nao nao
a nao sim nao sim sim sim
b nao nao nao nao sim nao
<vazia> nao nao nao nao sim nao
as construcoes conferem com as definicoes? simRepare que a verificação não olha o resultado esperado escrito à mão: ela calcula o que a definição de cada operação exige a partir dos dois autômatos originais e compara. Uma tabela de valores esperados escrita por mim teria os mesmos erros que a implementação, se eu tivesse entendido a operação errado.
O que isso destrava. Combinando diferença com o teste de linguagem vazia, o projeto passa a decidir inclusão: a linguagem de A está contida na de B exatamente quando a diferença é vazia. E combinando as duas diferenças, decide equivalência. A demonstração fecha com o caso mais simples — a interseção de uma linguagem com o próprio complemento é vazia, e tem de ser.
1.2.1 Fechamento como ferramenta de prova
O uso que justifica implementar tudo isso não é construir linguagens novas — é demonstrar que uma linguagem não é regular sem precisar bombear. O raciocínio tem uma elegância que vale mostrar, e é o motivo de o módulo tratar fechamento antes do lema.
Suponha que eu queira provar que a linguagem das cadeias com igual número de a e de b não é regular. Bombear diretamente sobre ela dá trabalho, porque o adversário tem muitas decomposições à disposição. O atalho é intersectá-la com a*b*, que é regular e cujo autômato é trivial. O resultado da interseção é exatamente a linguagem das cadeias com n letras a seguidas de n letras b.
Agora o argumento se fecha sozinho. A classe é fechada sob interseção: se a linguagem original fosse regular, a interseção com uma regular também seria. Mas a interseção é a linguagem canônica que sabemos não ser regular. Contradição, e a hipótese cai. Nenhum bombeamento foi feito sobre a linguagem original — ele foi feito uma vez, sobre o caso canônico, e reaproveitado por transferência.
O mesmo padrão se aplica ao complemento, com uma consequência que costuma surpreender: se o complemento de uma linguagem não é regular, a linguagem também não é. Como a classe é fechada sob complemento, uma das duas ser regular obrigaria a outra a ser. Isso permite escolher, entre a linguagem e o complemento dela, aquela sobre a qual a demonstração é mais fácil — e às vezes a diferença de dificuldade é grande.
No projeto, a utilidade imediata é outra e é prática: com diferença e teste de vazio implementados, passo a poder verificar automaticamente se uma categoria léxica está contida em outra. Se a linguagem de IDENTIFICADOR estivesse contida na de PALAVRA_RESERVADA, ou vice-versa, isso indicaria um problema de especificação que hoje só apareceria no módulo 7, quando o desempate por prioridade fosse implementado. A ferramenta existe antes do problema.
Onde é fácil errar aqui. Inverter a finalidade sem completar antes. O complemento de um autômato esparso, feito trocando finais por não finais, produz um autômato que rejeita as cadeias que caem fora — quando deveria aceitá-las, porque o original as rejeitava. O estado de erro precisa existir explicitamente para poder virar final.
1.3 Tarefa 2: O lema do bombeamento, exibido rodando
O tópico — toda cadeia suficientemente longa aceita por um autômato finito pode ser decomposta e bombeada.
O lema costuma ser ensinado direto na forma contrapositiva, que é como ele se usa. Resolvi mostrá-lo antes na forma direta, sobre uma linguagem que é regular, porque quem viu a decomposição funcionando acredita nela depois, quando ela for usada para derivar contradição.
06_bombeamento.h
#ifndef PENEIRA_06_BOMBEAMENTO_H
#define PENEIRA_06_BOMBEAMENTO_H
#include <cstddef>
#include <optional>
#include <string>
#include <vector>
#include "02_cadeia.h"
#include "03_afd.h"
namespace peneira {
// A decomposição que o lema do bombeamento garante existir: toda cadeia aceita
// com comprimento maior ou igual ao número de estados pode ser escrita como
// x y z, com y não vazio, |xy| dentro do número de estados, e x y^i z aceita
// para todo i.
struct Decomposicao {
Cadeia x;
Cadeia y;
Cadeia z;
Estado repetido = kSemEstado;
std::size_t inicioDoCiclo = 0;
std::size_t fimDoCiclo = 0;
};
// Encontra a decomposição percorrendo a cadeia e anotando o estado alcançado
// após cada prefixo. Com mais símbolos lidos do que estados existentes, algum
// estado necessariamente se repete — é o princípio da casa dos pombos, e é a
// demonstração inteira do lema.
//
// Devolve vazio quando a cadeia é curta demais para forçar repetição, ou
// quando não é aceita.
std::optional<Decomposicao> decompor(const Afd& a, const Cadeia& s);
// Gera x y^i z para i de 0 até o limite. Com i igual a 1 reproduz a cadeia
// original; com 0, remove o trecho repetido.
std::vector<Cadeia> bombear(const Decomposicao& d, std::size_t ate);
// Constrói a notação de uma expressão regular que reconhece os parênteses
// balanceados até a profundidade dada — e apenas até ela.
//
// É a tentativa que todo grupo faz antes de aceitar que o modelo não dá conta:
// como não é possível cobrir profundidade arbitrária, cobre-se até k. A
// expressão cresce, o autômato cresce, e sempre existe k+1.
std::string notacaoParentesesAte(std::size_t profundidade);
// Cadeia de parênteses aninhados na profundidade dada: "((( )))" sem espaços.
Cadeia parentesesNaProfundidade(std::size_t profundidade);
} // namespace peneira
#endif // PENEIRA_06_BOMBEAMENTO_H06_bombeamento.cpp
#include "06_bombeamento.h"
#include <map>
#include <utility>
namespace peneira {
std::optional<Decomposicao> decompor(const Afd& a, const Cadeia& s) {
if (a.inicial() == kSemEstado || !a.aceita(s)) {
return std::nullopt;
}
const std::size_t n = a.quantidadeDeEstados();
if (s.size() < n) {
// Cadeia curta demais: sem forçar repetição, o lema nada garante.
return std::nullopt;
}
// Anota o estado alcançado após cada prefixo. A primeira repetição dentro
// dos primeiros n passos é o ciclo procurado — e ela existe porque há n+1
// posições anotadas para no máximo n estados distintos.
std::map<Estado, std::size_t> primeiraOcorrencia;
Estado atual = a.inicial();
primeiraOcorrencia[atual] = 0;
for (std::size_t i = 0; i < s.size() && i < n; ++i) {
atual = a.transicao(atual, static_cast<Simbolo>(s[i]));
if (atual == kSemEstado) {
return std::nullopt;
}
const auto it = primeiraOcorrencia.find(atual);
if (it != primeiraOcorrencia.end()) {
Decomposicao d;
d.inicioDoCiclo = it->second;
d.fimDoCiclo = i + 1;
d.repetido = atual;
d.x = s.substr(0, d.inicioDoCiclo);
d.y = s.substr(d.inicioDoCiclo, d.fimDoCiclo - d.inicioDoCiclo);
d.z = s.substr(d.fimDoCiclo);
return d;
}
primeiraOcorrencia[atual] = i + 1;
}
return std::nullopt;
}
std::vector<Cadeia> bombear(const Decomposicao& d, std::size_t ate) {
std::vector<Cadeia> resultado;
resultado.reserve(ate + 1);
for (std::size_t i = 0; i <= ate; ++i) {
resultado.push_back(d.x + potencia(d.y, i) + d.z);
}
return resultado;
}
std::string notacaoParentesesAte(std::size_t profundidade) {
// Alternativa por profundidade: \(\) | \(\(\)\) | \(\(\(\)\)\) | ...
// Os parênteses precisam de barra invertida porque na notação eles são
// agrupamento, não símbolo.
std::string notacao;
for (std::size_t k = 1; k <= profundidade; ++k) {
if (k > 1) {
notacao += "|";
}
for (std::size_t i = 0; i < k; ++i) notacao += "\\(";
for (std::size_t i = 0; i < k; ++i) notacao += "\\)";
}
return notacao;
}
Cadeia parentesesNaProfundidade(std::size_t profundidade) {
Cadeia s;
for (std::size_t i = 0; i < profundidade; ++i) s += '(';
for (std::size_t i = 0; i < profundidade; ++i) s += ')';
return s;
}
} // namespace peneiraA implementação é a demonstração do lema transcrita. Percorro a cadeia anotando o estado alcançado após cada prefixo. Com mais símbolos lidos do que estados existentes, há mais anotações do que valores possíveis, e algum estado necessariamente se repete — princípio da casa dos pombos. A primeira repetição delimita o ciclo, e o ciclo é o y que pode ser percorrido quantas vezes se queira.
Rodando sobre o autômato do número, que tem cinco estados, com a cadeia 123456:
estado repetido: q2 (apos 1 e apos 2 simbolos)
x = "1"
y = "2" (nao vazio, como o lema exige)
z = "3456"
|xy| = 2, dentro dos 5 estados
bombeando:
i=0 "13456" -> aceita
i=1 "123456" -> aceita
i=2 "1223456" -> aceita
i=3 "12223456" -> aceita
i=4 "122223456" -> aceitaAs três condições do lema aparecem na saída e podem ser conferidas: o y não é vazio, o comprimento de xy cabe dentro do número de estados, e todas as potências são aceitas. O caso i = 0 merece atenção porque é o que mais confunde: bombear com zero remove o trecho, e a cadeia encurtada também precisa ser aceita.
A estrutura lógica, que é onde as demonstrações erram. O lema diz que existe uma decomposição, escolhida pelo adversário, tal que para todo i a cadeia bombeada é aceita. Ao usá-lo na forma contrapositiva, quem escolhe a cadeia é você, quem escolhe a decomposição é o adversário, e você precisa exibir um i que produza cadeia fora da linguagem — para qualquer decomposição que ele escolha.
A inversão dessa ordem é o erro dominante. Escolher a decomposição em vez de tratá-la como dada produz uma demonstração que parece completa e não é. O código deixa a assimetria visível: a função de decomposição encontra a decomposição, ela não a recebe — porque no lema quem a fornece é o autômato, não quem demonstra.
Onde é fácil errar aqui. Procurar a repetição na cadeia inteira em vez de nos primeiros n passos. Se você aceitar qualquer repetição, o y encontrado pode ficar além do limite que o lema garante, e a condição sobre o comprimento de xy deixa de valer. O laço para no número de estados de propósito.
1.4 Tarefa 3: O experimento — a ferramenta diante do aninhamento
A atividade — confrontar a ferramenta construída até o módulo 5 com uma construção aninhada e documentar como e por que ela falha.
Aqui o experimento reproduz o que todo grupo faz antes de aceitar o resultado teórico: se não dá para cobrir profundidade arbitrária, cobre-se até uma profundidade k. A notação suporta alternativa, então basta enumerar — parênteses até um nível, ou até dois, ou até três.
Rodando o pipeline completo do módulo 5 sobre essa expressão, para k de 1 a 8:
k estados aceita k aceita k+1
1 3 sim nao
2 5 sim nao
3 7 sim nao
4 9 sim nao
5 11 sim nao
6 13 sim nao
7 15 sim nao
8 17 sim naoTrês leituras dessa tabela, em ordem crescente de importância.
A primeira é que funciona — para cada k, o autômato aceita corretamente a profundidade k. Não há defeito de implementação; a ferramenta faz o que promete.
A segunda é o crescimento: os estados seguem 2k + 1, linear em k. Cada nível de profundidade cobrível custa dois estados. Isso é a memória do autômato sendo gasta para contar, e contar é exatamente o que um autômato finito não pode fazer sem limite.
A terceira é a coluna da direita, que é a resposta: sempre falha em k+1. E como para todo k existe k+1, nenhum valor resolve. O autômato precisaria de infinitos estados, e “autômato finito com infinitos estados” é contradição em termos.
O que o experimento prova, e o que não prova. Ele não prova nada. Mostrar que oito tentativas falharam não exclui a nona — talvez exista uma expressão esperta que ninguém pensou. O que o experimento faz é revelar o padrão: a falha é sempre no primeiro nível além do coberto, e o custo em estados cresce com o alcance.
A demonstração formal é que transforma padrão em impossibilidade. Supondo que a linguagem fosse regular, existiria um autômato com algum número n de estados. Tome a cadeia com n aberturas seguidas de n fechamentos: ela é aceita e tem comprimento maior que n, então o lema garante uma decomposição com y não vazio dentro dos primeiros n símbolos — que são todos aberturas. Bombear com i = 2 acrescenta aberturas sem acrescentar fechamentos, e a cadeia resultante está desbalanceada. Contradição: o autômato teria de aceitar uma cadeia que não pertence à linguagem. Logo não existe tal autômato.
Prova e experimento fazem coisas diferentes e se sustentam mutuamente. O experimento mostra como falha e dá a intuição do porquê; a prova mostra que sempre falhará. Entregar só um dos dois é entregar metade.
Onde é fácil errar aqui. Concluir do experimento que “a ferramenta tem um limite que poderia ser aumentado”. O limite não é da implementação — não é o número de estados que cabe na memória, nem uma restrição da notação. É do modelo. Nenhuma implementação de autômato finito, em nenhuma linguagem, com qualquer quantidade de memória, resolve isto.
1.5 Referência teórica: a caracterização por classes de equivalência
O módulo apresenta, em tratamento conceitual, uma segunda forma de caracterizar as linguagens regulares: uma linguagem é regular exatamente quando o número de classes de prefixos indistinguíveis é finito. Dois prefixos são distinguíveis quando existe um sufixo que completa um e não completa o outro.
Resolvi torná-la observável, porque ela dá o mesmo resultado do lema por um caminho que muitos estudantes acham mais natural — contar em vez de derivar contradição.
Para os parênteses balanceados, os prefixos de abertura são todos distinguíveis dois a dois: ( precisa de um fechamento para completar, (( precisa de dois, e nenhum sufixo completa os dois ao mesmo tempo. Como há infinitas profundidades, há infinitas classes.
No autômato construído até a profundidade k, isso aparece como contagem:
k estados estados dos prefixos
2 5 2
4 9 4
6 13 6
8 17 8Um estado distinto por profundidade, exatamente. O autômato é obrigado a gastar um estado por classe de equivalência que precise distinguir — e é essa correspondência, entre classes e estados, que o teorema formaliza. Como as classes são infinitas e os estados são finitos, não há autômato.
Vale notar a ligação com o módulo anterior: o autômato mínimo tem exatamente um estado por classe de equivalência. É por isso que ele é único, e é por isso que a minimização e esta caracterização são o mesmo fato visto de dois ângulos.
1.6 O que isso significa para o projeto
Fecho registrando a consequência concreta, que é o que a atividade pede na conclusão.
A parte da Peneira que não é regular é a condição composta do where, com parênteses aninhados de profundidade arbitrária. Tudo o mais na linguagem — identificadores, números, textos, padrões, pontuação — é regular e já está resolvido pelo motor pronto.
Isso define a divisão de trabalho do resto do semestre com precisão. O analisador léxico do módulo 7 fica com o que é regular, e é só isso que ele consegue fazer. A estrutura aninhada sobe para a análise sintática, que precisa de um modelo com memória de profundidade arbitrária — a pilha, que chega no módulo 9 como autômato de pilha e no módulo 10 como analisador de verdade.
A separação entre análise léxica e sintática, que no módulo 1 foi apresentada como decomposição clássica e podia parecer convenção, tem agora uma justificativa demonstrada: são fases separadas porque exigem modelos de poder diferente, e o mais fraco dos dois é comprovadamente incapaz de fazer o trabalho do outro.
1.7 Verificação da entrega
| Item | Como conferir | Estado nesta referência |
|---|---|---|
| Propriedades de fechamento | Construções conferidas contra as definições, cadeia a cadeia | Quatro operações, todas coerentes |
| Alfabeto explícito | Complemento correto fora dos símbolos originais | Parâmetro obrigatório nas quatro |
| Decisão de linguagem vazia | Interseção de uma linguagem com o próprio complemento | Vazia, como tem de ser |
| Lema na forma direta | Decomposição encontrada e potências aceitas | y não vazio, \lvert xy \rvert \le n, i de 0 a 5 aceitos |
| Experimento do aninhamento | Aceita em k, falha em k+1, para k de 1 a 8 | Confirmado; estados crescem como 2k+1 |
| Demonstração formal | Estrutura contrapositiva completa, com a escolha do adversário respeitada | Escrita na tarefa 3 |
| Articulação prova × experimento | O texto diz o que cada um estabelece e o que não estabelece | Bloco dedicado |
| Classes de equivalência | Contagem de estados distintos por profundidade | Um por profundidade, confirmado |
| Código compila limpo | Nenhum aviso sob o modo estrito | Atende, verificado por compilação e execução |
O que quero deixar registrado sobre esta entrega é que ela é a única do semestre cujo resultado principal é uma impossibilidade. O código escrito aqui não acrescenta capacidade ao compilador — acrescenta conhecimento sobre o que a capacidade existente não alcança, e é esse conhecimento que torna o próximo bloco necessário em vez de arbitrário.