flowchart LR
A["Linguagens regulares<br/>L1 e L2"] --> U["Uniao"]
A --> C["Concatenacao"]
A --> K["Fecho de Kleene"]
A --> N["Complemento"]
A --> I["Intersecao"]
U --> U1["Novo inicial<br/>com transicoes vazias"]
C --> C1["Transicao vazia do final<br/>do primeiro ao inicial do segundo"]
K --> K1["Novo estado inicial e final,<br/>com volta do final antigo"]
N --> N1["Inverter finais sobre AFD<br/>determinístico e COMPLETO"]
I --> I1["Produto: pares de estados<br/>avancando em paralelo"]
U1 --> R["Resultado continua regular"]
C1 --> R
K1 --> R
N1 --> R
I1 --> R
1 Módulo 06: Limites das Linguagens Regulares — Resumo
Esta é a versão de revisão. Recapitulo em ritmo de véspera o que este módulo tem de guardado; o tratamento por inteiro está na versão completa do material deste módulo e no livro. Use este texto para conferir se você reproduz, de cabeça e na ordem certa, uma demonstração de não regularidade.
Tente de novo: escreva uma expressão regular para parênteses balanceados. Um nível sai fácil, dois também, três com paciência — e aí vem a sensação de que cada nível novo pede um pedaço novo e isso não acaba nunca. A sensação está certa, e este módulo existe para você saber demonstrar que está.
1.1 O que sobrevive à combinação: propriedades de fechamento
Uma classe é fechada sob uma operação quando aplicá-la a membros da classe não faz você sair dela — igual aos inteiros, fechados sob soma e não sob divisão. A classe regular é fechada sob união, concatenação, fecho, complemento, interseção, diferença e reverso, e cada afirmação vem com uma construção que se implementa.
As três primeiras saem de graça porque são os três operadores da notação — demonstração correta que não ensina nada, já que a definição foi escrita para tornar o resultado trivial. A versão instrutiva passa pelos autômatos, e nas três o não determinismo faz o mesmo papel: adiar uma escolha que a máquina ainda não tem informação para tomar.
O complemento é o que machuca, porque parece trivial: inverta finais e não finais, pronto. Duas hipóteses sustentam esse “pronto”, e negligenciar qualquer uma produz um autômato bem formado que reconhece a linguagem errada. A primeira é o determinismo — num não determinístico, aceitar é “algum caminho chega a final”, e a negação é “nenhum caminho chega”, não “algum caminho chega a não final”. A segunda é a completude — com transição parcial, as cadeias que caem nos buracos morrem no meio antes e depois da inversão. Totalize antes de inverter, com um estado de erro absorvente; depois da inversão é ele que aceita o que antes morria, e o defeito de esquecê-lo passa em todo teste feito sobre o alfabeto original.
A interseção sai de De Morgan em uma linha, elegante e péssima como algoritmo. Implementa-se o produto: um estado é um par que registra onde cada máquina está, e ler um símbolo faz as duas avançarem juntas. A escolha dos finais é a única diferença entre interseção e união — par final quando os dois componentes são finais, ou quando pelo menos um é —, então a construção escrita uma vez, com um predicado como parâmetro, entrega as duas.
Daí vem a diferença, e com ela algo mais forte do que parece. Decidir se a linguagem de um autômato é vazia é uma busca em grafo: algum final é alcançável a partir do inicial? Combinando, a inclusão é decidível, porque uma linguagem está contida na outra exatamente quando a diferença é vazia, e a igualdade também, por dupla inclusão. Isso deixa de valer um andar acima: decidir se duas gramáticas livres de contexto geram a mesma linguagem é indecidível.
E o uso que mais me interessa: fechamento é ferramenta de demonstração de impossibilidade. Se A é regular e a interseção de A com B não é, então B não é, sem atacar B de frente — por isso apresento fechamento antes do resultado central.
Pare e pense. Toda construção desta seção parte de autômatos com finitos estados e produz autômatos com finitos estados — muitos, às vezes, e sempre finitos. Se nenhuma delas cria memória nova, que tipo de linguagem elas jamais alcançarão?
1.2 A casa dos pombos: o estado que se repete sem que ninguém perceba
A resposta cabe numa contagem que você faz de cabeça. Um autômato determinístico com n estados, ao processar uma cadeia de comprimento m, percorre m + 1 estados — um a mais que o comprimento, porque existe um estado antes de qualquer leitura. Se m \ge n, dois deles são necessariamente iguais: é o princípio da casa dos pombos, que Dirichlet formulou explicitamente na década de 1830 sob o nome de princípio das gavetas.
Daqui sai todo o resto: uma máquina finita, ao ler uma cadeia longa, volta obrigatoriamente a um estado em que já esteve, e não tem como saber que voltou, porque o estado é toda a memória que ela tem.
flowchart LR
q0(("r0")) -->|"x: primeiros simbolos"| qi(("ri"))
qi -->|"y: o ciclo"| qj(("rj = ri"))
qj -->|"z: o resto"| qf((("rm final")))
qi -.->|"repetir y quantas vezes quiser"| qi
Se dois estados coincidem, a cadeia se parte em três: o prefixo x até a primeira visita, o trecho y que sai do estado e volta a ele, e o resto z. Percorrer o ciclo y duas vezes, dez ou nenhuma deixa a máquina no mesmo lugar; logo xz, xyz e em geral xy^iz terminam no mesmo estado, e se uma é aceita, todas são. Aplique aos parênteses: o ciclo cai no bloco de aberturas, repeti-lo acrescenta aberturas sem fechamentos, e a máquina aceitaria uma cadeia desbalanceada. A demonstração é essa; o resto é notação, e necessária.
1.3 O lema do bombeamento e a ordem dos lances
Por que formalizar, se o argumento já está de pé? Porque a intuição tem duas frouxidões. Fala em “cadeia longa o bastante” sem dizer em relação a quê, e numa prova por absurdo a ordem em que as quantidades são escolhidas decide se o argumento vale. E não diz onde está o ciclo — se ele atravessasse o meio da cadeia, repeti-lo poderia produzir algo ainda balanceado.
O lema aperta as duas. Se L é regular, existe n \ge 1 tal que toda cadeia w \in L com |w| \ge n se escreve w = xyz com |y| \ge 1, com |xy| \le n e com xy^iz \in L para todo i \ge 0. A primeira condição impede o trecho bombeado de ser vazio; a segunda é a de localização, que confina o ciclo aos primeiros n símbolos; a terceira é a conclusão. A demonstração é a seção anterior escrita com cuidado, tomando n como o número de estados. O resultado é atribuído a Bar-Hillel, Perles e Shamir, de 1961.
Com quantificadores explícitos, ele diz “existe n, para toda w, existe decomposição, para todo i”. Para provar que a linguagem não é regular você nega isso, e a negação inverte tudo: “para todo n, existe w, para toda decomposição, existe i”.
sequenceDiagram
participant A as Adversario, que defende ser regular
participant D as Demonstrador, que e voce
A->>D: 1. anuncia o comprimento de bombeamento n
D->>A: 2. exibe a cadeia w da linguagem, de comprimento pelo menos n
A->>D: 3. decompoe w em x, y, z respeitando as duas condicoes
D->>A: 4. exibe o expoente i que joga xy^i z para fora
Note over D: vitoria do Demonstrador:<br/>a linguagem nao e regular
Guarde a forma lógica como uma partida. O Adversário defende que a linguagem é regular e anuncia um número; você exibe uma cadeia da linguagem com pelo menos aquele comprimento, e esse é o lance decisivo, porque cadeia ruim perde a partida mesmo com estratégia perfeita depois; ele decompõe a sua cadeia do jeito que mais lhe atrapalhe; você joga por último, com um expoente que atire o resultado para fora da linguagem.
O erro dominante é sempre o mesmo: o estudante escolhe a decomposição. O comprimento é dado; a cadeia é sua, e é aí que está a liberdade; a decomposição não é sua, e o argumento tem de cobrir todas as admissíveis; o expoente é seu. Uma prova que comece com “tome o trecho bombeado igual ao primeiro símbolo” está errada mesmo com a conta subsequente certa.
O contorno é o truque de quase toda demonstração de não regularidade: você não controla a decomposição, mas controla a cadeia — se os primeiros símbolos forem todos iguais, a localização obriga o trecho bombeado a ser feito só deles. Três armadilhas menores: esquecer que o expoente zero é permitido e remove o trecho; supor que os trechos externos são não vazios, quando só o do meio tem essa exigência; e usar o lema na direção errada, já que ele é implicação e não equivalência.
1.4 As demonstrações na prática
O caso canônico é o das cadeias com tantos a quantos b, nessa ordem, e os outros o imitam. Suponha regular, com comprimento de bombeamento p; escolha p letras a seguidas de p letras b; a localização obriga o trecho bombeado a ser feito só de a; com expoente dois você acrescenta a sem acrescentar b e sai da linguagem. Como a decomposição era arbitrária, a propriedade falha. Os parênteses caem pelo mesmo caminho, e é esse resultado que decide a arquitetura de todo compilador: parênteses em expressões, blocos, condicionais dentro de condicionais — cada aninhamento carrega embutida a linguagem dos parênteses balanceados, e é por isso que a análise sintática é fase separada.
| Linguagem | Cadeia a escolher | Expoente | Por que funciona |
|---|---|---|---|
Tantos a quantos b em ordem |
p letras a, depois p letras b |
2 ou 0 | Localização confina o ciclo ao bloco de a |
Mais a do que b |
uma letra a a mais que o bloco de b |
0 | Remover símbolos inverte a desigualdade |
| Comprimento quadrado perfeito | bloco de a de comprimento quadrado |
2 | Lacuna entre quadrados consecutivos |
| Comprimento primo | bloco de a de comprimento primo grande |
um a mais que o primo | O comprimento resultante é composto |
Duas linhas ensinam mais do que o caso que resolvem. A dos quadrados é um argumento de lacuna: eles se afastam cada vez mais e o bombeamento acrescenta incremento limitado, então cadeias longas caem no vão — vale igual para potências de dois e fatoriais. A dos primos mostra que o expoente pode depender de tudo o que veio antes.
E antes de bombear, pergunte se dá para transferir: para as cadeias com o mesmo número de a e de b em qualquer ordem, o ataque frontal dá trabalho, mas a interseção delas com blocos de a seguidos de blocos de b é o caso canônico. Duas linhas.
flowchart TD
P["Preciso mostrar que L nao e regular"] --> T{"Existe R regular simples<br/>tal que L interseccao R<br/>seja um caso canonico?"}
T -->|sim| TR["Transferencia por fechamento:<br/>tres linhas"]
T -->|nao| CO{"O complemento de L<br/>e mais facil de atacar?"}
CO -->|sim| TR
CO -->|nao| B["Lema do bombeamento:<br/>escolher bem a cadeia"]
B --> OK{"Fechou a contradicao<br/>para toda decomposicao?"}
OK -->|sim| FIM["Demonstrado"]
OK -->|nao| MN["Myhill-Nerode:<br/>exibir conjunto infinito<br/>dois a dois distinguivel"]
MN --> FIM
TR --> FIM
E a advertência que separa quem entendeu de quem memorizou: existe linguagem não regular que satisfaz a propriedade de bombeamento. Fracassar em bombear não demonstra que a linguagem é regular; demonstra que a ferramenta não serviu.
1.5 Myhill-Nerode: o que é um estado, afinal
Mudo de ferramenta, e este é o ponto de vista mais esclarecedor da teoria. A pergunta que o organiza é: para que serve um estado? Um autômato determinístico que leu um prefixo guardou dele apenas o estado atual, e se dois prefixos levam ao mesmo estado ele se comportará de forma idêntica daí em diante. Vem então a pergunta que independe de autômato algum: dados dois prefixos, existe continuação que os distinga, no sentido de exatamente uma das cadeias completas pertencer à linguagem?
No caso canônico, a e aa são distinguidos por b, porque ab está na linguagem e aab não. Generalizando, os prefixos formados só de a são dois a dois distinguíveis, são infinitos, e os estados são finitos. Acabou — não regularidade demonstrada de novo, sem bombear nada e sem argumento por absurdo.
flowchart LR
subgraph Prefixos["Prefixos lidos"]
P0["vazio"]
P1["a"]
P2["aa"]
P3["aaa"]
PN["..."]
end
subgraph Classes["Classes de equivalencia"]
C0["classe 0"]
C1["classe 1"]
C2["classe 2"]
C3["classe 3"]
CN["infinitas"]
end
P0 --> C0
P1 --> C1
P2 --> C2
P3 --> C3
PN --> CN
Classes --> E["Cada classe exige<br/>um estado proprio"]
E --> F["Indice infinito:<br/>nenhum AFD reconhece"]
Formalizando: dois prefixos são equivalentes quando nenhuma continuação os distingue, essa relação particiona as cadeias em classes, e o índice é o número de classes. O teorema de Myhill-Nerode — trabalhos independentes de John Myhill, de 1957, e de Anil Nerode, de 1958 — diz que a linguagem é regular se e somente se o índice é finito, e que o autômato mínimo tem tantos estados quantas são as classes. Daí sai a explicação retroativa do módulo anterior: a minimização não é heurística de compressão, é o cálculo de um objeto determinado pela linguagem, e por isso dois autômatos mínimos são iguais a menos de renomeação. Depois que isso assenta, você para de desenhar círculos até funcionar e passa a perguntar o que precisa ser lembrado do prefixo lido. Cada resposta é um estado. Eu mesmo demorei para perceber.
1.6 O limite medido no caso conduzido
Na Peneira, a construção de profundidade arbitrária está na condição do where: comparações ligadas por conectivos, com parênteses, e uma condição composta podendo ser operando de outra. Todo o resto — nomes, números, textos, literais de padrão, pontuação — é regular e já está resolvido pelo motor construído até aqui. Reduzida ao essencial, aquela condição é a linguagem dos parênteses balanceados: a demonstração já feita vale literalmente.
O caso conduzido implementa as construções de fechamento com o alfabeto sempre explícito na assinatura — tradução em código da armadilha do complemento. E implementa o lema sobre uma linguagem que é regular, encontrando a decomposição mecanicamente:
struct Decomposicao {
Cadeia x;
Cadeia y;
Cadeia z;
Estado repetido = kSemEstado;
std::size_t inicioDoCiclo = 0;
std::size_t fimDoCiclo = 0;
};
std::optional<Decomposicao> decompor(const Afd& a, const Cadeia& s);
std::vector<Cadeia> bombear(const Decomposicao& d, std::size_t ate);
std::string notacaoParentesesAte(std::size_t profundidade);Note a assimetria: a função encontra a decomposição, não a recebe de fora — quem a fornece é o autômato, não quem demonstra. E a busca pela repetição para no número de estados: é a condição de localização virando código.
A última função é o experimento: já que não dá para cobrir profundidade arbitrária, cobre-se até k enumerando os casos. Rodando o pipeline completo para k de um a oito, o autômato mínimo tem três, cinco, sete estados e assim por diante — dois a mais por nível, memória gasta para contar, o que confirma numericamente a contagem de classes de Myhill-Nerode. Em cada linha ele aceita a profundidade k e falha na seguinte, e como para todo k existe k+1, nenhum valor resolve. O experimento não prova nada, porque oito falhas não excluem a nona; ele revela o padrão, e é a demonstração que transforma padrão em impossibilidade. É essa articulação que a entrega do seu grupo avalia — experimento sozinho é anedota, prova sozinha é abstração.
1.7 Síntese
A classe regular é fechada sob sete operações, cada uma com construção implementável; o complemento exige determinismo e completude, e união e interseção são o mesmo produto com predicados diferentes. O resultado central nasce de uma contagem: máquina com n estados lendo n símbolos repete estado, e o trecho entre as duas visitas é um ciclo que ela não percebe. O lema é essa observação com duas amarrações — a ordem dos lances e a localização —, e Myhill-Nerode fecha a lacuna por ser equivalência exata.
flowchart TD
T["Texto do programa"] --> D{"A construcao exige contar<br/>profundidade sem cota?"}
D -->|nao| L["Analise lexica<br/>autômato finito, uma passada"]
D -->|sim| S["Analise sintatica<br/>autômato de pilha"]
L --> LX["Nomes, numeros, textos,<br/>literais de padrao, pontuacao"]
S --> SX["Condicoes compostas,<br/>blocos, expressoes aninhadas"]
LX --> R["Fases separadas por<br/>impossibilidade demonstrada,<br/>nao por convencao"]
SX --> R
Volte aos parênteses da abertura. Você não escreveu aquela expressão e agora sabe demonstrar que ninguém escreverá — limitação do modelo, não do seu talento. O que isso entrega ao resto do curso é uma divisão de trabalho justificada: o regular fica com o analisador léxico, em uma passada e sem retrocesso; o aninhado sobe para o autômato de pilha, cuja memória não tem cota. A pilha não foi acrescentada por conveniência: foi acrescentada porque este módulo demonstrou que sem ela não há saída.