1 Expressões regulares e linguagens regulares — resolução comentada
Documento exclusivo do professor, e gabarito de instrumento que compõe nota. Não o publique em perfil de estudante nem o distribua antes da aplicação.
As duas questões da verificação individual do módulo 02 medem os dois lados da mesma moeda, e cada uma delas sozinha deixa passar metade da turma. A objetiva pede uma contagem de nós: quatro linhas da tabela de reduções compostas sobre catorze caracteres digitados, com um número exato no fim. A dissertativa não tem número algum e pede posição tomada sobre uma proposta de troca de motor num serviço público de triagem, onde o custo de errar recai sobre gente que nunca escreveu um padrão na vida.
O par é montado para separar quem opera a redução de quem a recita. Um estudante pode enunciar corretamente que o núcleo tem três operadores e duas folhas e ainda assim compartilhar a subárvore na hora de clonar, produzindo um grafo e uma contagem menor que a esperada — menor, aliás, parece bom, e é esse o problema. O contrário também acontece: quem soma 157 sem errar uma parcela pode continuar achando que a retrovisão é mais um açúcar sintático, porque a aparência do padrão que alguém escreveria não denuncia a memória que a máquina precisaria ter.
Conduza a devolutiva na ordem do arquivo. A objetiva se corrige sozinha no ambiente, e o que interessa dela chega pelo relatório de distribuição: os quatro números errados têm dono conceitual registrado no contrato do módulo, e a proporção que caiu em cada um aponta a seção que volta ao quadro. A dissertativa fica aguardando avaliação até a correção manual contra a rubrica da Seção 1.2.3, e a nota do bloco A só fecha depois dela. São seis módulos no bloco, portanto seis respostas escritas por estudante: a régua tem de ser a mesma na primeira e na trigésima, e é por isso que ela está escrita aqui.
1.1 Questão 1: ::M02E01:: — objetiva
1.1.1 O que o item pede
O campo do código de protocolo exige duas letras minúsculas obrigatórias seguidas de uma terceira opcional. Quem digitou usou a notação de conveniência: a faixa das vinte e seis minúsculas sob um quantificador contado de duas repetições, seguida da mesma faixa sob o operador opcional. Catorze caracteres, contando colchetes e chaves. O leitor de expressões da equipe reduz tudo ao núcleo durante a leitura, expande cada faixa em folhas e alternâncias, clona a subárvore uma vez por repetição exigida, e reduz o opcional à alternância com a cadeia vazia. A pergunta é quantos nós a árvore tem e como eles se repartem.
O comando encadeia quatro recuperações e uma composição. As quatro são linhas da tabela de reduções escritas em pares; a composição é a parte que o item mede, porque cada redução isolada é fácil e a ordem em que elas se empilham é onde a turma escorrega. A alternativa marcada com = é, ao pé da letra:
“157 nós, sendo 79 folhas e 78 nós de operador.”
1.1.2 O caminho até a resposta
O primeiro passo é a faixa, e ele já foi feito no material com número na mão. Uma faixa de n símbolos vira n folhas e n-1 alternâncias, isto é, 2n-1 nós. A alternância é binária e junta duas coisas de cada vez, de modo que a primeira folha não consome operador algum e cada folha seguinte consome um. Para as vinte e seis minúsculas: 26 folhas, 25 alternâncias, 51 nós para três caracteres digitados.
O segundo passo é o quantificador contado. Ele exige duas repetições, e o enunciado é explícito sobre o modo como o leitor as produz: uma cópia inteira da subárvore para cada repetição, e não dois ponteiros para o mesmo nó. São 102 nós, 52 folhas e 50 alternâncias, e nenhuma economia.
O terceiro passo é o opcional, e é ele que carrega o detalhe que decide o item. A redução de x? é a alternância entre x e a cadeia vazia. O ramo da esquerda continua contendo a expressão por inteiro — a terceira cópia da faixa, com seus 51 nós. O ramo da direita é a folha da cadeia vazia, que tem existência própria na árvore. E a alternância que une os dois é mais um nó de operador. O opcional custa, portanto, 51 + 1 + 1 = 53 nós.
O quarto passo é a emenda. Três subárvores em sequência — cópia, cópia, opcional — se juntam por duas concatenações, pela mesma razão pela qual vinte e seis folhas pedem vinte e cinco alternâncias.
Somando: 51 + 51 + 51 = 153 nós nas três faixas, mais a folha da cadeia vazia, mais a alternância do opcional, mais as duas concatenações. Total 157. As folhas são 26 \times 3 + 1 = 79; os operadores são 25 \times 3 + 1 + 2 = 78.
A segunda via de cálculo vale ir ao quadro, e ela não usa nada da soma acima. Toda operação que sobrou nesta árvore é binária: alternância e concatenação tomam exatamente dois filhos. Numa árvore em que todo nó interno tem dois filhos, o número de internos é o de folhas menos um, e o total é 2\ell - 1. Com \ell = 79, o total é 157 e os internos são 78. Duas contas independentes chegando ao mesmo lugar, que é o padrão de conferência que o item quer instalar.
Um cuidado a declarar em aula, porque ele limita a identidade: o fecho é unário, e uma árvore que o contivesse deixaria de satisfazer 2\ell-1. O padrão deste item não tem fecho — só faixa, quantificador contado e opcional —, e é essa ausência que autoriza a segunda via. Aplicá-la a [a-z]+, que tem 104 nós e 52 folhas, devolve 103 e erra por um, justamente o nó de fecho.
1.1.3 Por que cada distrator atrai
55 nós, 27 folhas e 28 operadores — compartilhou a subárvore. É o E-14 do contrato do módulo, e a tutoria o prevê como o quarto grupo: o estudante aponta as três ocorrências da faixa para o mesmo nó “para economizar memória”, e acha que otimizou. A atração aqui é estética antes de ser conceitual, porque duplicar 51 nós idênticos parece desperdício óbvio a qualquer pessoa que já escreveu código. O que sai dali deixa de ser árvore e passa a ser grafo, com mais de um pai para o mesmo filho, e o sintoma numérico vem invertido: a contagem cai, e menor parece melhor. A trava independente pega o engano sem que ninguém precise olhar o código — 28 operadores para 27 folhas é impossível numa árvore de operadores binários, que aceitaria no máximo 26. O estrago real aparece dois capítulos adiante, quando a construção do autômato percorre o nó compartilhado duas vezes e liga ao mesmo trecho de máquina passagens que deveriam ser distintas.
106 nós, 53 folhas e 53 operadores — o ramo opcional sem a terceira cópia. Este é o distrator mais bem-feito dos quatro, porque quem chega nele fez tudo certo até a última linha. As duas cópias do quantificador contado foram expandidas por inteiro, as concatenações entraram, e o opcional foi lido como se acrescentasse apenas a possibilidade da ausência: a folha da cadeia vazia e a alternância. A expressão continua inteira dentro do ramo esquerdo, e é essa presença que o estudante apagou. O sinal está na repartição: 53 e 53 significam uma alternância que ficou com um filho só, e alternância com um filho é operador sem função.
156 nós, 78 folhas e 78 operadores — esqueceu a folha da cadeia vazia. Aqui a terceira cópia entrou, as concatenações entraram, e o ramo vazio foi tratado como ausência de nó. A confusão de fundo é a E-8, a segunda forma do velho engano entre \emptyset e \varepsilon que o módulo 01 declarou atravessar o período inteiro: quem escreve “vazio” pensa em “nada”, e nada não ocupa espaço. A cadeia vazia é uma das duas folhas do núcleo, tem existência própria na árvore, e é ela que faz a linguagem denotada incluir o código de duas letras — sem ela, o opcional deixa de ser opcional. Folhas e operadores em número igual acusam de novo, pelo mesmo argumento.
160 nós, 79 folhas e 81 operadores — usou n alternâncias em vez de n-1. O estudante acertou a estrutura inteira e errou a aritmética da junção, contando uma alternância por folha da faixa. A atração é a simetria: parece natural que vinte e seis coisas peçam vinte e seis operadores, e a fórmula 2n-1 tem exatamente a forma que se decora errado. Os três nós excedentes são um por faixa. A repartição denuncia antes de qualquer conferência de código, porque 79 folhas não comportam 81 internos, e este é o único dos quatro em que a contagem de folhas está certa — o que faz dele o mais útil para introduzir a segunda via, já que a soma parece plausível e a identidade não perdoa.
1.1.4 O que o erro revela sobre o ensino
Concentração em 55 é o sinal mais grave, porque o erro sobrevive à explicação e reaparece no código do projeto: retome a redução do fecho positivo executando o compartilhamento até a falha, com a contagem de nós antes e depois no quadro, e só então pergunte o que acontece quando algo percorrer aquela estrutura a partir da raiz. Concentração em 106 ou 156 pede a tabela de reduções relida em pares, com o lado direito do opcional escrito por extenso; concentração em 160 pede apenas a fórmula da faixa refeita com n=3, onde os dois nós de alternância se contam com o dedo.
1.2 Questão 2: ::M02E02:: — dissertativa
1.2.1 O que o item pede
Um serviço público tria mensagens escritas por cidadãos num balcão digital. Centenas de padrões passam por um único motor da família que compila para máquina de estados e decide numa passada; o que não é triado cai numa fila de leitura humana lenta. Chega uma exigência nova — sinalizar a mensagem em que um mesmo código de protocolo aparece duas vezes, qualquer que seja o código — e alguém propõe trocar o motor por outro da família com retrocesso, que oferece retrovisão. A proposta vem apoiada em duas afirmações: a retrovisão seria mais um açúcar sintático, como a verificação adiante e o grupo de captura, e trocar biblioteca sairia mais barato que reescrever a exigência.
O comando pede crítica com posição tomada, em oito a doze linhas, cobrindo cinco pontos: a pergunta que decide a classe aplicada ao operador, a separação entre quem sai da classe e quem só parece sair, o custo nomeado com a fonte que o capítulo registra, quem paga esse custo no serviço descrito, e o fecho declarando sob que condição escrita a mesma exigência voltaria à classe regular sem troca de motor.
O espelho #### do item, transcrito ao pé da letra, é o esqueleto da correção:
“A resposta esperada percorre cinco pontos, nesta ordem. Primeiro, a pergunta que decide, aplicada ao operador — ele exige lembrar um trecho da entrada cujo tamanho não tenha teto? A retrovisão exige, porque conferir a repetição de um bloco obriga a guardar o bloco inteiro, caractere por caractere, e os códigos não têm comprimento limitado por nada. Refeito o argumento das casas de pombo, uma máquina com k estados escolhidos antes de ela rodar termina no mesmo estado para dois blocos distintos, deixa de distingui-los dali em diante e erra uma das duas respostas; acrescentar estados não salva, porque o argumento se refaz para qualquer k finito. Daí a retrovisão sair da classe regular, e daí ela deixar de ser açúcar sintático — açúcar abrevia sem ampliar, e este operador amplia. Segundo, a separação que a proposta não faz. Verificação adiante, grupo de captura e quantificador não guloso permanecem dentro da cerca, cada um por razão própria, e a resposta forte diz qual — o que se verifica adiante é ele mesmo regular; a captura marca um trecho para extração e a linguagem descrita é a mesma com ela e sem ela; o não guloso muda qual trecho é escolhido quando há mais de uma escolha, e não quais cadeias pertencem ao conjunto. A analogia com esses três é o que dá plausibilidade ao pedido, e é ela que cai. Terceiro, o custo com fonte declarada — casar padrão com retrovisor é problema NP-completo, resultado que Aho registra no Handbook of Theoretical Computer Science, de 1990. Quarto, quem paga. A garantia de tempo é propriedade do conjunto de padrões e vale o que vale o pior membro dele, de modo que basta um padrão casar com uma entrada infeliz para que todos os outros, corretamente escritos, parem junto; o serviço deixa de triar, e a conta recai sobre os cidadãos cujas mensagens caem na fila humana lenta, que não escreveram padrão nenhum e não trabalham no serviço. Quinto, o fecho. Com o conjunto de códigos de protocolo válidos finito e conhecido antes de a entrada existir, a exigência descreve um conjunto finito de cadeias, e toda linguagem finita é regular — a expressão fica feia e comprida, e ela existe, que é a única coisa exigida, e o motor atual continua servindo. O que tira a exigência da classe é o qualquer que seja o código, e essa condição precisa constar da especificação por escrito, sob pena de virar defeito escondido. A posição aceitável é a recusa da troca, sustentada pelo mecanismo, e não por desempenho medido. O equívoco mais provável é recusar a proposta apenas alegando que a biblioteca nova seria mais lenta, ou aceitá-la porque a notação de uso corrente é extensível e bastaria acrescentar operadores; quem tropeçar em qualquer dos dois precisa rever, no capítulo sobre o que a cerca barra e o que ela deixa passar, o procedimento de três passos que classifica um requisito pela memória que a máquina precisaria ter, e nunca pela aparência do padrão que alguém escreveria.”
O item admite uma posição só, a recusa da troca, e isso é escolha declarada de projeto. A liberdade do estudante está no mecanismo com que ele sustenta a recusa e na condição que redige no fecho, e é ali que a rubrica mede.
1.2.2 Resposta de referência
Segue o texto esperado de uma resposta de nota máxima, na extensão declarada pelo enunciado. Ele ocupa doze linhas.
Recuso a troca. A pergunta que decide a classe é se o operador exige lembrar um trecho da entrada cujo tamanho não tem teto, e a retrovisão exige: conferir que um código apareceu duas vezes obriga a guardar o código inteiro, caractere por caractere, e nada limita o comprimento dele. Uma máquina de estados tem k estados escolhidos antes de ela rodar; havendo mais códigos distintos que estados, dois deles terminam no mesmo estado, a máquina deixa de distingui-los dali em diante e erra uma das duas respostas. Acrescentar estados não resolve, porque o argumento se refaz para qualquer k finito. A retrovisão sai, portanto, da classe regular, e por isso ela deixa de ser açúcar sintático: açúcar abrevia sem ampliar, e este operador amplia o que se pode descrever. A analogia da proposta é o que a sustenta, e é ela que cai. Verificação adiante, grupo de captura e quantificador não guloso ficam dentro da cerca, cada um por razão própria — o que se verifica adiante é ele mesmo regular; a captura marca um trecho para extração, e a linguagem descrita é a mesma com ela e sem ela; o não guloso muda qual trecho é escolhido quando há mais de uma escolha, sem mudar quais cadeias pertencem ao conjunto. Casar padrão com retrovisor é problema NP-completo, resultado que Aho registra no Handbook of Theoretical Computer Science, de 1990. Quem paga não é quem pediu a exigência: a garantia de tempo é propriedade do conjunto de padrões e vale o que vale o pior membro dele, de modo que basta um padrão encontrar uma entrada infeliz para que as outras centenas, corretamente escritas, parem junto, e a conta recai sobre os cidadãos cujas mensagens caem na fila humana lenta. Com o conjunto de códigos de protocolo válidos finito e conhecido antes de a entrada existir, a exigência descreve um conjunto finito de cadeias, e toda linguagem finita é regular: a expressão fica feia e comprida, ela existe, e o motor atual continua servindo. O que tira a exigência da classe é o “qualquer que seja o código”, e essa condição precisa constar da especificação por escrito, sob pena de virar defeito escondido.
1.2.3 Rubrica de correção
As faixas cobram os cinco pontos na ordem do espelho, mais a posição que o comando exigiu. A evidência é sempre algo que se lê no texto do estudante, e adjetivo de impressão não decide faixa aqui. Os pesos moram na especificação de avaliação.
| Faixa | Evidência observável no texto do estudante | O que devolver |
|---|---|---|
| Satisfaz | Escreve a recusa da troca e a sustenta pelo mecanismo; aplica a pergunta da memória sem teto ao operador e afirma que conferir a repetição obriga a guardar o bloco inteiro, com o argumento dos k estados escrito — dois blocos distintos terminando no mesmo estado, e acrescentar estados não salvando; nomeia ao menos dois dos três acréscimos que permanecem na classe (verificação adiante, grupo de captura, quantificador não guloso) e dá a razão de ao menos um deles; escreve NP-completo com a fonte Aho, Handbook of Theoretical Computer Science, 1990; nomeia como pagantes os cidadãos cujas mensagens caem na fila humana, ligando a perda à propriedade do conjunto de padrões — um padrão infeliz derrubando os outros; e fecha com a condição escrita, isto é, conjunto de códigos válidos finito e conhecido antes de a entrada existir, tornando a exigência uma linguagem finita e portanto regular. | Apontar em qual dos cinco pontos a redação está mais firme e pedir a mesma frase aplicada ao projeto do próprio estudante: qual dos operadores da notação dele ainda não passou pela pergunta da memória sem teto. |
| Satisfaz em parte, com a lacuna nomeada | Cumpre de dois a quatro dos pontos. Lacunas típicas, cada uma nomeada na devolutiva: recusa a troca e sustenta a recusa só pela lentidão do motor com retrocesso, sem chegar à saída da classe; aplica a pergunta corretamente e empilha a retrovisão com a verificação adiante, tratando as quatro construções como se saíssem juntas; escreve NP-completo sem fonte, ou com fonte trocada; cobra o custo apenas de quem pediu a exigência, sem alcançar os padrões que nada pediram nem os cidadãos na fila; percorre os quatro primeiros pontos e fecha sem condição alguma, ou fechando com “limitar o tamanho da mensagem”, que não é a condição do espelho; ou escreve a condição finita sem exigir que ela conste da especificação por escrito. | Nomear a lacuna com a palavra que faltou e devolver a pergunta correspondente por escrito: o que essa máquina precisaria lembrar para decidir; qual das quatro construções muda o conjunto de cadeias e quais só mudam o que se extrai dele; quem escreveu os outros padrões que param junto; e o que precisaria estar assinado na especificação para o motor atual continuar servindo. |
| Não satisfaz | Aceita a troca, com ou sem salvaguarda; ou a recusa apenas alegando que a biblioteca nova seria mais lenta, prometendo medir o desempenho antes de decidir, e para aí; ou justifica a saída da classe pela ausência de operador na notação, em vez de pela memória exigida; ou afirma que a retrovisão é açúcar sintático como os outros três; ou aceita a proposta porque a notação de uso corrente é extensível e bastaria acrescentar operadores; ou descreve as duas famílias de motor corretamente e não toma posição sobre a proposta; ou escreve tão abaixo da extensão pedida que não há texto em que verificar ponto algum. | Devolver a seção do capítulo sobre o que a cerca barra e o que ela deixa passar, e pedir a reescrita respondendo a uma pergunta única: o que essa máquina precisaria lembrar, e por quanto tempo, para decidir se um código apareceu duas vezes. |
1.2.4 Erros recorrentes e o que devolver
Recusar pelo desempenho. É o equívoco que o próprio espelho antecipa, e chega bem escrito: o motor com retrocesso é reconhecidamente mais lento, logo a troca é ruim. O argumento acerta a conclusão pelo caminho errado, e desmonta na primeira reunião em que alguém apresentar uma medição favorável. Faixa inferior quando é a espinha da resposta; faixa intermediária quando aparece ao lado do argumento dos k estados. Devolva a pergunta que fecha o assunto: qual medição de tempo faria a máquina de estados passar a lembrar um bloco de tamanho ilimitado.
Trocar a causa do limite. É o E-12 do contrato, e o plano de aula já registra o peso dele nas questões conceituais: o estudante aceita que a exigência sai da classe e culpa a notação por não ter operador de recursão. O que barra o requisito é a memória que a máquina teria de ter, e o repertório da notação nada decide. Faixa intermediária quando o resto está lá, faixa inferior quando substitui o argumento inteiro. Devolva o procedimento de três passos que classifica um requisito pela memória, e peça o mesmo parágrafo reescrito sem a palavra “operador”.
Empilhar a retrovisão com os três que ficam. O estudante conclui que a família com retrocesso inteira sai da classe, e joga verificação adiante, captura e não guloso no mesmo saco. É o erro simétrico do que a proposta comete, e a rubrica o trata com o mesmo peso, porque quem não separa também não decide. Faixa intermediária. Devolva a pergunta por construção: a linguagem descrita muda quando eu removo esta construção do padrão?
Descrever sem decidir. A resposta explica corretamente as duas famílias de motor, cita PCRE e RE2 com as datas certas, e nunca diz o que fazer com a proposta. Faixa intermediária, com a lacuna na posição. Devolva pedindo a primeira frase do texto reescrita como decisão assinada.
Aceitar a proposta pela extensibilidade da notação. É o E-7 na forma que o plano registra como a que mais aparece: a notação é extensível, logo basta acrescentar o operador. Faixa inferior. Devolva pedindo a expressão que resolveria a exigência para um código de comprimento arbitrário, e deixe a sala perceber que o texto não termina.
Cobrar o custo do bolso errado. A resposta nomeia como pagante a equipe que mantém o filtro, ou o autor da exigência nova. O enunciado descreveu uma fila de leitura humana que anda devagar, e o item existe para que os cidadãos parados nela apareçam no texto. Faixa intermediária, lacuna no quarto ponto. Devolva o cenário com o número na mão: centenas de padrões compartilhando um motor, e um deles bastando para derrubar todos.
Fechar com “limitar o tamanho da entrada”. O fecho pedia a condição que devolve a exigência à classe, e recebe uma salvaguarda operacional. Truncar a mensagem torna a linguagem finita por acidente e deixa a exigência escrita do mesmo jeito, sem que ninguém saiba onde o limite mora. Faixa intermediária. Devolva a condição pelo nome — conjunto de códigos válidos finito e conhecido antes de a entrada existir — e peça a frase que ela ocuparia na especificação.
1.2.5 O que o erro revela sobre o ensino
Turma que recusa a troca pelo desempenho, ou que culpa a notação, trocou classe de máquina por esforço de programar, e o bloco do limite não pegou — refaça o argumento dos k estados no quadro sobre este caso, com dois códigos distintos escritos lado a lado e a pergunta operacional escrita por extenso antes de qualquer conclusão: o que essa máquina precisaria lembrar para decidir?