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
Bem-vindo ao módulo que não entrega ferramenta nova. Todos os anteriores lhe deram uma capacidade a mais: descrever, reconhecer, converter, minimizar. Este aqui faz o contrário — ele desenha a fronteira do que o motor de autômatos que você já conhece nunca vai alcançar, por mais memória, tempo ou esperteza que se jogue no problema. Parece recuo. É o módulo que torna necessária a metade seguinte do curso.
1.1 O problema: a expressão regular que não termina nunca
Vou começar pedindo que você tente uma coisa antes de continuar lendo. Escreva uma expressão regular que reconheça sequências de parênteses balanceados.
Não é pegadinha, e você já tem tudo de que precisa: sabe descrever alternativas, repetições e a composição das duas. A primeira tentativa sai rápido. Um par de parênteses? Fácil. Um par que pode ter outro dentro? Também dá. Três níveis, ainda dá. E aí, lá pelo quarto ou quinto nível, chega a sensação incômoda de que isso não vai acabar nunca, de que cada nível novo pede um pedaço novo de expressão e o texto cresce sem chegar a lugar nenhum.
Olha só: a sensação está certa. Não vai acabar nunca. E o motivo não é que você seja desastrado com a notação, nem que a ferramenta seja pobre, nem que falte um recurso que outro programa ofereceria. É impossível no sentido forte da palavra: não existe expressão regular, não existe autômato finito, não existe nenhum objeto de nenhum dos formalismos equivalentes que reconheça essa linguagem. E, o que mais importa para você, essa impossibilidade tem demonstração — curta e ao seu alcance agora.
Abro por aí porque o assunto tem uma utilidade prática raramente dita em voz alta. Você vai passar a vida esbarrando em obstáculos de implementação, e precisará distinguir dois casos que, de fora, se parecem: aquele em que a coisa não funciona porque o seu código tem defeito, e aquele em que não funciona porque o modelo escolhido não comporta o que você está pedindo. No primeiro, insistir é o certo. No segundo, insistir é queimar semana. Já vi mais tempo desperdiçado nessa confusão do que em qualquer outra causa isolada.
Este capítulo pressupõe, de forma bastante concreta, o que os capítulos anteriores construíram, e vale nomear o que é.
Pressuponho que você saiba descrever uma linguagem por uma expressão regular e ler a notação sem hesitar diante de uma alternativa dentro de uma estrela. Pressuponho que saiba desenhar um autômato finito determinístico, seguir uma cadeia por ele símbolo a símbolo e dizer, em cada ponto, em que estado a máquina está. Pressuponho familiaridade com o autômato não determinístico e com as transições vazias, com a construção que traduz uma expressão regular em autômato, com a determinização por subconjuntos e com a minimização por refinamento de partições — não os detalhes de implementação, mas o fato de que os quatro modelos de descrição são equivalentes em poder e de que existe um caminho mecânico de qualquer um deles para qualquer outro.
Esse último ponto é o que torna este capítulo possível. Quando eu disser que uma linguagem não é regular, a afirmação vale simultaneamente contra expressão regular, contra autômato determinístico, contra autômato não determinístico e contra qualquer outro formalismo equivalente, porque a equivalência já foi estabelecida. Sem ela, cada demonstração de impossibilidade teria de ser refeita quatro vezes, e o resultado seria sobre um formalismo em vez de sobre uma classe de linguagens.
O que não pressuponho é qualquer experiência anterior com demonstrações de impossibilidade. É provável que este seja o primeiro momento do seu percurso em que você precisa provar que algo não pode ser feito, e não que pode. A diferença é maior do que parece, e é por ela que vou começar.
1.2 Propriedades de fechamento: o que sobrevive à combinação
Antes de demonstrar que algo é impossível, vale saber o que é possível. Dizemos que uma classe de linguagens é fechada sob uma operação quando aplicar essa operação a membros da classe não faz você sair dela. É a mesma ideia dos inteiros: fechados sob soma, subtração e multiplicação, e não fechados sob divisão, porque dividir dois inteiros pode produzir algo que já não é inteiro.
As três primeiras são de graça por um motivo que vale explicitar: elas correspondem exatamente aos três operadores da notação de expressão regular. Se duas linguagens têm expressões, a alternativa entre elas denota a união, a justaposição denota a concatenação e a estrela denota o fecho. Fim da demonstração — que é correta e não explica nada, porque só observa que a definição foi escrita para tornar o resultado trivial. A versão instrutiva passa pelos autômatos: para a união, crie um estado inicial novo e ligue-o por transições vazias aos dois iniciais antigos; para a concatenação, ligue o final do primeiro ao inicial do segundo; para o fecho, crie um estado que é inicial e final ao mesmo tempo, com volta do final antigo. Repare no papel do não determinismo nas três: ele é o dispositivo que permite adiar uma escolha — qual ramo tomar, onde cortar a cadeia, quantas voltas dar — que a máquina ainda não tem informação para fazer.
Agora uma que não tem operador correspondente na notação, e que por isso costuma surpreender: o complemento. Tome um autômato determinístico e troque os estados finais pelos não finais. Pronto, ele reconhece o complemento. Simples assim — e é aqui que quase todo mundo se machuca.
Duas hipóteses, e negligenciar qualquer uma produz um autômato bem formado que reconhece a linguagem errada. A primeira é o determinismo: num autômato não determinístico, aceitar significa que algum caminho chega a estado final, e a negação disso é “nenhum caminho chega”, não “algum caminho chega a estado não final”. Inverter finais de um não determinístico não complementa nada. A segunda é a completude: se a função de transição for parcial, as cadeias que caem nos buracos morrem no meio do caminho e continuam morrendo depois da inversão. O resultado rejeita ao mesmo tempo as cadeias de dentro e as de fora. A correção é totalizar antes de inverter, acrescentando um estado de erro absorvente que recebe todas as transições ausentes — depois da inversão, é justamente ele que aceita o que antes morria.
Esse é o tipo de defeito que passa em qualquer teste construído sobre o alfabeto que o autômato original já usava, e só aparece meses depois, quando alguém alimenta a máquina com um símbolo em que ninguém pensou.
Com complemento e união no bolso, a interseção sai por De Morgan em uma linha — elegante, e péssima como algoritmo, porque manda complementar duas vezes, unir e complementar de novo. A construção que se implementa é o produto: um estado do produto é um par que registra em que estado cada máquina está, e ler um símbolo faz as duas avançarem em paralelo. O detalhe bonito é que a escolha dos estados finais é a única diferença entre interseção e união — par final quando os dois componentes são finais dá interseção, quando pelo menos um é final dá união. Escrita uma vez com um predicado como parâmetro, a mesma construção entrega as duas operações.
E com interseção mais complemento, a diferença sai de graça também. Isso destrava algo que parece pequeno e não é. Decidir se a linguagem de um autômato é vazia é uma busca em grafo: basta perguntar se algum estado final é alcançável a partir do inicial. Combine com a diferença e você tem um resultado forte: a inclusão entre linguagens regulares é decidível, porque uma está contida na outra exatamente quando a diferença é vazia; e a igualdade também, porque é a dupla inclusão. Guarde isso, porque deixa de valer um andar acima — decidir se duas gramáticas livres de contexto geram a mesma linguagem é indecidível. Você pode perguntar a uma máquina se duas expressões regulares descrevem a mesma coisa e obter resposta garantida; não pode fazer o mesmo com duas gramáticas de linguagem de programação.
Chego ao uso que mais me interessa. Propriedades de fechamento são ferramentas de demonstração de impossibilidade. Se a classe é fechada sob interseção, e você sabe que uma linguagem A é regular, e sabe que A \cap B não é regular, então B não é regular — sem atacar B diretamente. Esse tipo de argumento por transferência resolve uma proporção grande dos exercícios com muito menos escrita do que o ataque frontal, e é a razão pela qual eu apresento fechamento antes do resultado central, contrariando a ordem de vários livros.
Pare e pense. Todas as construções desta seção partem de autômatos com finitos estados e produzem autômatos com finitos estados — eventualmente muitos, sempre finitos. Se nenhuma delas introduz memória nova, que tipo de linguagem elas jamais conseguirão alcançar, por mais que você as combine?
1.3 A casa dos pombos, e o estado que se repete sem que ninguém perceba
A resposta à pergunta acima cabe numa contagem que você faz de cabeça.
Pegue um autômato determinístico com exatamente n estados e uma cadeia de comprimento m. Processá-la produz uma sequência de estados: o inicial, o alcançado após o primeiro símbolo, o alcançado após dois, e assim por diante. Essa sequência tem m + 1 elementos, um a mais do que o comprimento da cadeia, porque existe um estado antes de qualquer leitura. Agora conte: são m+1 estados retirados de um conjunto de n elementos. Se m \ge n, então necessariamente dois elementos da sequência são iguais. Não é probabilidade alta, é obrigação lógica — é o princípio da casa dos pombos, que Dirichlet formulou explicitamente na década de 1830, em teoria dos números, sob o nome de princípio das gavetas.
Detenha-se aqui, porque é desta frase que sai tudo o mais. 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. Não há registro, não há contador, não há histórico. O estado é toda a memória que ela possui, e estar em determinado estado pela segunda vez é, do ponto de vista da máquina, indistinguível de estar nele pela primeira.
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 da sequência coincidem, a cadeia se parte naturalmente em três pedaços: o prefixo x que leva até a primeira visita, o trecho y que sai do estado e volta a ele, e o resto z. O trecho y é um ciclo. E se percorrer y uma vez leva de um estado a ele mesmo, percorrê-lo duas vezes também leva, e dez vezes também, e não percorrê-lo nenhuma vez deixa a máquina exatamente onde ela já estava. Conclusão: as cadeias xz, xyz, xyyz e em geral xy^iz terminam todas no mesmo estado. Se uma é aceita, todas são.
Volte aos parênteses com esse óculos. Uma cadeia longa de aberturas seguidas de fechamentos, processada por um autômato hipotético que reconhecesse a linguagem, teria de repetir estado em algum ponto do trecho de aberturas. O ciclo correspondente é feito só de aberturas. Repeti-lo acrescenta aberturas e não acrescenta fechamentos, produzindo uma cadeia desbalanceada que a máquina, ainda assim, aceitaria. Essa é a demonstração inteira. O resto é notação — e é notação necessária, como vou mostrar agora.
1.4 O lema do bombeamento
Se o argumento é esse, por que precisamos de um enunciado formal com três condições? Porque a intuição acima tem duas frouxidões, e cada uma delas, solta, produz demonstração inválida.
A primeira é que ela 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 é o que determina se o argumento vale. A segunda é que ela não diz onde está o ciclo. No argumento dos parênteses eu precisei que ele estivesse dentro do bloco de aberturas; se pudesse atravessar o meio da cadeia, repeti-lo poderia produzir cadeia ainda balanceada e nada fecharia.
O lema aperta as duas frouxidões. Ele diz: se L é regular, existe um inteiro n \ge 1, o comprimento de bombeamento, tal que toda cadeia w \in L com |w| \ge n se escreve como 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, o que tornaria o lema trivial. A segunda é a de localização, e é ela que confina o ciclo aos primeiros n símbolos. A terceira é a conclusão.
A demonstração é a seção anterior escrita com cuidado: tome n igual ao número de estados do autômato; entre os n+1 primeiros estados percorridos há repetição, pela casa dos pombos; corte a cadeia nos dois pontos de repetição e confira as três condições. O resultado é atribuído ao trabalho de Bar-Hillel, Perles e Shamir, de 1961, sobre propriedades formais de gramáticas de estrutura sintagmática, embora a ideia já esteja implícita nos trabalhos fundadores de Kleene, de 1956, e de Rabin e Scott, de 1959.
Agora o ponto em que mais gente se perde, e vou ser chato porque a chatice é justificada pela estatística das provas que corrijo. Escrito com quantificadores explícitos, o lema tem a forma “existe n, para toda w, existe a decomposição, para todo i”. Quando você quer provar que a linguagem não é regular, nega essa fórmula, 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
A forma lógica é precisa e difícil de manter na cabeça. Guarde-a como uma partida entre dois jogadores. O Adversário defende que a linguagem é regular; você é o Demonstrador. Ele joga primeiro e anuncia um número — pode ser um, mil, um bilhão, e a sua estratégia tem de funcionar para todos. Você joga em seguida e exibe uma cadeia da linguagem com comprimento pelo menos aquele; esse é o lance mais importante da partida, porque cadeia ruim perde o jogo mesmo com estratégia perfeita depois. Ele joga de novo e decompõe a sua cadeia, escolhendo a decomposição que mais lhe atrapalhe. E você joga por último, exibindo um expoente que jogue o resultado para fora da linguagem.
O erro dominante é sempre o mesmo: o estudante escolhe a decomposição. Você escolhe o comprimento de bombeamento? Não, ele é dado. A cadeia? Sim, e é aí que está a sua liberdade. A decomposição? Não — ela é lance do Adversário, e o seu argumento tem de cobrir todas as decomposições admissíveis. O expoente? Sim, e pode ser diferente para cada família de decomposições. Uma prova que diga “tome y igual ao primeiro símbolo” está errada mesmo com a conta subsequente certa, porque assume uma decomposição particular quando o enunciado obriga a considerar todas.
O contorno dessa dificuldade é o truque técnico de quase toda demonstração de não regularidade: você não controla a decomposição, mas controla a cadeia — e, escolhendo-a com cuidado, força a decomposição a ter a forma que lhe convém. Se os primeiros símbolos forem todos iguais, a condição de localização obriga o trecho bombeado a ser feito só deles. Você acaba de eliminar as decomposições inconvenientes sem escolher nenhuma.
Três armadilhas menores, todas frequentes. Esquecer que i = 0 é permitido, e que bombear com zero remove o trecho em vez de repeti-lo — às vezes é o expoente zero que dá a contradição mais limpa, às vezes é ele que estraga uma prova que parecia funcionar. Supor que os trechos externos são não vazios, quando só o do meio tem essa exigência. E, a mais insidiosa, usar o lema na direção errada: ele é implicação, não equivalência. Mostrar que uma linguagem satisfaz a propriedade de bombeamento não prova que ela é regular. Se alguém lhe entregar uma prova cuja conclusão seja “logo a linguagem é regular, pelo lema do bombeamento”, pode devolver sem ler o resto.
1.5 Demonstrações de não regularidade na prática
O caso canônico é L = \{a^n b^n\}, e ele é o modelo que todos os outros seguem. Suponha regular, com comprimento de bombeamento p. Escolha a cadeia a^p b^p, que está na linguagem e é longa o bastante. Como os primeiros p símbolos são todos a, a condição de localização obriga o trecho bombeado a ser feito só de a, com pelo menos um. Bombeando com expoente dois, você acrescenta a sem acrescentar b e sai da linguagem. Como a decomposição era arbitrária, a propriedade falha, e a linguagem não é regular. Repare onde exatamente a condição de localização foi usada: é ela que permitiu afirmar a forma do trecho bombeado, e é ela que torna a demonstração curta.
Os parênteses balanceados caem pelo mesmo caminho, com (^p)^p no lugar. E vale explicitar por que esse resultado decide a arquitetura de todo compilador: a estrutura sintática de praticamente toda linguagem de programação contém aninhamento de profundidade arbitrária — parênteses em expressões, chaves em blocos, condicionais dentro de condicionais, chamadas dentro de argumentos de chamadas. Cada uma carrega, embutida, a linguagem dos parênteses balanceados, e nenhuma é reconhecível por autômato finito. É por isso, e não por tradição, que a análise sintática existe como fase separada da análise léxica.
| Linguagem | Cadeia a escolher | Expoente que resolve | Por que funciona |
|---|---|---|---|
| \{a^nb^n\} | a^pb^p | 2 ou 0 | Localização confina o ciclo ao bloco de a |
| Parênteses balanceados | (^p)^p | 2 | Idem, com aberturas |
| \{a^nb^m : n > m\} | a^{p+1}b^p | 0 | Remover símbolos inverte a desigualdade |
| Palíndromos de tamanho par | a^pba^p | 2 | Desequilibra os blocos externos |
| Comprimento quadrado perfeito | a^{p^2} | 2 | Lacuna entre quadrados consecutivos |
| Comprimento primo | a^q com q primo maior que p+1 | q+1 | O comprimento resultante é composto |
Duas linhas dessa tabela ensinam ideias que valem além delas. A dos quadrados perfeitos é um argumento de lacuna: os quadrados ficam cada vez mais afastados uns dos outros, enquanto o bombeamento acrescenta um incremento limitado, de modo que cadeias longas caem inevitavelmente no vão entre dois quadrados consecutivos. Vale igual para potências de dois, fatoriais e qualquer sequência que cresça mais rápido do que linearmente. A dos primos mostra que o expoente também é escolha sua e pode depender de tudo o que apareceu antes — nada impede, porque o quantificador do expoente vem por último.
Antes de bombear, sempre vale perguntar se dá para transferir. Para mostrar que a linguagem das cadeias com o mesmo número de a e de b não é regular, atacá-la direto dá trabalho, porque as cadeias têm formas variadas e é fácil escolher mal. Mas a interseção dela com a regular a*b* é exatamente \{a^nb^n\}; se a primeira fosse regular, a interseção seria regular, e não é. 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
Fecho com a advertência que separa quem entendeu de quem memorizou. Existe linguagem não regular que satisfaz a propriedade de bombeamento — a clássica é a das cadeias a^ib^jc^k nas quais a igualdade entre j e k só é exigida quando i vale exatamente um. Ela passa no teste com comprimento de bombeamento dois, porque toda cadeia admite decomposição que evita o caso restrito, e mesmo assim não é regular, o que se mostra por transferência. Fracassar em bombear não demonstra que a linguagem é regular; demonstra apenas que essa ferramenta não serviu.
Você reduz a linguagem a um caso já demonstrado, intersectando-a com uma regular conveniente ou passando ao complemento. É a mais barata quando dá, e dá com frequência. Custo típico: duas ou três linhas. Requer conhecer o repertório de casos canônicos.
Demonstração por absurdo, com a alternância de quantificadores respeitada. Funciona na maioria dos casos que aparecem na prática e generaliza para classes superiores — existe um lema análogo para linguagens livres de contexto, com cinco pedaços em vez de três. Quando não fecha, o resultado é ambíguo.
Argumento direto, por contagem de classes de prefixos. É uma equivalência exata: se a linguagem não é regular, o conjunto distinguível existe e só resta encontrá-lo. Custa um pouco mais de trabalho e não generaliza para classes superiores, mas nunca falha por insuficiência da ferramenta.
1.6 Myhill-Nerode: o que é um estado, afinal
Mudo de ferramenta e de ponto de vista, e este é, na minha opinião, o ponto de vista mais esclarecedor de toda a teoria de linguagens regulares. A pergunta que o organiza é: para que serve um estado?
Pense num autômato determinístico processando uma cadeia. A certa altura ele leu um prefixo e está em algum estado. Toda a informação retida sobre aquele prefixo está ali — o prefixo em si foi esquecido, e o que sobrou dele é o rótulo do estado. Logo, se dois prefixos diferentes levarem ao mesmo estado, a máquina se comportará de forma idêntica para os dois daí em diante. Isso sugere uma pergunta que independe de autômato algum: dados dois prefixos, existe alguma continuação que os distinga, no sentido de que exatamente uma das duas cadeias completas pertence à linguagem?
Aplique a \{a^nb^n\} com os prefixos a e aa. A continuação b distingue os dois, porque ab está na linguagem e aab não está — logo nenhum autômato que reconheça essa linguagem pode levar os dois ao mesmo estado. Generalizando, para quaisquer dois expoentes diferentes existe continuação que distingue, e os prefixos formados só por a são dois a dois distinguíveis. São infinitos, os estados são finitos, e acabou.
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"]
Note que acabo de demonstrar de novo a não regularidade daquela linguagem, por um caminho completamente diferente, sem bombear nada e sem argumento por absurdo. É uma contagem direta. Formalizando: dois prefixos são equivalentes quando nenhuma continuação os distingue; essa relação particiona o conjunto de todas as cadeias em classes; e o índice da linguagem é o número dessas classes. O teorema de Myhill-Nerode — dois trabalhos independentes do fim dos anos 1950, o de John Myhill de 1957 e o de Anil Nerode de 1958 — diz que a linguagem é regular se e somente se o índice é finito, e que, quando é regular, o autômato mínimo tem exatamente tantos estados quantas são as classes.
Por que a minimização sempre encontra o mesmo autômato
Os estados do autômato mínimo são determinados pela linguagem — as classes de prefixos indistinguíveis — e não por escolhas de quem construiu; por isso dois autômatos mínimos para a mesma linguagem são iguais a menos de renomeação. Releia o refinamento de partições com esses olhos: ele parte da separação entre finais e não finais e refina até que dois estados fiquem juntos exatamente quando nenhuma continuação os distingue. Não é heurística de compressão; é um procedimento que calcula um objeto matematicamente determinado.
E aqui está a razão de ensinar as duas ferramentas em vez de só a exata. O lema dá demonstrações mais curtas quando funciona, e funciona na maioria dos casos práticos; além disso tem análogo nas classes superiores, que você usará adiante. Myhill-Nerode não generaliza, mas explica o que o lema não explica: os estados de um autômato mínimo são exatamente as distinções que a linguagem obriga a fazer, nem uma a mais, nem uma a menos. Depois que isso assenta, você deixa de projetar autômatos desenhando círculos e setas até funcionar, e passa a perguntar o que precisa ser lembrado do prefixo lido. Cada resposta é um estado. Eu mesmo demorei mais do que devia para perceber.
1.7 O limite observado no caso conduzido
Chega de quadro. Um resultado de impossibilidade apresentado só como demonstração tende a ficar guardado como fato memorizado, e não como intuição que opera; vê-lo em números medidos é o que o converte em conhecimento utilizável. O experimento tem a forma que quase todo mundo tenta antes de aceitar a teoria: já que não dá para cobrir profundidade arbitrária, cobre-se até uma profundidade escolhida, enumerando os casos. A pergunta interessante não é se funciona para aquela profundidade — funciona —, mas o que acontece na fronteira e quanto custa cada nível a mais.
1.7.1 6.1 Onde está o aninhamento na linguagem conduzida
A linguagem Peneira, que este livro constrói, tem uma única construção de profundidade arbitrária, e ela está na condição do where. Uma condição pode ser uma comparação simples, mas pode também ser uma combinação de condições ligadas por conectivos, e uma condição combinada pode ser cercada por parênteses e usada como operando de outra combinação. Não existe limite declarado para essa profundidade, e não existe porque impor um seria arbitrário: quem escreve o programa não deveria descobrir, na terceira revisão, que o quarto nível de parênteses é o último aceito.
Tudo o mais na linguagem é regular e já está resolvido. Nomes, números, cadeias de texto, literais de padrão e os sinais de pontuação são descritos por expressões regulares, e o motor construído até aqui os reconhece. A condição composta é a única parte que escapa, e escapa por uma razão que agora você sabe enunciar: reconhecê-la exige lembrar quantos parênteses foram abertos e ainda não foram fechados, e essa contagem não tem cota superior.
Reduzida ao essencial, a construção é a linguagem dos parênteses balanceados, que a Seção 4 já demonstrou não ser regular. A demonstração feita lá, sobre um objeto matemático abstrato, é literalmente a demonstração sobre esta linguagem: não há passo adicional a dar, apenas o reconhecimento de que a mesma estrutura está presente.
1.7.2 6.2 As construções de fechamento, implementadas
As propriedades de fechamento da Seção 1 não ficaram na prosa. O caso conduzido as implementa como operações sobre autômatos finitos determinísticos, e a razão de implementá-las antes do lema do bombeamento — e não depois — é a que a Seção 1.6 defendeu: elas são instrumento de demonstração.
A interface declara as cinco operações e as duas funções auxiliares que as tornam utilizáveis.
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_H
Repare no que a assinatura de cada operação exige: o alfabeto vem como parâmetro explícito, e não é inferido dos símbolos que o autômato já usa. Essa é a tradução, em código, da advertência da Seção 1.3. Um complemento calculado sobre alfabeto inferido sairia correto para os símbolos presentes e errado para todos os demais, sem que nenhum teste construído sobre o alfabeto original percebesse. Deixar o parâmetro obrigatório na assinatura força quem chama a tomar a decisão conscientemente.
A implementação exibe as duas escolhas de projeto que discuti em abstrato.
06_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 peneira
A primeira é que união e interseção são o mesmo código. As duas são a construção do produto da Seção 1.4, e diferem em uma única decisão: o par é final quando os dois componentes são finais, ou quando qualquer um é. Escrevi a construção uma vez, com um predicado como parâmetro. Duplicá-la seria convidar as duas cópias a divergirem na primeira correção que uma delas recebesse.
A segunda é que só os pares alcançáveis nascem. A definição da Seção 1.4 fala do produto cartesiano completo, com |Q_1| \times |Q_2| estados, mas construir o autômato por percurso a partir do par inicial cria apenas os pares que a máquina realmente atinge. Um autômato de três estados intersectado com um de dois resulta, nos exemplos deste capítulo, em três estados e não em seis. A definição é a especificação; a construção por percurso é a implementação que a respeita gastando menos.
A demonstração executável confere as quatro operações contra as definições, cadeia por cadeia, em vez de contra uma tabela de resultados esperados escrita à mão. A diferença importa: uma tabela escrita por mim carregaria exatamente os mesmos mal-entendidos que a implementação, se eu tivesse entendido a operação errado, e os dois erros se cancelariam em silêncio. Calculando o que a definição exige a partir dos autômatos originais e comparando com o que a construção produziu, o teste vira confronto entre duas fontes independentes.
O que isso destrava, no caso conduzido, é o que a Seção 1.5 antecipou: com a diferença e o teste de linguagem vazia disponíveis, o projeto passa a decidir inclusão entre linguagens. Essa capacidade parece ociosa agora e não é — quando a verificação de tipos precisar decidir se um padrão declarado pelo usuário reconhece somente números, a pergunta que ela fará é exatamente a de inclusão, e a resposta virá dessas duas funções.
1.7.3 6.3 O lema do bombeamento, exibido rodando
Sobre uma linguagem que é regular, a decomposição que o lema garante existir pode ser encontrada mecanicamente, e vê-la funcionando antes de usá-la para derivar contradição muda a relação com o enunciado. Quem viu a decomposição sair acredita nela depois.
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_H
06_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 peneira
O código é a demonstração da Seção 3.2 transcrita, e vale acompanhar a correspondência linha a linha. A cadeia é percorrida anotando o estado alcançado após cada prefixo, o que produz a sequência de estados r_0, r_1, \dots da demonstração. A busca pela repetição para no número de estados do autômato, e não segue pela cadeia inteira — é isso que garante a condição |xy| \le n. Deixar o laço correr até o fim encontraria repetições legítimas, produziria um y não vazio e violaria a terceira condição do lema, dando uma decomposição que não é a que o lema promete.
Rodando sobre o autômato do número, que tem cinco estados, com a cadeia 123456, a decomposição encontrada é x = 1, y = 2, z = 3456, com o estado repetido alcançado após um e após dois símbolos. As três condições podem ser conferidas na saída: o y tem comprimento um, portanto não é vazio; o comprimento de xy é dois, dentro dos cinco estados; e todas as potências de zero a cinco são aceitas, inclusive a de expoente zero, que remove o trecho e produz 13456.
Há uma assimetria no código que quero que você note, porque ela é a estrutura lógica da Seção 3.3 materializada. A função de decomposição encontra a decomposição; ela não a recebe como parâmetro. Isso não é conveniência de interface — é fidelidade ao enunciado. No lema, quem fornece a decomposição é o autômato, não quem demonstra. Uma função que recebesse x, y e z de fora estaria modelando o erro que a Seção 3.3 descreveu como dominante.
1.7.4 6.4 O experimento: a ferramenta diante do aninhamento
A parte final é o confronto direto entre o motor construído e a construção aninhada, e ele reproduz o que quase todo mundo tenta 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 os casos até k.
O gerador dessa expressão está no cabeçalho acima, e a demonstração roda o pipeline completo — notação, autômato não determinístico, determinização, minimização — sobre a expressão gerada, para k de um a oito. Os números medidos:
| Profundidade coberta | Estados do autômato mínimo | Aceita profundidade k | Aceita profundidade k+1 |
|---|---|---|---|
| 1 | 3 | sim | não |
| 2 | 5 | sim | não |
| 3 | 7 | sim | não |
| 4 | 9 | sim | não |
| 5 | 11 | sim | não |
| 6 | 13 | sim | não |
| 7 | 15 | sim | não |
| 8 | 17 | sim | não |
Trê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 caçar, e essa constatação precisa vir antes de qualquer outra, porque a suspeita natural de quem vê a falha é a de que o próprio código está errado.
A segunda é o crescimento. Os estados seguem 2k + 1, linear na profundidade coberta. Cada nível a mais custa dois estados, o que é a memória do autômato sendo gasta para contar. Confronte esse número com a Seção 5: são exatamente as classes de equivalência de Myhill-Nerode que precisam ser distinguidas, uma por profundidade, mais as classes dos sufixos. O autômato mínimo não pode ter menos estados do que classes a separar, e a contagem medida confirma o teorema em vez de apenas ilustrá-lo.
A terceira é a coluna da direita, e é a resposta. Sempre falha em k+1. Como para todo k existe k+1, nenhum valor resolve. O autômato precisaria de infinitos estados, e a expressão “autômato finito com infinitos estados” é contradição em termos.
Aviso
O que o experimento prova, e o que não prova. Ele não prova nada, e é importante ser explícito quanto a isso. Mostrar que oito tentativas falharam não exclui a nona; sempre resta a hipótese de que exista uma expressão mais 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. 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á, para toda expressão, em toda implementação, com qualquer quantidade de memória. Ter apenas um dos dois é ter metade do argumento.
O erro de leitura que essa tabela convida, e contra o qual quero prevenir você, é concluir 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, não é uma restrição da notação adotada, não é uma escolha de representação que pudesse ser trocada por outra mais folgada. É do modelo, e é por isso que este capítulo precisou de uma demonstração e não de um perfilamento.
1.7.5 6.5 A consequência para o resto da construção
Fecho registrando a divisão de trabalho que este capítulo estabelece para todo o resto do livro, porque ela é o produto concreto do resultado teórico.
O analisador léxico, que vem a seguir, fica com o que é regular — e é só isso que ele consegue fazer. Nomes, números, textos, literais de padrão, pontuação: tudo descrito por expressões regulares, tudo reconhecido pelo motor pronto, tudo em tempo linear com uma passada e sem retrocesso. A estrutura aninhada não entra nessa fase, e não entra por impossibilidade demonstrada, não por convenção de arquitetura.
Ela sobe para a análise sintática, que precisa de um modelo com memória de profundidade arbitrária. Esse modelo é o autômato de pilha, e a pilha é exatamente o dispositivo que falta ao autômato finito: um lugar onde a contagem de aberturas pendentes pode crescer sem cota. O capítulo seguinte ao próximo apresenta a classe de linguagens que esse modelo alcança, e o capítulo depois dele a máquina.
Há ainda um efeito de projeto que este resultado produz e que costuma passar despercebido. A decisão sobre a forma dos comentários da linguagem conduzida — comentário de linha, iniciado por um marcador e terminado no fim da linha, em vez de comentário de bloco aninhável — é consequência direta deste capítulo. Um comentário de bloco que possa conter outro comentário de bloco exige contar profundidade, e contar profundidade é precisamente o que o analisador léxico não pode fazer. Essa é a primeira vez, na construção inteira, em que um resultado de impossibilidade decide uma característica visível da linguagem, e não vai ser a última.
1.8 Síntese
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. O complemento exige autômato determinístico e completo, e esquecer a completude produz um autômato bem formado que reconhece a linguagem errada — erro silencioso, do tipo que atravessa testes. União e interseção são a mesma construção do produto com predicados de finalidade diferentes. E a diferença, somada ao teste de linguagem vazia, torna decidíveis a inclusão e a equivalência, capacidade que a classe imediatamente superior não oferece.
O resultado central nasce da observação mais simples possível: uma máquina com n estados, ao ler uma cadeia com pelo menos n símbolos, repete estado obrigatoriamente, e o trecho entre as duas passagens é um ciclo que pode ser percorrido qualquer número de vezes sem que ela perceba diferença. O lema do bombeamento é essa observação com duas amarrações: a ordem em que as quantidades são escolhidas, e a condição de localização. Você escolhe a cadeia e o expoente; o adversário escolhe o comprimento e a decomposição. Trocar essa ordem produz uma prova errada — e o perigo mora aí, porque uma prova errada que chega à conclusão certa não é corrigida por quem só confere o resultado.
O lema é condição necessária e não suficiente, e existe linguagem não regular que passa no teste. Myhill-Nerode fecha essa lacuna por ser uma equivalência exata, e faz mais: explica o que é um estado.
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
Volto, para fechar, aos parênteses da abertura. Você não conseguiu escrever aquela expressão regular, e agora sabe demonstrar que ninguém conseguirá — não por limitação da notação, do seu talento ou da máquina, mas do modelo. O que isso entrega ao resto do curso é uma divisão de trabalho justificada: tudo o que é regular fica com o analisador léxico, em uma passada e sem retrocesso; tudo o que é aninhado sobe para uma fase que dispõe de um modelo mais forte. Esse modelo é o autômato de pilha, e a pilha é exatamente o dispositivo que faltou aqui — uma memória cuja profundidade não tem cota. Quando você chegar lá, vai reconhecer que ela não foi acrescentada por conveniência de implementação. Foi acrescentada porque este módulo demonstrou que sem ela não há saída.
E se ficou o desconforto de gastar um módulo inteiro concluindo que algo não pode ser feito, ofereço outra leitura: saber com precisão onde uma ferramenta para é o que permite usá-la com confiança onde ela funciona. Engenharia madura não se distingue pela quantidade de técnicas conhecidas, mas pela clareza sobre o limite de cada uma.