flowchart LR
M05["Módulos 3 a 5<br/>Autômatos, determinização<br/>e minimização<br/>a ferramenta pronta"]
M06["Módulo 6<br/>Limites das<br/>linguagens regulares<br/>A FRONTEIRA"]
M07["Módulo 7<br/>Análise léxica<br/>o que cabe<br/>no modelo fraco"]
M09["Módulos 8 a 10<br/>Gramáticas, pilha e<br/>análise sintática<br/>o modelo mais forte"]
M05 --> M06
M06 --> M07
M06 --> M09
subgraph ENTREGA["O que o módulo 6 deixa pronto"]
D1["Fechamento com as<br/>construções que o<br/>demonstram"]
D2["Lema do bombeamento<br/>e a disciplina dos<br/>quantificadores"]
D3["Myhill-Nerode:<br/>estado é distinção<br/>que a linguagem obriga"]
D4["Falha do artefato<br/>diante do aninhamento,<br/>medida em estados"]
end
M06 --- ENTREGA
D1 -.->|"prova por transferência"| D2
D4 -.->|"justifica a pilha"| M09
Limites das Linguagens Regulares — Plano de Aula
Documento exclusivo do professor. Guia operacional das seis aulas do módulo: roteiro por blocos das duas aulas teóricas, plano das quatro aulas de tutoria, entregáveis e riscos antecipados. Não distribua à turma — a demonstração deliberadamente defeituosa e as questões de discussão perdem função assim que o estudante as lê antes da aula.
Visão Geral do Módulo
Onde este módulo fica — é a fronteira, e é o que torna necessária a segunda metade do semestre.
Cinco módulos foram gastos construindo um motor de reconhecimento que funciona. Este serve para descobrir o que ele não faz — e, mais do que isso, para demonstrar que o que ele não faz é impossível para qualquer coisa da mesma família. É o único módulo do semestre cujo produto principal é uma impossibilidade, e é essa singularidade que precisa ser conduzida com cuidado.
O ganho de conduzi-lo bem aparece só no bloco seguinte, e vale ter isso claro antes de entrar em sala. Se a turma sair daqui sem a demonstração no lugar, o autômato de pilha e o analisador sintático dos módulos 9 e 10 vão parecer técnicas alternativas — outra forma de fazer a mesma coisa, adotada por tradição. Com a demonstração no lugar, eles aparecem como a única saída disponível, exigida por um resultado. A diferença entre as duas leituras é a diferença entre o profissional que sabe por que a arquitetura é assim e o que a reproduz por hábito.
O tratamento é conceitual com exigência de demonstração, e essa exigência é o eixo do módulo. Aqui você não avalia se o estudante chegou à conclusão certa — a conclusão é conhecida e está no material —, e sim se o argumento que a sustenta é válido. Um raciocínio inválido que produz a conclusão certa é reprovável, e este é o módulo em que esse padrão se estabelece para o resto do semestre.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Estabelecer a fronteira da classe regular e desenvolver a capacidade de demonstrar que uma linguagem está fora dela. Conectar o resultado teórico a uma limitação concreta e observável do artefato construído, produzindo a motivação para o modelo mais forte do bloco seguinte.
Competências a desenvolver. Capacidade de conduzir uma demonstração formal com estrutura lógica correta, entendendo que uma prova incompleta não prova nada. Capacidade de reconhecer, ao encontrar um obstáculo de implementação, quando ele decorre de uma limitação teórica do modelo adotado e não de erro de programação — distinção que separa quem insiste inutilmente de quem troca de abordagem.
Habilidades a adquirir. Enunciar e aplicar as propriedades de fechamento da classe regular, com as construções que as demonstram. Enunciar o lema do bombeamento com a ordem correta dos quantificadores. Produzir uma demonstração completa de não regularidade na forma contrapositiva. Reconhecer, em uma linguagem, os indícios que sugerem não regularidade.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a ordem importa, e a inversão que mais importa é tratar fechamento antes do bombeamento.
Bloco de abertura — escrevam a expressão dos parênteses balanceados
Esta é a melhor abertura disponível no semestre e ela funciona sozinha: peça, sem nenhuma introdução, que cada dupla escreva no papel uma expressão regular que reconheça sequências de parênteses balanceados. Não diga que é impossível. Não diga nada.
Circule e observe a progressão, porque ela é sempre a mesma e é o conteúdo do módulo acontecendo. A dupla resolve um par em segundos. Resolve dois níveis com algum cuidado na escrita. Resolve três reclamando. E em torno do quarto ou quinto nível alguém levanta a cabeça e diz alguma versão de “isso não vai terminar nunca”. Quando essa frase aparecer, e ela aparece, peça que a pessoa repita em voz alta para a sala e escreva no quadro exatamente o que ela disse.
Aí faça a única intervenção do bloco: “está correto, e o que vamos fazer hoje é provar isso”. Deixe claro em que sentido — não é difícil, não é uma limitação da notação que adotamos, não é falta de habilidade: é impossível no sentido matemático, e a demonstração cabe em cinco linhas que vocês vão saber escrever ao fim da segunda aula. Escreva no canto do quadro a palavra IMPOSSÍVEL com um ponto de interrogação e deixe-a lá até o fechamento.
Bloco seguinte — fechamento, e por que ele vem primeiro
Anuncie a inversão em voz alta, porque ela contraria a ordem de vários livros e alguém vai perceber: fechamento primeiro, bombeamento depois. A razão é que propriedades de fechamento não são curiosidade taxonômica, são ferramenta de demonstração — e uma ferramenta apresentada depois do problema que resolve chega tarde.
Passe rápido por união, concatenação e fecho, dizendo o que basta: as três são fáceis porque correspondem exatamente aos operadores da notação, e as construções sobre autômatos já foram vistas. Gaste o tempo do bloco nas duas que surpreendem.
O complemento é uma construção de três palavras — troque finais por não finais — e tem duas hipóteses que ninguém lembra. Faça a demonstração do perigo no quadro, com números. Desenhe o autômato de dois estados que reconhece a* sobre o alfabeto {a, b}, sem transição definida para b. Pergunte à sala o que acontece com a cadeia ab: ela morre, e portanto é rejeitada. Agora inverta a finalidade e pergunte de novo: ab continua morrendo no mesmo lugar, continua rejeitada. Escreva a conclusão: o autômato “complementado” rejeita ab e o original também, de modo que ele não é o complemento de coisa alguma. Complete o autômato para três estados, refaça a inversão, e mostre que agora o estado de erro virou final e é ele que aceita ab. Diga a frase que fecha: totalizar não é higiene, é a hipótese do teorema.
A interseção é o produto, e o ponto que rende é a economia. Escreva a transição do par, \delta((p,q), a) = (\delta_1(p,a), \delta_2(q,a)), e mostre que a única diferença entre interseção e união é o conjunto de estados finais — os dois componentes finais, ou pelo menos um. Registre também a diferença entre definição e implementação com o número da nossa própria referência: o produto de um autômato de três estados por um de dois tem seis estados na definição e nasce com três quando construído por percurso a partir do par inicial, porque os demais pares nunca são alcançados.
Bloco seguinte — demonstrar por transferência
Este bloco tem um único objetivo e ele é vendável: mostrar que se pode provar não regularidade sem fazer conta nenhuma. Tome L como o conjunto das cadeias sobre {a, b} com o mesmo número de a e de b e conduza o argumento no quadro em três linhas: L \cap a^*b^* = \{a^nb^n\}; se L fosse regular, a interseção com a linguagem regular a^*b^* seria regular; mas \{a^nb^n\} não é. Contradição.
Alguém sempre observa que o argumento usa o caso canônico sem tê-lo demonstrado. Reconheça o crédito na hora — é a observação certa — e transforme-a na ponte: “é exatamente por isso que o próximo bloco existe; o bombeamento é feito uma vez, sobre o caso canônico, e todo o resto se resolve por transferência”.
Primeira questão de discussão em duplas. “Um autômato determinístico tem função de transição parcial, sem transição definida para alguns pares de estado e símbolo. Trocando finais por não finais, obtém-se um autômato que reconhece: (a) o complemento da linguagem original; (b) uma linguagem contida no complemento, mas em geral menor; (c) o complemento, desde que o alfabeto seja o mesmo; (d) a mesma linguagem original.”
Voto individual sem comentário seu, discussão em duplas, segundo voto. A resposta é (b): as cadeias que morriam por falta de transição continuam morrendo, e portanto não entram na linguagem do autômato invertido. Quem vota (a) memorizou a construção sem a hipótese. Quem vota (c) percebeu que há uma condição, mas a colocou no lugar errado — e esse é o voto mais produtivo para comentar, porque a exigência não é sobre o alfabeto ser o mesmo, e sim sobre a função ser total sobre ele.
Bloco seguinte — a casa dos pombos, com a contagem feita
Não introduza o lema pelo enunciado. Introduza pela contagem, no quadro, com números fixos.
Fixe um autômato com n = 5 estados e uma cadeia de comprimento m = 6. Pergunte quantos estados a máquina visita ao processá-la, e espere a resposta errada, que é seis. Corrija na frente da sala: são sete, porque existe um estado antes de qualquer leitura, isto é, m + 1. Sete valores retirados de um conjunto de cinco. Escreva a conclusão como obrigação, não como probabilidade: algum estado se repete.
Então nomeie as consequências. Se r_s = r_t com s < t, o trecho lido entre as duas passagens é um ciclo; percorrê-lo uma vez, dez vezes ou nenhuma vez termina no mesmo estado; e a máquina não tem como saber a diferença, porque o estado é toda a memória que ela possui. Volte aos parênteses do quadro e feche o raciocínio informalmente: numa cadeia de aberturas seguidas de fechamentos, a repetição está dentro do bloco de aberturas, repetir o ciclo acrescenta aberturas sem acrescentar fechamentos, e a máquina aceitaria uma cadeia desbalanceada.
Termine dizendo que isso ainda não é uma demonstração, e diga por quê nestes termos: falta dizer em relação a quê a cadeia é “longa o bastante”, e falta garantir onde o ciclo está. É para apertar esses dois parafusos que o lema existe.
Bloco seguinte — o enunciado, os quantificadores e a partida
Escreva o enunciado por extenso e depois em símbolos, com todos os quantificadores visíveis, e leia a cadeia em voz alta: existe, para todo, existe, para todo. Negue a fórmula na frente deles e leia de novo: para todo, existe, para todo, existe. Diga que é essa segunda fórmula que descreve a demonstração que eles vão escrever, e que quase todo erro do módulo nasce de trocar um turno.
Aí jogue a partida. Você é o Adversário, a turma é o Demonstrador. Anuncie n = 4 e peça a cadeia. Se a turma propuser w = aaaabbbb, decomponha da forma que mais atrapalhar — por exemplo x = a, y = aa, z = abbbb — e devolva a bola pedindo o expoente. Com i = 2 sai aaaaaabbbb, seis a contra quatro b, fora da linguagem, e a turma ganha o ponto.
Depois jogue uma segunda partida com a intenção contrária: aceite uma cadeia mal escolhida, se alguém propuser uma, e escolha a decomposição que a salva. O momento pedagógico do módulo inteiro está aqui — a sala percebe sozinha que o problema não estava na conclusão, e sim no segundo lance. Se ninguém propuser cadeia ruim, proponha você: sobre \{a^nb^m : n > m\} com n = 4, ofereça w = aaaabbb e mostre que bombear com i = 2 mantém a cadeia na linguagem; só o expoente zero resolve, e é o que quase ninguém tenta.
Segunda questão de discussão em duplas. “Numa demonstração de não regularidade pelo lema do bombeamento, quem escolhe o quê? (a) o demonstrador escolhe n, a cadeia e o expoente; (b) o demonstrador escolhe a cadeia e o expoente, e recebe n e a decomposição; (c) o demonstrador escolhe a cadeia e a decomposição, e recebe n e o expoente; (d) o demonstrador escolhe apenas o expoente.”
A resposta é (b). A alternativa (c) é a que interessa e costuma ser a mais votada no primeiro turno: é literalmente o erro dominante do módulo, escrito como opção. Não revele a resposta antes da discussão em duplas; guarde o histograma do primeiro voto, porque ele prevê com precisão desconfortável quantas demonstrações voltarão para correção na tutoria.
Bloco de abertura da segunda aula — a demonstração errada
Comece a segunda aula sem recapitulação. Projete a demonstração defeituosa do caso canônico — aquela que diz “tome a decomposição x = \varepsilon, y = a” e conclui corretamente que \{a^nb^n\} não é regular — e peça que a turma encontre o defeito em duplas, avisando apenas que existe um.
Deixe que tentem antes de intervir. A dificuldade é real e é instrutiva: a conclusão está certa, as contas estão certas, e é justamente por isso que o argumento passa. Quando alguém achar, faça a correção na frente da sala trocando uma frase só — onde estava “tome a decomposição”, escreva “seja w = xyz uma decomposição arbitrária com |y| \ge 1 e |xy| \le p” — e mostre que a restrição sobre a forma de y passa a ser deduzida da condição de localização em vez de postulada. Dê o critério de autoverificação para eles usarem na tutoria: procure a primeira frase em que você fala de x, y e z; se ela tem um verbo no imperativo, a demonstração provavelmente está errada.
Bloco seguinte — as demonstrações resolvidas
Faça três no quadro, inteiras, sem pular passo. A primeira é o caso canônico e é o modelo: w = a^pb^p, localização obriga y = a^t com t \ge 1, i = 2 produz a^{p+t}b^p com p + t > p, fora da linguagem. Registre em seguida que i = 0 também resolveria, produzindo a^{p-t}b^p, e que quando os dois funcionam se escolhe o de conta mais limpa.
A segunda é a que paga a dívida da abertura: os parênteses balanceados, em cinco linhas, com w = (^p)^p. Depois de escrevê-la, pare e amarre ao curso — toda linguagem de programação carrega essa estrutura em expressões, blocos e chamadas aninhadas, e é por isso, e não por convenção, que a análise sintática é uma fase separada da análise léxica.
A terceira precisa ter números concretos, porque é a que ensina o argumento de lacuna. Tome os quadrados perfeitos e faça a conta com p = 5: a cadeia é a^{25}, a localização dá 1 \le t \le 5, o bombeamento com i = 2 produz comprimento entre 26 e 30, e o quadrado seguinte a 25 é 36. Escreva a cadeia de desigualdades 25 < 25 + t \le 30 < 36 e conclua que nenhum desses comprimentos é quadrado. Só então generalize para p qualquer, com p^2 < p^2 + t \le p^2 + p < (p+1)^2 = p^2 + 2p + 1.
Se sobrar espaço no bloco, o caso dos primos é o que mostra que o expoente pode depender de tudo o que veio antes. Com p = 4, escolha o primo q = 7, que é maior ou igual a p + 2 = 6; bombeie com i = q + 1 = 8 e obtenha comprimento q(1+t); para t = 3, isso dá 7 \times 4 = 28, composto. Diga em voz alta o que isso autoriza: o quantificador do expoente vem por último, portanto ele pode depender de p, de q e da decomposição.
Bloco seguinte — o que o lema não diz
Este bloco separa quem entendeu de quem memorizou, e é curto. O lema é condição necessária, não suficiente: regular implica bombeável, e não o contrário. Portanto fracassar em bombear não demonstra regularidade — demonstra apenas que a ferramenta não serviu.
Apresente a linguagem que passa no teste sem ser regular, aquela em que a restrição só vale quando o bloco inicial tem exatamente um símbolo. Não faça a verificação por casos inteira no quadro; ela está no livro do módulo e consome o bloco. Faça um caso só, o mais ilustrativo: com o bloco inicial de tamanho um, tomar y igual a esse único símbolo e bombear com zero remove-o, caindo no caso em que nada é exigido, e bombear com dois ou mais também escapa da restrição. Diga que os demais casos seguem o mesmo padrão e que a propriedade vale com comprimento de bombeamento igual a dois.
Então apresente Myhill-Nerode como a ferramenta que fecha a lacuna, em tratamento conceitual: uma linguagem é regular exatamente quando o número de classes de prefixos indistinguíveis é finito. Aplique aos parênteses em duas linhas — os prefixos (, ((, ((( são distinguíveis dois a dois, porque cada um exige um número diferente de fechamentos — e feche com a frase que vale o bloco: os estados de um autômato mínimo são as distinções que a linguagem obriga a fazer, uma por classe, o que explica de uma vez por que o mínimo é único e por que a minimização do módulo anterior encontra sempre o mesmo objeto.
Bloco de demonstração ao vivo — a teoria em números medidos
Abra o projeto de referência e execute na frente da turma; este bloco não funciona narrado. Duas execuções, nesta ordem.
A primeira é o lema na forma direta, sobre uma linguagem que é regular. Rode a decomposição sobre o autômato do número, que tem cinco estados, com a cadeia 123456. A saída dá o estado repetido após um e após dois símbolos, e a decomposição x = 1, y = 2, z = 3456. Confira as três condições em voz alta com a turma: y tem comprimento um, portanto não é vazio; |xy| = 2, dentro dos cinco estados; e todas as potências são aceitas, inclusive a de expoente zero, que produz 13456 — mostre essa em particular, porque bombear com zero remove o trecho e é o caso que mais confunde.
A segunda é o experimento do aninhamento, e é o fechamento do módulo. Rode o pipeline do módulo anterior sobre a expressão que cobre parênteses até profundidade k, para k de um a oito, e projete a tabela: os estados do autômato mínimo saem 3, 5, 7, 9, 11, 13, 15, 17, e a coluna da direita dá “não” em todas as linhas. Conduza a leitura em três tempos. Primeiro, funciona — para cada k o autômato aceita corretamente a profundidade k, e não há defeito a caçar. Segundo, os estados crescem como 2k + 1, dois por nível, que é a memória sendo gasta para contar; amarre isso ao bloco anterior, porque são as classes de equivalência sendo distinguidas uma a uma. Terceiro, e é a resposta: falha sempre em k + 1, e como para todo k existe k + 1, nenhum valor resolve.
Diga explicitamente o que o experimento não faz. Ele não prova nada — oito falhas não excluem a nona. Ele revela o padrão; a demonstração transforma padrão em impossibilidade. Entregar só um dos dois é entregar metade do argumento, e essa frase é literalmente o critério de correção da entrega deste módulo.
Bloco de fechamento — apagar o ponto de interrogação
Volte ao canto do quadro onde está a palavra da abertura e apague o ponto de interrogação na frente da turma. Peça que alguém dite a demonstração dos parênteses de memória, e escreva o que for ditado, corrigindo apenas as trocas de turno.
Feche com a divisão de trabalho que o módulo estabelece, porque é ela que o próximo bloco do semestre vai herdar. Tudo o que é regular na linguagem de cada grupo — nomes, números, textos, pontuação — fica com a análise léxica do módulo 7 e já está resolvido pelo motor pronto. Tudo o que é aninhado sobe para a análise sintática, e sobe por impossibilidade demonstrada. Diga a última frase devagar: no módulo 1 a separação entre análise léxica e sintática foi apresentada como decomposição clássica e podia parecer convenção; hoje ela tem demonstração.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — demonstração formal da não regularidade de uma construção da própria linguagem, experimento com a ferramenta do módulo anterior e a articulação entre os dois.
O andaime aqui já é intermediário: você dá o objetivo e o critério de correção, e o caminho é do grupo. O que não afrouxa é o rigor — este é o módulo em que a correção deixa de ser sobre o resultado e passa a ser sobre o argumento, e a mudança precisa ser anunciada antes da primeira sessão, não descoberta na devolutiva.
Tenha o projeto de referência aberto e rodando durante as duas sessões. A construção não regular da Peneira é a condição composta do where, em que uma comparação pode conter outra entre parênteses sem limite de profundidade — reduzida ao essencial, os parênteses balanceados. Mostre isso já no começo: o grupo que vê a construção do professor apontada dentro de uma linguagem concreta encontra a sua em minutos; o grupo que só ouve “identifiquem uma construção não regular” passa a sessão inteira procurando.
Primeira sessão de tutoria — achar a construção e escrever o esqueleto da prova
Abra projetando o critério de correção da demonstração, item por item, e leia em voz alta. Quem escolhe o comprimento de bombeamento, quem escolhe a cadeia, quem escolhe a decomposição, quem escolhe o expoente. Diga que demonstração com a ordem trocada volta para correção e que a conclusão certa não salva o argumento errado. Custa pouco e evita a conversa desagradável da devolutiva.
A primeira metade da sessão é achar a construção. Circule com uma pergunta única e repita-a igual em todos os grupos: “mostre onde a sua linguagem permite uma construção dentro de outra do mesmo tipo, sem limite de profundidade”. Quase todos respondem apontando expressão aritmética entre parênteses, condição composta ou bloco dentro de bloco. Se o grupo travar, mande-o reler o contrato de capacidades aprovado no módulo 1, que exige exatamente isso — a construção está lá, aprovada por eles mesmos.
O grupo que insiste que a linguagem dele não tem aninhamento merece atenção imediata, e o diagnóstico é binário. Ou o aninhamento existe e não foi visto, e você o aponta; ou ele realmente não existe, e nesse caso o problema não é deste módulo — é uma linguagem que degenerou em formato de configuração ao longo dos módulos 2 a 5, e a correção é acrescentar a construção recursiva agora, enquanto ainda cabe, e não no módulo 8, quando a gramática já estiver escrita.
A segunda metade é escrever o esqueleto da demonstração, não a demonstração. Exija cinco linhas em ordem, uma por passo: suponha regular e receba n; exiba w em função de n; derive a forma de y da condição de localização; exiba o expoente; conclua a contradição. Feche a sessão passando de grupo em grupo e jogando a partida contra a cadeia que cada um escolheu — você é o Adversário e escolhe a decomposição que mais atrapalha. Toda cadeia mal escolhida cai nesse teste em segundos, e cai aqui, quando corrigir custa uma linha.
Segunda sessão de tutoria — o experimento e a articulação
Comece pelo experimento, porque ele é rápido e porque a articulação depende de ele estar feito. Cada grupo escreve a expressão regular que tentaria usar para a construção aninhada, cobrindo profundidade até um valor escolhido, roda o pipeline do módulo anterior e registra em tabela o tamanho do autômato obtido e o resultado nos dois testes de fronteira. Projete a tabela da referência como formato esperado, não como resultado a reproduzir: os números do grupo serão outros, e devem ser.
O erro de execução mais comum é testar só a profundidade coberta e comemorar que funcionou. Circule perguntando a mesma coisa em todos os grupos: “e um nível a mais?”. A segunda coluna é o experimento; a primeira é só a verificação de que não há defeito de implementação.
A metade final da sessão é a articulação, e é o item que mais falta nas entregas. Exija um parágrafo que diga, com todas as letras, o que cada peça estabelece e o que não estabelece — o experimento mostra como falha e não prova nada, porque oito falhas não excluem a nona; a demonstração mostra que sempre falhará, para toda expressão e toda implementação. Grupos entregam as duas partes lado a lado sem essa costura, e o documento fica com cara de dois trabalhos grampeados. Recuse assim mesmo e mande costurar na hora, enquanto você está na sala para conferir.
Mantenha o revezamento de papéis mesmo sendo um módulo de escrita, e verifique-o de fato: quem digita é o piloto, quem lê e questiona é o navegador, e trocam a cada item concluído. Aqui o navegador tem função técnica real — a leitura em voz alta da demonstração pelo integrante que não a escreveu é o melhor detector de troca de quantificador que existe, melhor do que a sua correção, porque acontece antes.
O fechamento, e o que registrar
Feche o módulo exigindo de cada grupo uma frase escrita no diário: qual parte da linguagem deles não é regular e onde ela será tratada. Essa frase é o vínculo com os módulos 7 a 10 e é o que impede que o resultado deste módulo fique guardado como episódio isolado.
Anote, por grupo, duas coisas. A primeira é se a demonstração fechou na sessão ou voltou para correção — no módulo 8 essa informação prediz quem vai argumentar mal sobre ambiguidade. A segunda é quem escreveu a demonstração; se for sempre o mesmo integrante, o desequilíbrio que você mediu no módulo 1 continua lá, e o marco de consolidação do módulo 7, em que a compreensão precisa ser demonstrável por qualquer integrante, está a uma semana de distância.
Entregáveis e Avaliação
A entrega do módulo é um documento com quatro partes: a demonstração formal de que alguma construção da linguagem do grupo não é regular, o registro do experimento com a ferramenta do módulo anterior, a articulação explícita entre os dois e a conclusão sobre o que isso impõe aos módulos seguintes. Acompanha o código usado no experimento.
Corrija a demonstração pela estrutura, não pela conclusão. Confira, na ordem: o comprimento de bombeamento é recebido e não escolhido; a cadeia é exibida em função dele e pertence à linguagem; a decomposição é tratada como arbitrária, com a forma de y deduzida da condição de localização; o expoente é exibido e a cadeia resultante é mostrada fora da linguagem; e a conclusão é a contradição, não a afirmação direta. Demonstrações com a ordem dos quantificadores trocada retornam para correção, mesmo quando a conclusão está certa — e diga isso à turma antes da primeira sessão de tutoria, não depois da entrega.
No experimento, exija número medido e não impressão. A tabela precisa ter, por profundidade coberta, o tamanho do autômato obtido e o resultado nos dois testes de fronteira; um relato em prosa dizendo “não funcionou” não é registro de experimento. E exija a articulação em parágrafo próprio, dizendo o que cada peça estabelece e o que não estabelece: é o item que mais falta e é o que se avalia.
Registre no componente contínuo a pontualidade, a contribuição nas duas discussões em duplas da aula teórica e o engajamento nas atividades colaborativas da tutoria. Deixe claro, aqui como no módulo 1, que a entrega deste módulo não acrescenta capacidade ao compilador de ninguém, e que isso está certo: o que se entrega é conhecimento sobre a fronteira, e é ele que torna o bloco seguinte necessário em vez de arbitrário.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as duas votações, com a projeção anônima. A questão sobre quem escolhe o quê é a mais informativa do semestre até aqui: guarde os dois histogramas e olhe especificamente a fatia da alternativa que descreve o erro dominante. Se ela continuar alta no segundo voto, a discussão em duplas não corrigiu — o que significa que não há massa crítica de quem entendeu, e a resposta certa é refazer a partida no quadro com uma cadeia nova antes de seguir, e não explicar de novo com as mesmas palavras.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. Este módulo tem uma assinatura própria e vale conhecê-la: como não há código novo a escrever no projeto de cada grupo, o engajamento costuma cair em relação ao módulo anterior mesmo em turmas que estão indo bem. Não leia essa queda como desinteresse sem cruzar com a qualidade das demonstrações entregues; leia como o sinal de que o módulo é de escrita, e reforce isso na primeira sessão de tutoria.
Pontos de Atenção Específicos
O aceno de cabeça é enganoso. Este é o módulo em que a turma mais concorda e menos entende. A ideia da casa dos pombos é fácil, a conclusão é intuitiva, e todo mundo assente. O que não passa é a disciplina lógica, e ela só se revela quando alguém escreve. Não confie na expressão da sala: confie no histograma da segunda questão e nas demonstrações da tutoria.
Não ceda à demonstração completa de indecidibilidade nem à de Myhill-Nerode. As duas são pedidas com frequência, sobretudo por quem está mais adiantado, e as duas consomem um bloco inteiro. Trate Myhill-Nerode conceitualmente, como o plano prevê, e mostre o poder dela pelo exemplo que derruba a linguagem que passa no bombeamento. Quem quiser mais tem o livro do módulo.
Cuidado com a leitura “é um limite que dá para aumentar”. É a conclusão errada mais frequente do experimento, e ela aparece disfarçada de bom senso de engenharia: mais memória, mais estados, uma notação melhor. Corte na hora e seja específico — o limite não é da implementação, não é do ambiente e não é da notação; é do modelo, e nenhuma implementação de autômato finito, em nenhuma linguagem, com qualquer quantidade de memória, resolve isto.
Grupos que programam bem subestimam este módulo. É o ponto de atenção número um da tutoria. Um grupo acostumado a entregar código vê um módulo de escrita e conclui que é leve; produz meia página apressada na última sessão e descobre na correção que a demonstração não fecha. Antecipe isso na abertura da primeira sessão, com o critério de correção projetado, e exija o esqueleto da demonstração ainda na primeira sessão em vez de na última.
Aceitar uma prova “quase certa” custa o semestre inteiro. Este é o primeiro módulo com exigência de rigor formal, e o padrão que você estabelecer aqui é o que vale nos módulos 8 a 11, quando a turma tiver de argumentar sobre ambiguidade e sobre conflitos de tabela. Devolver uma demonstração incompleta para correção é desconfortável uma vez; não devolver é conviver com argumentação frouxa até dezembro.
A escolha da construção pode não ser óbvia em algumas linguagens. Um grupo ou outro vai insistir que a linguagem dele não tem aninhamento. Quase sempre tem, e está escondido na expressão aritmética ou na condição composta; se realmente não tiver, o problema não é deste módulo, é do contrato de capacidades aprovado no módulo 1, e a correção é acrescentar a construção que se contenha, não dispensar a demonstração.