1 Expressões regulares e linguagens regulares — Resolução dos Exercícios
Documento exclusivo do professor. Não o entregue à turma nem o registre em perfil de estudante. Os três problemas foram armados para que o erro apareça no papel antes de a correção chegar, e quem lê o gabarito antes de tentar sai da folha sem ter errado nada — prejuízo que se disfarça de economia. Em cada exercício as orientações vêm antes do gabarito, na ordem da condução em sala e não na da conferência.
A folha deste módulo tem uma característica que a do anterior não tinha: dois dos três problemas terminam num número, e números discordam entre si de um jeito que impressões não conseguem. O primeiro pede cinco conjuntos escritos por extenso, com a cardinalidade ao lado de cada um, e mede se o estudante já separa a expressão do conjunto que ela denota. O segundo pede uma conta de três parcelas sobre um padrão de nove caracteres. O terceiro não tem conta alguma até a letra (b), e é onde a classificação de quatro exigências reais é feita pela memória que a máquina precisaria ter.
Uma advertência de método antes de tudo, e ela governa a correção inteira. Em boa parte da folha o estudante chega ao resultado certo por um caminho que a folha não registra, e você só descobre qual foi perguntando em voz alta. Pergunte sempre, inclusive a quem acertou — sobretudo a quem acertou depressa e sem rasura.
O exercício 2 tem uma peça que depende de você e some se a aula correr apertada: o palpite escrito antes da conta. O enunciado manda escrever o número no papel antes de calcular qualquer coisa, e a distância entre esse número e o total é o conteúdo do item. Sem o palpite registrado, a conta vira aritmética sem consequência, e o estudante soma vinte e dois nós com a mesma serenidade com que somaria doze. Circule pelas carteiras nos primeiros três minutos e confira que há um número escrito num canto de cada folha. É a única fiscalização de processo que vale a pena fazer no módulo.
Reserve para o exercício 3 mais tempo do que para os dois primeiros somados, e conduza a letra (a) com a turma inteira falando. A quarta exigência dele é o ponto em que a teoria arbitra uma decisão de engenharia cuja conta é paga por quem está fora do sistema — a pessoa que espera na fila de leitura humana, que não trabalha no serviço e nunca escreveu padrão nenhum.
1.1 Resolução do Exercício 1: cinco expressões, cinco conjuntos
Nível básico
1.1.1 Orientações Pedagógicas para o Professor
Abra pedindo apenas as cinco cardinalidades, de cabeça, antes de qualquer conjunto escrito, e anote no quadro os cinco números que a turma disser. O que interessa está nas três primeiras posições: quantos disseram zero para \emptyset, quantos disseram zero para \varepsilon, e quantos disseram zero para \emptyset^*. A sequência correta é 0, 1, 1, 0, 2, e a turma que responde 0, 0, 0, 0, 2 está inteira dentro da mesma confusão, com uma palavra só — “vazio” — para duas coisas diferentes. Ter os dois números lado a lado no quadro rende mais que qualquer explicação sobre a cadeia vazia.
A resposta errada que vence o primeiro voto com folga é a de \emptyset^*, e o argumento dela parece impecável: o fecho de um conjunto sem elementos não tem o que produzir, logo L(\emptyset^*) = \emptyset. Quem raciocina assim aplicou ao fecho a intuição correta sobre a concatenação, onde o conjunto vazio de fato aniquila. A intervenção é a definição, e ela cabe numa linha do quadro: o fecho reúne as potências a partir da de expoente zero, e a potência de expoente zero é \{\varepsilon\} para qualquer linguagem, inclusive a vazia. Escreva a reunião com os três primeiros termos à vista e deixe o estudante ver o \{\varepsilon\} entrar sozinho no primeiro deles.
A segunda resposta errada sobre a mesma expressão vem de outro lugar e pede outra intervenção: L(\emptyset^*) é a linguagem de todas as cadeias do alfabeto. Quem marca isto leu o asterisco como “qualquer coisa”, que é o significado que ele tem num campo de busca de arquivos e não nesta notação. Corrigir a definição desta pessoa resolve pouco, porque a definição que ela usou tem outra origem: veio de fora, chegou antes, e ninguém pediu para desinstalá-la. Pergunte a ela sobre qual conjunto o fecho foi aplicado, e depois o que aconteceria se a expressão fosse b^* sobre um alfabeto com dez símbolos.
A terceira, mais rara e mais fácil de corrigir, é “a expressão é malformada, porque não se aplica fecho ao conjunto vazio”. Ela aplica à notação uma restrição que a definição não faz: a cláusula de composição vale para toda expressão regular, sem exigir que o operando denote conjunto habitado. Se essa resposta passar de dois ou três estudantes, releia a definição de expressão regular no quadro antes de seguir; o exercício 2 inteiro se apoia nela.
Em \emptyset a o erro é de outra família e não tem nada de vocabular. O estudante escreve \{a\}, e o que ele fez foi tratar o \emptyset como elemento neutro da concatenação. Essa troca é a que custa mais caro fora da folha: quem a leva para dentro de um analisador produz um sistema que rejeita tudo, e o sintoma aparece longe da linha responsável. Devolva pela definição de concatenação de linguagens, que é a pergunta que o próprio enunciado já sugeriu — quantos pares uv se formam quando um dos dois conjuntos não tem nenhum candidato a oferecer.
Agora o ponto que exige atenção na hora de corrigir, e que a fala do enunciado não prevê. Existem dois pares que denotam o mesmo conjunto, e não um: r_1 com r_4, os dois denotando \emptyset, e r_2 com r_3, os dois denotando \{\varepsilon\}. O estudante que encontra apenas um dos dois pares não errou nada; ele parou no primeiro. Trate a folha que traz os dois como resposta completa e leia-a em voz alta. E use a diferença entre as duas descobertas como diagnóstico: quem achou só r_2 com r_3 estava atento ao símbolo e distraído da operação; quem achou só r_1 com r_4 fez a conta da concatenação e leu \emptyset^* depressa demais.
Na letra (b) quase todo mundo escreve os dois conjuntos certos, e o discriminador está na leitura da árvore. O erro previsível é responder qual das duas expressões a figura representa olhando para a quantidade de nós, ou procurando na figura o parêntese que o texto tinha. O parêntese não deixa marca: ele não vira nó, não vira folha e desaparece na leitura. Peça a justificativa pela posição relativa dos dois operadores, e nada mais — quem está na raiz e quem está abaixo de quem.
Na letra (c) o tropeço é de explicação, e ele se esconde atrás de uma resposta certa. O estudante lista os quatro elementos de cada conjunto sem dificuldade, aponta \varepsilon como a cadeia que separa os dois, e então explica o conjunto infinito dizendo que “o asterisco permite repetir quantas vezes quiser”. Essa frase descreve o comportamento de um usuário digitando, e o que se pediu foi a semântica de um operador. Devolva pedindo a reunião escrita: qual é a primeira potência, qual é a segunda, e onde a reunião pararia se ela parasse. O próprio enunciado já traz o teste que separa a boa explicação da fraca — uma explicação que serve igualmente bem para uma lista de mil cadeias escritas à mão ainda não separou o tamanho do texto do tamanho do conjunto.
Sobre a devolutiva escrita. Uma boa resposta neste exercício escreve os cinco conjuntos por extenso mesmo achando o pedido óbvio, põe a cardinalidade ao lado de cada um, e em (b) justifica pela forma da árvore sem recorrer ao texto que a originou. Uma resposta parcial típica acerta as cinco cardinalidades, acerta o par r_1 com r_4 e erra \emptyset^*: ela mostra alguém que já domina a concatenação e ainda não separou o fecho dela. A orientação para essa pessoa é uma tarefa de três linhas, e não uma explicação — escreva L^0, L^1 e L^2 para L = \emptyset, uma linha cada, e diga qual delas contribui com elemento para a reunião. Quem errou (c) por explicar o infinito com “quantas vezes quiser” tem outra fragilidade, e a tarefa dele é outra: escrever a reunião das potências de \{a\} até a quarta e dizer, em uma frase, por que ela não termina.
1.1.2 Resolução Modelo
(a) As cinco linguagens, por extenso, com a cardinalidade e a razão de cada uma.
L(r_1) = L(\emptyset) = \emptyset \qquad |L(r_1)| = 0
A cláusula da definição atribui a \emptyset o conjunto sem cadeia alguma. Nada a listar entre as chaves.
L(r_2) = L(\varepsilon) = \{\varepsilon\} \qquad |L(r_2)| = 1
A cláusula atribui a \varepsilon o conjunto cujo único elemento é a cadeia de comprimento zero. O conjunto tem um habitante, e esse habitante não tem símbolo nenhum dentro.
L(r_3) = L(\emptyset^*) = L(\emptyset)^* = \bigcup_{i \geq 0} \emptyset^i = \{\varepsilon\} \cup \emptyset \cup \emptyset \cup \cdots = \{\varepsilon\} \qquad |L(r_3)| = 1
A reunião começa no expoente zero, e a potência de expoente zero de qualquer linguagem é \{\varepsilon\} — inclusive a da linguagem vazia. Todas as potências seguintes são vazias e nada acrescentam. Sobra o primeiro termo.
L(r_4) = L(\emptyset a) = L(\emptyset)\,L(a) = \emptyset\,\{a\} = \emptyset \qquad |L(r_4)| = 0
A concatenação de linguagens forma a cadeia uv para cada u da primeira e cada v da segunda. Não existe u a escolher, de modo que nenhum par se forma e nenhuma cadeia entra no resultado. O conjunto vazio aniquila na concatenação; quem é neutro é \{\varepsilon\}.
L(r_5) = L(a \mid \varepsilon) = L(a) \cup L(\varepsilon) = \{a\} \cup \{\varepsilon\} = \{\varepsilon,\ a\} \qquad |L(r_5)| = 2
Os pares que denotam o mesmo conjunto são dois. As expressões r_1 e r_4 denotam ambas \emptyset; as expressões r_2 e r_3 denotam ambas \{\varepsilon\}. A igualdade é entre os conjuntos denotados, e não entre os textos: \emptyset e \emptyset a são cadeias de caracteres diferentes, construídas por cláusulas diferentes da definição, e produzem estruturas diferentes quando lidas — o que elas têm em comum é o valor que a semântica lhes atribui, que é o mesmo conjunto. Duas expressões são equivalentes quando as linguagens denotadas coincidem, e nada além disso é exigido delas.
(b) As duas expressões e os dois conjuntos.
L(a \mid bc) = \{a,\ bc\} \qquad L((a \mid b)c) = \{ac,\ bc\}
A cadeia a pertence à primeira e não pertence à segunda; a cadeia ac pertence à segunda e não pertence à primeira. Qualquer uma das duas serve como testemunha da diferença.
A regra que produz a diferença é a precedência entre alternância e concatenação: a concatenação liga mais forte que a alternância. Sem parênteses, a \mid bc se lê como a \mid (bc), com a alternância na raiz e a concatenação abaixo dela. O parêntese em (a \mid b)c inverte essa ordem, forçando a alternância a ser resolvida primeiro para servir de operando esquerdo da concatenação.
A árvore da figura é a de (a \mid b)c. A justificativa está na posição relativa dos dois operadores: a raiz aplica a concatenação e tem a alternância como filha esquerda. Uma leitura livre de parênteses jamais produziria essa forma, porque a precedência põe a alternância acima da concatenação — a alternância só desce para baixo dela quando um agrupamento a força. O parêntese que provocou a inversão não aparece na figura, e não apareceria: ele não vira nó, não vira folha e não deixa marca. O que ele deixou foi a ordem em que os dois operadores se aninham, que é precisamente o que a árvore registra.
(c) Os quatro primeiros elementos de cada conjunto, em ordem crescente de comprimento.
L(a^*) : \varepsilon,\ a,\ aa,\ aaa \qquad L(a^+) : a,\ aa,\ aaa,\ aaaa
A cadeia que está numa e não está na outra é \varepsilon. Ela pertence a L(a^*) porque o fecho reúne as potências a partir da de expoente zero, e não pertence a L(a^+), cuja reunião começa no expoente um.
Duas posições escritas no papel denotam um conjunto infinito porque o operador de fecho não descreve cadeias, e sim uma reunião indexada por todos os expoentes naturais: L(a^*) = \bigcup_{i \geq 0} \{a\}^i. O texto tem tamanho fixo porque enuncia a regra de formação; o conjunto tem tamanho ilimitado porque a regra se aplica sem teto. É a mesma economia de uma progressão aritmética escrita em três símbolos e válida para infinitos termos.
Daí resulta que “expressão curta denota linguagem pequena” é falsa, e falsa da maneira mais direta possível: a^* ocupa duas posições e denota conjunto infinito, enquanto \emptyset a ocupa duas posições e denota conjunto vazio. Duas expressões do mesmo tamanho, cardinalidades nos dois extremos. Tamanho do texto e tamanho da linguagem denotada são grandezas independentes, e a única maneira de conhecer a segunda é aplicar a semântica.
Fecha o exercício a comparação entre \emptyset e \emptyset^*, que denotam conjuntos de cardinalidades diferentes embora o segundo se construa a partir do primeiro. O fecho preserva pouco do tamanho do operando: ele acrescenta, por definição, a potência de expoente zero, e essa potência traz \{\varepsilon\} mesmo quando não há nada a repetir. Um conjunto de zero elementos passa a um de um elemento, e o elemento acrescentado é justamente aquele que não exige nenhum símbolo do operando.
1.2 Resolução do Exercício 2: o preço da conveniência, em nós
Nível intermediário
1.2.1 Orientações Pedagógicas para o Professor
Comece pelos palpites, no quadro, antes de qualquer conta. Peça em voz alta o número que cada um escreveu para ([a-e]+)? e anote quatro ou cinco deles. O que costuma aparecer fica entre oito e doze, e a razão é aritmeticamente inocente: o estudante contou os caracteres do padrão, tirou os dois parênteses e os dois operadores, e chegou a algo próximo do tamanho do texto. O total é 22. Deixe os palpites escritos no quadro durante a conta inteira e escreva o 22 ao lado deles quando a soma fechar. A distância é o resultado que interessa ali, e ela desaparece se a conta vier primeiro.
Nove caracteres entram e vinte e dois nós saem, sem que ninguém tenha digitado nada a mais. Essa é a frase que a turma leva do exercício, e ela só funciona com os dois números à vista.
A exigência de somar apenas depois de ter as três parcelas separadas parece burocracia e tem função. Quem soma direto acerta o total com frequência razoável e não consegue dizer onde o dinheiro foi gasto, o que inutiliza a letra (b) — a fórmula geral se escreve olhando as três parcelas, e quem tem só o 22 não tem de onde tirá-la. Exija as três, e recuse a folha que traz o total sozinho.
O erro estrutural deste exercício é o compartilhamento da subárvore no lugar da clonagem, e o que o torna caro é o sintoma numérico invertido. O estudante que aponta a mesma subárvore da faixa duas vezes, em vez de cloná-la, chega a 13 nós, e treze parece bom: é menor, é econômico, e ele acha que otimizou. A folha dele não traz nenhuma marca de erro — traz um número menor que o do colega, e ele defende esse número com o vocabulário certo. É por isso que o palpite escrito antes importa tanto: sem ele, não há com o que comparar a queda.
A devolutiva para esse caminho é em dois tempos, e o primeiro tempo não é uma correção. Peça a contagem que ele obteve e a contagem do colega ao lado, lado a lado no papel dele. Só então faça a pergunta operacional: o que acontece quando alguma coisa percorrer essa estrutura a partir da raiz? Dois pais apontando o mesmo filho fazem um grafo, e um percurso a partir da raiz passa duas vezes pelo mesmo trecho, ligando ao mesmo pedaço de máquina o que deveriam ser duas passagens distintas. A economia de treze nós compra uma máquina errada. Não antecipe a construção que percorrerá essa árvore; ela é assunto dos capítulos seguintes, e a pergunta funciona melhor sem a resposta.
Um segundo caminho errado, mais silencioso, aparece na parcela do opcional. O estudante escreve que x? acrescenta um nó, contando a alternância e esquecendo a folha da cadeia vazia. O total dele sai 21, e o erro fica invisível na soma. Ele se pega perguntando quantos filhos a alternância tem e onde mora o segundo. A concepção por baixo é a mesma do exercício 1 na sua forma mais teimosa: a cadeia vazia lida como ausência, quando ela é um elemento que ocupa lugar. Quem erra aqui e errou a cardinalidade de \varepsilon na folha anterior tem um problema só, e vale corrigir os dois de uma vez.
Na letra (b), o tropeço é confundir a fórmula da faixa com a fórmula do padrão inteiro. Aparece f(k) = 2k-1, que é a conta da faixa isolada e ignora as duas reduções empilhadas sobre ela. A verificação está prescrita no enunciado e o estudante consegue fazê-la sozinho: avaliada em k = 5, a fórmula precisa devolver o total já calculado à mão. Fórmula que não reproduz o caso pequeno está errada, e essa é a única correção que ele precisa ouvir de você.
Na letra (c) há uma pergunta cuja resposta discrimina de verdade, e é a última: qual dos dois fatores é o perigoso. Quem responde “os dois” está evitando decidir. O produto n(2k-1) tem n sob controle de quem escreve o padrão, e k limitado pelo alfabeto; é o n que alguém pode aumentar livremente numa linha de configuração, e é por ele que se pergunta antes de aceitar uma notação com quantificador contado sem teto declarado. Se ninguém na sala chegar lá, ponha o número no quadro: avalie a expressão geral para k = 26 e n = 100 e deixe o resultado falar.
Sobre a devolutiva escrita. Uma boa resposta traz o palpite registrado, as três parcelas separadas com o que cada uma mede, a fórmula conferida em k = 5 antes de ser avaliada em k = 26, e uma frase final que separa o tamanho da árvore do tamanho da linguagem denotada — porque a árvore cresceu e a linguagem continua sendo a mesma. Uma resposta parcial típica acerta as parcelas e a fórmula, avalia tudo corretamente e fecha dizendo que a redução “deixa o sistema mais lento”: a fragilidade é ter trocado a grandeza medida por outra que ninguém mediu neste módulo. A orientação para essa pessoa cabe numa pergunta escrita na margem — qual conjunto de cadeias ([a-e]+)? denota antes da redução, e qual ele denota depois. Quem compartilhou a subárvore precisa de outra tarefa, e ela é de desenho: refaça a árvore com a subárvore clonada, numere os nós de 1 a 22, e diga quais números um percurso a partir da raiz visitaria duas vezes na versão compartilhada.
1.2.2 Resolução Modelo
(a) As três parcelas do padrão ([a-e]+)?, medidas uma a uma, na ordem em que as reduções se aplicam.
Primeira parcela — a faixa. [a-e] reduz à enumeração [abcde], e essa à alternância dos cinco símbolos. São 5 folhas, uma por símbolo, e 4 nós de alternância, porque cada alternância binária junta dois operandos e são precisos quatro passos para reunir cinco. A subárvore da faixa custa
5 + 4 = 9 \text{ nós.}
Segunda parcela — o fecho positivo. x+ reduz a xx*, isto é, a concat(x, fecho(x)). Sobre a subárvore já medida, isso acrescenta: uma cópia clonada da faixa, que custa outros 9 nós; um nó de fecho, que aplica o operador à cópia; e um nó de concatenação, que junta o original à cópia sob fecho. O acréscimo é
9 + 1 + 1 = 11 \text{ nós.}
A cópia é clonada, e o mesmo filho jamais é apontado por dois pais. Dois pais apontando o mesmo filho produzem um grafo, e a estrutura que a leitura precisa entregar é uma árvore.
Terceira parcela — o opcional. x? reduz à alternância entre x e a cadeia vazia. Sobre o resultado do passo anterior, isso acrescenta a folha da cadeia vazia e o nó de alternância que a junta ao operando. O acréscimo é
1 + 1 = 2 \text{ nós.}
O parêntese de agrupamento reduz a nada e não entra em nenhuma parcela.
O total, somando as três parcelas e só agora:
9 + 11 + 2 = 22 \text{ nós, para 9 caracteres digitados.}
(b) A forma geral. Com k símbolos na faixa, a subárvore da faixa tem k folhas e k-1 alternâncias, isto é, 2k-1 nós. O fecho positivo acrescenta uma cópia dela mais dois nós, ou 2k+1. O opcional acrescenta dois. Somando:
f(k) = (2k-1) + (2k-1) + 2 + 2 = 4k + 2 .
A conferência em k = 5 devolve f(5) = 22, que é o total obtido à mão. Avaliada na faixa das letras minúsculas:
f(26) = 4 \cdot 26 + 2 = 106 \text{ nós, para os mesmos 9 caracteres digitados.}
A fórmula é linear em k, com coeficiente 4: cada símbolo acrescentado à faixa custa quatro nós, porque a faixa aparece duas vezes na árvore e cada aparição cobra dois nós por símbolo. Quem digita nove caracteres esperando pagar nove está pagando cento e seis, e a razão do fator não está escondida em lugar nenhum — está nas três reduções, cada uma com o seu preço declarado. O coeficiente é constante, de modo que a conta é previsível e se refaz para qualquer faixa antes de a expressão ser escrita.
(c) A remedida com quantificador contado. [a-e]{3} reduz a três cópias da faixa concatenadas em sequência: três subárvores de 2k-1 nós cada, ligadas por dois nós de concatenação. Logo
g(k) = 3(2k-1) + 2 = 6k - 1 .
Avaliada na mesma faixa das minúsculas:
g(26) = 6 \cdot 26 - 1 = 155 \text{ nós.}
Comparando com f(26) = 106: a forma contada custa cerca de metade a mais, e a razão é estrutural. O fecho positivo duplica a faixa uma vez e apenas uma, quaisquer que sejam as repetições que ele venha a autorizar em tempo de reconhecimento; o quantificador contado replica a faixa uma vez por cópia pedida, e o número de cópias está escrito no padrão.
Generalizando para n cópias da faixa de k símbolos:
h(n, k) = n(2k-1) + (n-1) .
Dois termos, e eles se comportam de maneira diferente. O primeiro é um produto: o custo da faixa multiplicado pelo número de cópias. O segundo é uma soma: os nós de concatenação que ligam as cópias, um a menos que o número delas. Dos dois fatores do produto, k tem teto — está limitado pelo tamanho do alfabeto, e ninguém escreve uma faixa maior que ele. Já n não tem teto algum, e é o fator escrito por quem edita a linha de configuração. Com k = 26 e n = 100, a expressão devolve 100 \cdot 51 + 99 = 5199 nós a partir de um punhado de caracteres. O perigoso é n, porque ele multiplica e porque está sob controle de quem digita.
Fecha a conta a leitura que ela sustenta, e ela precisa ser dita com o cuidado de não trocar a grandeza. O que cresceu foi a árvore, medida em nós. A linguagem denotada manteve o tamanho que tinha: ([a-e]+)? denota exatamente o mesmo conjunto de cadeias antes e depois da redução, porque a redução troca a escrita da expressão e preserva a semântica. Nenhum tempo de execução foi medido aqui, e nenhuma cadeia entrou ou saiu do conjunto. A árvore ficou muitas vezes maior que o texto porque a conveniência de quem escreve o padrão tem um preço, e o preço se paga na estrutura que a leitura entrega à peça seguinte — que só conhece as cláusulas do núcleo e nada mais.
1.3 Resolução do Exercício 3: quatro exigências, uma notação de triagem
Nível desafiador
1.3.1 Orientações Pedagógicas para o Professor
Este é o problema que separa a turma, e a separação acontece na letra (a), na quarta exigência. Conduza-a com todo mundo falando, e conduza-a por último — deixe a primeira, a segunda e a terceira serem classificadas rápido, porque elas vão ser, e reserve o tempo para a quarta.
A quarta exigência é lida como a mais simples das quatro, e está mais alto na hierarquia que qualquer uma das outras três. Peça a classificação a mão levantada antes de qualquer justificativa e você verá a sala dividida ao contrário do que deveria: muita gente pondo a terceira acima da quarta, porque a terceira “tem parênteses aninhados, que é aquele caso” e a quarta “é só procurar duas vezes a mesma coisa”. A concepção por baixo é sempre a mesma, e é a que atravessa o módulo inteiro — o estudante classifica pela aparência do padrão que alguém escreveria, e não pela memória que a máquina reconhecedora precisaria ter.
A devolutiva é a pergunta que o percurso vem repetindo desde o módulo anterior, e ela funciona melhor sem enfeite: o que essa máquina precisaria lembrar para decidir? Na terceira exigência, um número — quantas aberturas continuam pendentes. Na quarta, um bloco inteiro de texto, guardado até o fim da mensagem, para conferir se ele reaparece. Um número sem teto já sai da classe regular; um bloco sem tamanho limitado sai também da seguinte. Ponha as duas respostas lado a lado no quadro e a hierarquia se ordena sozinha.
O discriminador do item é a pergunta da pilha, e ela existe porque o estudante que aceitou a classificação da quarta ainda vai propor a pilha como solução — afinal, foi a pilha que resolveu os parênteses. Conduza como experimento de quadro, sem enunciar nada. Empilhe A, B, 1, 2, nessa ordem, escrevendo a pilha em pé no quadro. Depois desempilhe, escrevendo o que sai: 2, 1, B, A. A pilha devolveu 21BA diante de AB12, e a sala vê que ela guarda o espelho. É por isso que a pilha casa aberturas com fechamentos, que se leem em ordem inversa, e não casa um código com a segunda ocorrência dele, que se lê na mesma ordem. O argumento se encerra sem que você precise enunciar nada.
Se alguém pedir a demonstração formal de que a repetição de um bloco arbitrário está fora da classe livre de contexto, diga que o resultado está estabelecido — Hopcroft, Motwani e Ullman o registram — e que a demonstração usa uma ferramenta que este percurso ainda não tem. Prometer a demonstração para depois custa menos que improvisá-la, e improvisá-la agora exigiria um instrumento que a turma vai construir mais adiante.
A última parte da letra (a) tem uma sutileza que vale você conhecer antes de entrar na sala, porque um estudante atento vai encontrá-la. O enunciado pergunta o que mudaria se o conjunto de códigos válidos fosse finito e conhecido de antemão — e a primeira exigência já fixa o formato do código em duas letras e seis dígitos, o que torna esse conjunto finito desde sempre. A resposta honesta reconhece as duas leituras e diz o que muda em cada uma, e o gabarito abaixo a escreve por extenso. Se ninguém levantar o ponto, deixe-o quieto; se alguém levantar, pare tudo e conduza, porque ali está a lição mais valiosa do exercício — a classe pode dizer “sim” a uma exigência que nenhuma engenharia consegue construir.
Na letra (b) o erro previsível é escrever as duas contas com os mesmos fatores e não perceber que uma delas se paga uma vez e a outra se paga todo dia. Peça a unidade ao lado do símbolo: custo por partida do serviço, custo por dia. Com a unidade escrita, o estudante vê sozinho qual dos dois fatores está fora do controle de quem opera. O segundo tropeço é responder à pergunta da medição com “medir o desempenho”, que nomeia uma categoria e não uma grandeza. Exija a grandeza nomeada, e recuse a resposta que não diga o que se põe na balança.
A letra (c) tem um caminho errado que chega à decisão certa pelo motivo errado, e ele é o mais frequente de todos. O estudante escolhe a segunda biblioteca porque “a primeira é mais lenta”. A recusa dele se sustenta em desempenho suposto, e o enunciado já avisa que isso deixa faltando o passo que a letra (a) deu. Devolva com a pergunta: em que entradas a primeira é mais lenta, e como ele saberia disso antes de encontrá-las. A resposta que o item quer trata da garantia que se tem antes de a entrada existir, e não da velocidade média.
O segundo caminho errado em (c) é a proposta de decidir a questão testando as duas bibliotecas com entradas grandes. Ela é razoável, aparece em toda turma, e a réplica é curta o bastante para ser dita de memória: teste dá confiança proporcional ao que foi testado, e leitura dá garantia antes de a entrada existir. Emende com o critério operacional, que é o que torna a réplica útil — para saber se um conjunto de padrões usa retrovisão, procure barra invertida seguida de dígito nos padrões, e a resposta sai por leitura, sem executar nada. Quem propõe o teste está oferecendo um método que só encontra o problema depois de a entrada ruim chegar, e no cenário descrito quem espera essa entrada chegar é a fila humana.
Guarde para o fim a frase que o item pede em palavras do estudante — o critério que separa o que uma classe garante do que uma implementação entrega. A formulação que você tem na mão é a resposta esperada, e o enunciado a omitiu de propósito para que ela seja formulada e não reconhecida: a garantia é da classe; a conta é da implementação. Não a escreva no quadro antes de recolher três ou quatro versões da turma. Depois escreva, e deixe cada um comparar a sua com ela.
Sobre a devolutiva escrita. Uma boa resposta classifica as quatro exigências pela memória exigida, com o argumento das casas de pombo conduzido por escrito na terceira, e ordena a quarta acima da terceira dizendo o que a pilha devolve; escreve as duas contas de (b) com a unidade ao lado e nomeia a medição que falta; e recusa a primeira biblioteca em (c) por garantia, e não por velocidade medida. Uma resposta parcial típica classifica as três primeiras corretamente, acerta a quarta e justifica-a dizendo que “casar duas ocorrências é mais difícil”: a fragilidade é ter chegado ao degrau certo por dificuldade percebida, e não por memória exigida. A orientação para essa pessoa é uma tarefa de duas linhas — diga o que a máquina precisa guardar em cada uma das quatro exigências, uma linha por exigência, e ordene as quatro por essa coluna. Quem propôs a pilha para a quarta precisa de outra tarefa, e ela é o experimento refeito à mão: empilhe um código de oito caracteres, desempilhe, escreva o que saiu, e diga que linguagem essa máquina reconhece. Quem recusou a primeira biblioteca por desempenho recebe a terceira tarefa — escreva a recusa de novo sem usar nenhuma palavra de tempo.
1.3.2 Resolução Modelo
(a) A classificação das quatro exigências, justificada pela memória que a máquina reconhecedora precisaria ter.
Primeira exigência — o código de protocolo, duas letras maiúsculas seguidas de seis dígitos: cabe na classe regular. A máquina precisa saber apenas em que posição do código ela está, e as posições são em número fixo: oito. Uma contagem com teto conhecido de antemão cabe dentro do conjunto de estados, porque basta um estado por posição. Nada precisa ser lembrado além do ponto do formato em que se está, e esse ponto pertence a um conjunto finito fixado antes de qualquer mensagem chegar.
Segunda exigência — a data em oito dígitos separados por barras: cabe na classe regular, e pelo mesmo motivo, com uma observação a mais. O comprimento é fixo, de modo que a contagem de posições tem teto. E mesmo a verificação do conteúdo — que o mês esteja entre 01 e 12, que o dia caiba no mês — permanece dentro da classe, porque o conjunto de datas bem formadas é finito, e toda linguagem finita é regular: ela se escreve, no limite, por enumeração. A exigência parece mais rica que a primeira e mora no mesmo degrau.
Terceira exigência — o trecho entre parênteses, com aninhamento sem profundidade máxima declarada: fora da classe regular. A máquina precisaria saber quantas aberturas continuam pendentes, e essa quantidade não tem teto, porque a profundidade não foi limitada por ninguém.
O argumento fecha assim, e vale para qualquer máquina de estados finita. Fixe k, o número de estados, antes de qualquer coisa — ele é parte da máquina, escolhido na construção. Apresente a ela as k+1 mensagens formadas por 1, 2, …, k+1 aberturas consecutivas. São k+1 entradas e apenas k estados disponíveis, de modo que duas delas, com i e j aberturas, i \neq j, terminam no mesmo estado. Dali em diante a máquina responde igual às duas, porque tudo o que ela sabe é o estado em que está. Apresente então os i fechamentos correspondentes: ela aceita, corretamente, a mensagem de i aberturas e i fechamentos, e aceita também, incorretamente, a de j aberturas e i fechamentos, que está desbalanceada.
Acrescentar estados não resolve para nenhum k finito, porque o argumento acima se refaz para qualquer k: escolhido um número de estados, existem k+1 profundidades que o esgotam, e a colisão volta. A ordem dos quantificadores é o ponto — para toda máquina finita existe um contraexemplo. Uma máquina com mais estados reconhece corretamente uma linguagem, só que outra: a dos aninhamentos até uma profundidade fixa, que é um conjunto finito de formas e por isso é regular. Comprar mais estados troca a linguagem reconhecida, e o requisito pedido continua onde estava. O que barra o requisito é a memória, e o repertório de operadores da notação nada tem com isso: acrescentar operadores não muda o que uma máquina de memória finita consegue distinguir.
Quarta exigência — a mensagem em que um mesmo código de protocolo aparece duas vezes, qualquer que seja o código: fora da classe regular, e mais alto na hierarquia que a terceira. A máquina precisaria guardar o bloco inteiro do primeiro código encontrado, para conferir adiante se ele reaparece idêntico. Guardar um número sem teto já sai da classe regular; guardar um bloco de texto e compará-lo depois na mesma ordem sai também da classe seguinte. A forma geral do requisito é a repetição de um bloco arbitrário dentro da mesma cadeia, e ela está fora da classe livre de contexto — resultado que Hopcroft, Motwani e Ullman registram, e cuja demonstração usa uma ferramenta que este percurso ainda não tem.
A pilha não dá conta dela. Uma pilha devolve o que guardou em ordem inversa da que guardou. Empilhado o código AB12, símbolo a símbolo, o desempilhamento devolve 21BA. Uma máquina assim equipada compara um trecho com o espelho dele, que é exatamente o que se precisa para casar aberturas com fechamentos — o fechamento mais recente casa com a abertura mais recente, e a ordem inversa é a ordem certa. A quarta exigência pede a comparação de um trecho com a cópia dele, lida na mesma ordem em que foi escrita, e a pilha entrega a informação virada ao contrário. É essa diferença entre espelho e cópia que separa a terceira exigência da quarta, e ela é invisível para quem classifica pelo aspecto do padrão.
Se o conjunto de códigos válidos fosse finito e conhecido de antemão, a classificação mudaria: a exigência voltaria à classe regular. Com uma lista fechada de códigos c_1, \ldots, c_N, o requisito se escreve como a alternância, sobre os N códigos, dos padrões que exigem duas ocorrências daquele código específico — uma reunião finita de linguagens regulares, e portanto regular pelo fechamento sob união. O que tira a exigência da classe é o “qualquer que seja o código”: é ele que obriga a lembrar um bloco que ninguém listou antes.
Vale registrar, e é a observação que fecha o item, que o formato declarado na primeira exigência já torna esse conjunto finito: duas letras maiúsculas e seis dígitos dão 26^2 \cdot 10^6 = 676\,000\,000 códigos possíveis. Sob essa leitura estrita, a quarta exigência é formalmente regular, e a máquina que a reconhece precisa de um ramo por código — centenas de milhões deles. A classe responde “sim” e a engenharia responde “não”, e as duas respostas estão certas sobre perguntas diferentes. A leitura que sustenta a decisão de projeto é a geral, com o código tratado como bloco sem lista prévia, e é ela que a letra (c) usa.
(b) As duas contas de custo, em símbolos, com a unidade ao lado de cada uma.
O arranjo de hoje lê os padrões uma vez, na partida do serviço, e guarda as árvores prontas:
\text{custo hoje} = c \cdot p \quad \text{por partida do serviço.}
A proposta em discussão lê cada padrão de novo a cada mensagem que chega:
\text{custo da proposta} = c \cdot p \cdot m \quad \text{por dia.}
A conta de hoje multiplica c pelo número de padrões e se paga uma única vez. A conta da proposta traz o fator m, o número de mensagens, e se paga todo dia. O fator que cresce fora do controle de quem opera o serviço é m: quem decide quantas mensagens chegam são os cidadãos no balcão digital, e não a equipe do motor. O número de padrões p é escrito pela própria equipe e muda quando ela decide mudá-lo. A proposta troca um custo limitado e conhecido por um custo que acompanha a demanda, e a demanda é a única grandeza do sistema que ninguém ali dentro governa.
A medição que precisaria existir antes de a proposta ser aceita ou recusada tem duas grandezas nomeadas. Primeira: quanta memória as árvores residentes de fato ocupam, medida em bytes com os padrões reais em uso — porque a proposta existe para poupar memória, e ninguém disse quanta. Segunda: o valor de c, o custo de reduzir e montar a árvore de um padrão, medido nos padrões reais e não estimado. Sem as duas, a discussão compara uma economia desconhecida com um gasto desconhecido, e a decisão sai por preferência de equipe. O terceiro número, m, o serviço já tem: basta contar as mensagens de um dia.
(c) A decisão do motor.
Adote a segunda biblioteca, a que não oferece retrovisão e decide numa única passada, sem voltar atrás sobre o texto já lido.
A razão é a garantia, e não a velocidade observada. A primeira biblioteca atenderia diretamente à quarta exigência, e o preço desse atendimento tem nome na literatura: casar padrão com retrovisor é NP-completo, resultado que Aho registra no Handbook of Theoretical Computer Science, de 1990. Um motor que aceita o operador aceita, junto com ele, padrões cujo custo de casamento não tem limite conhecido em função do tamanho da entrada — e a garantia de tempo do motor inteiro passa a valer o que valer o pior padrão que alguém carregou nele. Em 2 de julho de 2019, um fragmento de padrão com sete caracteres derrubou um serviço em produção por essa via exata.
O critério que sustenta a decisão, em uma frase: a garantia é da classe; a conta é da implementação. Uma classe de linguagens garante que existe uma máquina capaz de decidir a pergunta, e diz que espécie de memória ela precisa ter; uma implementação escolhe uma estratégia concreta e cobra por ela em tempo e espaço, e a conta dela pode exceder o que a classe exigiria. As duas afirmações convivem sem contradição: o mesmo padrão pertence a uma classe que se decide numa passada e, executado por um motor que retrocede, cobra um tempo sem limite conhecido em função do tamanho da entrada. A classe descreve o que é possível; a implementação determina o que se recebe.
A quarta exigência, recusada a retrovisão, permanece de pé — ela sobe de camada. O motor reconhece as ocorrências de código pelo padrão da primeira exigência, que é regular, e entrega a lista de ocorrências; a verificação de repetição se faz fora da linguagem de padrões, comparando os trechos extraídos. A exigência que não coube na classe passou a ser paga pela camada de cima, com código escrito à mão, e o preço dela ficou visível e limitado — o que a retrovisão fazia dentro do padrão, sem preço declarado.
Quem paga a diferença entre as duas escolhas é quem espera na fila de leitura humana. Ela não trabalha no serviço, não escreveu padrão nenhum, e o que lhe chega é a demora, ou a mensagem que voltou sem triagem porque o motor ficou preso num padrão patológico enquanto outras mensagens se acumulavam. A distância entre a decisão e a consequência é o que torna o caso sério: quem escolhe a biblioteca não é quem espera na fila.
A quem propuser resolver a questão testando as duas bibliotecas com entradas grandes, a resposta tem duas partes. A primeira é sobre o alcance do método: teste dá confiança proporcional ao que foi testado, e a entrada que derruba um motor com retrocesso é justamente aquela que ninguém pensou em escrever. A segunda é o que se faz em lugar do teste, e é mais barata: a garantia se obtém por leitura, antes de qualquer entrada existir. Para saber se um conjunto de padrões usa retrovisão, procure nos padrões barra invertida seguida de dígito. A resposta sai por inspeção do texto, vale para toda entrada possível, e custa alguns minutos — enquanto a bateria de testes custa dias e vale apenas para as entradas que ela conteve.