flowchart LR
M1["Módulo anterior<br/>panorama das fases<br/>e mapa da hierarquia"] --> M2["Este módulo<br/>cadeias, linguagens<br/>e expressões regulares"]
M2 --> D["Descrever conjuntos infinitos<br/>com texto finito"]
D --> P["Falta reconhecer<br/>a notação é declarativa"]
P --> M3["Módulo seguinte<br/>a máquina de memória finita"]
M2 --> PI["Entrega do grupo<br/>especificação léxica<br/>com corpora de fronteira"]
PI --> M3
Módulo 02: Plano de Aula — Alfabetos, Linguagens e Expressões Regulares
Documento exclusivo do professor. Este é o guia operacional das seis aulas do módulo 2: roteiro por blocos das duas aulas teóricas, plano das quatro aulas de tutoria, entregáveis e riscos antecipados. Não distribua à turma — as questões de discussão perdem função assim que o estudante conhece as alternativas antes da aula, e as cadeias de fronteira guardadas para a tutoria só revelam a especificação frouxa quando são surpresa.
Visão Geral do Módulo
Onde este módulo fica — o vocabulário formal que os quatro módulos seguintes vão consumir sem reapresentar.
O módulo anterior tinha por critério de sucesso que o estudante situasse; este tem por critério que ele opere. A mudança de registro é deliberada e precisa ser anunciada à turma na abertura, porque a turma não a percebe sozinha e interpreta a densidade formal como aumento arbitrário de exigência. Ao fim das duas aulas teóricas, espera-se que o estudante leia e escreva expressões regulares com fluência, demonstre equivalências simples por manipulação algébrica sem recorrer a autômatos — que ainda não existem para nós — e olhe para uma construção de biblioteca dizendo se ela é açúcar sobre a teoria ou se pulou a cerca.
Há uma tentação a resistir aqui, e ela é o inverso da do módulo anterior. Lá o risco era degenerar em lista; aqui é degenerar em formalismo por si mesmo, uma sucessão de definições que ninguém consegue usar. O antídoto é que cada definição deste módulo tem um caso concreto que a testa, e o caso vem antes ou logo depois da definição, nunca no fim da aula. A distinção entre o conjunto vazio e o conjunto que contém a cadeia vazia não se ensina enunciando: ensina-se pedindo o valor do fecho de Kleene do conjunto vazio e deixando a turma errar.
Do lado do Projeto Integrador, este é a última entrega puramente documental do semestre: do módulo 3 em diante há código a manter, e a especificação léxica escrita aqui é o critério de verificação consumido sem alteração até o módulo 5. Um grupo que sai daqui com especificação frouxa não tem como saber, três módulos adiante, se o reconhecedor que construiu está correto ou apenas roda.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Estabelecer o vocabulário formal sobre o qual toda a primeira metade da disciplina será construída. Levar o estudante da familiaridade prática com expressões regulares à compreensão de sua definição formal e de suas propriedades algébricas. Distinguir a classe das linguagens regulares das notações que apenas se parecem com ela.
Competências a desenvolver. Capacidade de operar com definições formais recursivas, entendendo a semântica de uma notação a partir da estrutura sintática que a produz. Capacidade de reconhecer, numa ferramenta de uso cotidiano, a teoria que a fundamenta e os limites que decorrem dela.
Habilidades a adquirir. Manipular cadeias e linguagens com as operações definidas. Ler e escrever expressões regulares com fluência. Demonstrar equivalências simples entre expressões por manipulação algébrica, sem recorrer a autômatos. Identificar, em uma notação de biblioteca, quais construções extrapolam a classe regular.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a sequência é ascendente em três degraus: cadeias, linguagens, expressões. Nenhum degrau se sustenta sem o anterior.
Bloco de abertura — duas expressões, o mesmo conjunto, custos diferentes
Chegue com duas expressões projetadas lado a lado, sem título e sem explicação: a^*b e (a^*)^*b. Peça duas coisas à turma, nesta ordem, e não inverta.
A primeira: as duas descrevem o mesmo conjunto de cadeias? A sala vai hesitar, e a hesitação já é informação — quem aprendeu expressões regulares por imitação não tem como responder, porque nunca houve modelo. Recolha as hipóteses no quadro sem julgá-las e diga apenas que a resposta é sim, e que a álgebra que demonstra isso será construída na segunda aula.
A segunda: submetidas as duas à mesma entrada — trinta letras a e nenhum b —, uma delas pode levar a busca a travar. Qual, e por quê? Aqui não dê resposta alguma. Diga que a pergunta será paga no último bloco da segunda aula e que a resposta envolve uma interrupção mundial de serviço documentada publicamente. A dívida declarada segura melhor do que a resposta imediata, e esta costuma fazer alguém procurar o assunto por conta própria entre as duas aulas.
Feche o bloco escrevendo três palavras no canto do quadro e não as apague durante as duas aulas: conjunto, notação, estratégia. Para explicar por que duas expressões que descrevem o mesmo conjunto têm custos diferentes é preciso ter as três, e ainda não temos nenhuma.
Bloco seguinte — os objetos elementares e a estrutura que eles formam
Comece pelo fundo da abstração, rápido e sem cerimônia, mas sem pular as duas exigências que fazem trabalho pesado adiante. Alfabeto é conjunto finito e não vazio; diga em voz alta que a finitude não é detalhe de arrumação, e sim a hipótese de que dependem praticamente todos os resultados deste andar — um alfabeto infinito não quebra a implementação, quebra os teoremas. Cadeia é sequência finita de símbolos, com \varepsilon de comprimento zero, e registre desde já que \Sigma^0 = \{\varepsilon\} e não \emptyset.
A concatenação merece a maior parte do bloco, porque tudo se apoia nela: associativa, com \varepsilon como elemento neutro, e não comutativa — sobre \Sigma = \{a,b\} basta ab \ne ba. Amarre com o nome próprio: \Sigma^* com a concatenação é um monoide livre, e “livre” significa que não há igualdade entre cadeias além das que os axiomas impõem, de modo que uma cadeia carrega exatamente a informação da sequência que a compõe.
Faça no quadro uma demonstração por indução, sobre um enunciado cujo resultado a turma já conhece: \lvert uv \rvert = \lvert u \rvert + \lvert v \rvert. Caso base u = \varepsilon, com uv = v; passo escrevendo u = a u', de onde \lvert uv \rvert = 1 + \lvert u'v \rvert = 1 + \lvert u' \rvert + \lvert v \rvert pela hipótese. Diga por que está demonstrando algo tão óbvio: a forma do argumento — caso base na cadeia vazia, passo que retira o primeiro símbolo — é a de quase toda demonstração dos próximos quatro módulos, e vale internalizá-la agora, quando a atenção não está ocupada com o conteúdo.
Feche com a enumeração de abc, feita no quadro e não projetada. Prefixos: \varepsilon, a, ab, abc — quatro, que é n+1. Sufixos: \varepsilon, c, bc, abc — quatro pelo mesmo motivo. Subcadeias distintas: \varepsilon, a, b, c, ab, bc, abc — sete, e faça a turma notar que ac não está. Depois vá a aaa: a subcadeia aa ocorre em duas posições e é uma só. Contar ocorrências não é contar objetos distintos, e a maneira segura de não errar é coletar num conjunto.
Primeira questão de discussão em duplas. “Sobre a cadeia abc, a cadeia ac é: (a) subcadeia e subsequência; (b) subsequência, mas não subcadeia; (c) subcadeia, mas não subsequência; (d) nenhuma das duas.”
Voto individual primeiro, sem comentário seu; discussão em duplas; segundo voto. A resposta é (b). Quem vota (a) não reteve a exigência de contiguidade e é a maioria no primeiro voto. Quem vota (d) leu contiguidade nas duas definições. Feche com a consequência que interessa à disciplina: praticamente toda categoria léxica de linguagem de programação exige contiguidade — os símbolos de um identificador são adjacentes no texto —, e essa é uma das razões pelas quais o formalismo regular basta para descrevê-las. Não revele a resposta antes da discussão em duplas.
Bloco seguinte — linguagens, e as duas caixas que a turma confunde
Suba de nível com a definição mais generosa do módulo: uma linguagem sobre \Sigma é um subconjunto qualquer de \Sigma^*. Explore a generalidade em voz alta, porque a turma não a vê sozinha — o conjunto dos identificadores válidos é uma linguagem, o dos programas sintaticamente corretos é uma linguagem sobre outro alfabeto, o dos programas que terminam também é. A única diferença que a teoria enxerga entre elas é a dificuldade de decidir a pertinência.
Então pare tudo e trate a confusão número um do módulo. Escreva \emptyset e \{\varepsilon\} lado a lado no quadro: o primeiro não tem elemento algum, o segundo tem um. Um reconhecedor de \emptyset rejeita toda entrada, inclusive a vazia; um de \{\varepsilon\} rejeita todas exceto a vazia. Use a imagem da caixa fechada e vazia contra a caixa com uma folha em branco dentro — a folha em branco é uma coisa, a ausência de folha é outra.
Passe às operações com exemplos numéricos resolvidos no quadro, um por operação. Para a concatenação, tome L_1 = \{a, ab\} e L_2 = \{b, \varepsilon\}: há quatro pares, e o resultado é \{a, ab, abb\}, com três elementos, porque (a,b) e (ab,\varepsilon) produzem a mesma cadeia — o mesmo fenômeno das subcadeias de aaa, um nível acima.
Escreva juntas as identidades do neutro e do absorvente, porque é a troca entre elas que produz as falsas demonstrações da segunda aula: \{\varepsilon\}L = L, porque concatenar a cadeia vazia com cada cadeia devolve a própria; e \emptyset L = \emptyset, porque não há cadeia alguma para começar o par.
Para a falha da distributividade sobre a interseção, faça a conta inteira, que é curta e convence: com L = \{a, aa\}, L_1 = \{a\} e L_2 = \{aa\}, o lado esquerdo é vazio porque L_1 \cap L_2 = \emptyset; já LL_1 = \{aa, aaa\} e LL_2 = \{aaa, aaaa\}, cuja interseção contém aaa. A razão do fracasso é a ideia a carregar: aaa é produzida à esquerda por aa \cdot a e à direita por a \cdot aa, decomposições que a concatenação não distingue, porque ela perde a fronteira. Avise que essa perda reaparece na ambiguidade de gramáticas.
Chegue às potências e aos fechos e faça a turma derivar, não decorar. L^0 = \{\varepsilon\} para toda linguagem, inclusive L = \emptyset, e a defesa não é convenção: se fosse L^0 = \emptyset, então L^1 = L^0L = \emptyset para toda linguagem, o que é absurdo. Ofereça também a leitura combinatória, que costuma ser a que convence: há exatamente uma maneira de concatenar zero cadeias — não fazer nada —, e o resultado dela é a cadeia vazia.
Segunda questão de discussão em duplas. “Qual é o valor de \emptyset^*, o fecho de Kleene do conjunto vazio? (a) \emptyset; (b) \{\varepsilon\}; (c) \Sigma^*; (d) indefinido, porque não há cadeia a concatenar.”
A resposta é (b), e esta é a questão que mais separa quem entendeu de quem decorou — espere maioria em (a) no primeiro voto. O argumento a extrair do segundo voto é o da definição: \emptyset^* = \bigcup_{n\ge 0}\emptyset^n, e a parcela n = 0 vale \{\varepsilon\}, enquanto todas as demais são vazias. Aproveite para escrever o contraste ao lado, porque ele fixa: \emptyset^+ = \emptyset, porque a união começa em n = 1. Quem vota (d) percebeu a estranheza e concluiu que a definição falha; é o erro mais interessante e o melhor gancho para dizer que a definição foi escolhida justamente para não falhar em caso algum.
Bloco de fechamento da primeira aula — quase toda linguagem é indescritível
Termine a primeira aula com o argumento de contagem, que é curto e reorganiza o problema. O conjunto \Sigma^* é infinito enumerável; a coleção dos seus subconjuntos, pela diagonalização de Cantor, tem a cardinalidade do contínuo; já uma descrição finita é uma cadeia finita sobre um alfabeto finito de notação, e essas formam uma coleção enumerável. Não há função sobrejetora de um conjunto enumerável sobre um não enumerável, e portanto qualquer sistema de descrição finita deixa linguagens de fora — quase todas.
Não conte isso para desanimar; conte para trocar a pergunta. Ela deixa de ser “como descrever qualquer linguagem”, que é impossível, e passa a ser “que classe vale a pena poder descrever, e com que notação”. Encerre aí: é a melhor pendência que se pode deixar entre as duas aulas, porque a resposta é o assunto inteiro da segunda.
Bloco de abertura da segunda aula — seis construtores e nada mais
Retome pela pergunta pendente, não por resumo. A resposta é uma notação minúscula, e a surpresa a explorar é o tamanho dela: três casos-base — o conjunto vazio, a cadeia vazia, cada símbolo do alfabeto — e três construtores — união, concatenação, estrela. Seis. Diga que tudo o que a turma já viu em uma ferramenta de busca ou é abreviação escrita em termos desses seis, ou não é expressão regular coisa nenhuma.
Faça a advertência de notação, porque a confusão é real e persistente: \emptyset e \varepsilon aparecem aqui como elementos da sintaxe, caracteres que se escrevem, e apareceram na primeira aula como objetos semânticos. Mesmo desenho, naturezas diferentes. Adote em voz alta o hábito de dizer “a expressão \varepsilon” ou “a cadeia \varepsilon”, e cobre isso da turma.
Escreva a precedência — estrela, depois concatenação, depois união — e verifique com os dois casos que apanham todo mundo: ab^* é a(b^*) e não (ab)^*; a \mid bc é a \mid (bc) e não (a\mid b)c.
Passe à semântica e apresente-a pelo que ela é: seis igualdades, com operações sobre sintaxe à esquerda e operações sobre conjuntos à direita, uma para cada construtor. O ponto a martelar é a composicionalidade — o significado do todo depende apenas do das partes —, porque é ela que dará forma a todos os algoritmos dos próximos módulos: um caso por construtor, cada caso combinando os resultados dos filhos.
Exercite a definição uma vez com todo o cuidado, no quadro. Tome r = (a\mid b)^*a sobre \Sigma = \{a,b\} e desdobre passo a passo: L(r) = L((a\mid b)^*)L(a) = (\{a\}\cup\{b\})^*\{a\} = \{a,b\}^*\{a\}, que é o conjunto das cadeias terminadas em a. Faça a turma verificar duas coisas: que \varepsilon \notin L(r), porque toda cadeia do conjunto tem ao menos o a final; e que a cadeia a está no conjunto, obtida tomando a cadeia vazia do fecho seguida do a — é aqui que a distinção da primeira aula paga, porque sem a cadeia vazia no fecho a expressão descreveria outra coisa.
Bloco seguinte — açúcar sintático e a leitura da expressão como árvore
Apresente as formas derivadas como o que elas são: abreviações eliminaveis. O sinal de mais é rr^*; a interrogação é (r\mid\varepsilon); a classe entre colchetes é união finita de símbolos; o ponto é a união de todos os símbolos do alfabeto. Registre o preço da eliminação: uma classe de vinte e seis letras vira vinte e cinco uniões, e um contador de cinquenta repetições vira cinquenta cópias. Preço de tamanho, não de poder.
Dê a decisão de projeto que decorre disso, porque ela será cobrada dos grupos a partir do módulo 4: represente apenas os seis construtores na estrutura de dados e monte as formas derivadas em termos deles. Acrescentar um caso ao tipo enumerado para o sinal de mais parece economizar uma composição e custa caro no módulo seguinte, quando o algoritmo de construção da máquina tiver de tratar doze casos em vez de seis.
Então incuta o hábito que mais rende no módulo: ler expressão como árvore, não como texto da esquerda para a direita. Tome no quadro a expressão de um número com sinal opcional, parte inteira obrigatória e parte fracionária opcional. Lida como estrutura, é uma concatenação de três filhos: um opcional com o sinal; um fecho positivo de dígitos; um opcional contendo ponto seguido de fecho positivo de dígitos. Desenhada assim, resolva as perguntas na frente da turma, sempre pela expressão e nunca pela intenção.
A expressão aceita a cadeia vazia? Só se os três fatores puderem produzi-la; o primeiro pode, o terceiro pode, o segundo não, por ser fecho positivo. Logo não aceita — e avise que esse raciocínio, trivial aqui, é o cálculo de anulabilidade que aparecerá algoritmicamente no módulo 12. Aceita uma cadeia que começa pelo separador decimal, ou dígito seguido de separador e nada depois? Não e não, porque a parte inteira é obrigatória e a fracionária, quando presente, exige ao menos um dígito. Aceita zeros à esquerda? Sim, e isso é decisão de quem escreveu, não descuido — desde que registrada. Aceita sinal positivo? Não, porque o opcional contém apenas o de menos, e a assimetria precisa estar anotada sob pena de parecer erro.
Terceira questão de discussão em duplas. “Considere as construções que uma biblioteca de busca oferece. Qual delas não pode ser reescrita usando apenas os seis construtores da definição? (a) o quantificador de uma ou mais repetições; (b) a classe de caracteres com faixa; (c) o retrovisor, que exige que um trecho já casado reapareça idêntico; (d) o ponto que casa qualquer símbolo.”
A resposta é (c). As outras três são açúcar, e vale reconstruir a expansão de cada uma no segundo voto. O argumento sobre o retrovisor é o mesmo que separou os dois andares inferiores da hierarquia no módulo anterior: reconhecer exige lembrar um trecho de comprimento ilimitado, e a memória de um reconhecedor da classe regular é fixada antes de a entrada ser vista. Registre a consequência que costuma surpreender: a linguagem das cadeias formadas por um trecho repetido duas vezes não é regular e não é sequer livre de contexto.
Bloco de construção ao vivo — a notação inteira em código
Este é o bloco de code-along, e o roteiro é curto de propósito, porque a estrutura recursiva é o conteúdo e o resto é digitação. Avise para abrir o editor e digitar junto, pause ao fim de cada peça e circule para conferir — não pergunte “todo mundo conseguiu”, que sempre recebe silêncio afirmativo.
A primeira peça é o tipo da expressão com exatamente seis casos, e as formas derivadas construídas em termos deles. Verbalize, ao digitar, a decisão de compartilhar a subárvore em vez de duplicá-la: quando o sinal de mais é montado como r seguido de r^*, a mesma subárvore aparece dos dois lados, e apontar duas vezes para ela é a escolha certa por razão estrutural.
A segunda peça é a função que calcula a linguagem denotada, digitada com o quadro à vista, um caso por construtor, na mesma ordem da definição escrita no bloco anterior. O objetivo é que a turma veja a mesma coisa em duas notações; diga isso em voz alta, porque nem todo mundo percebe.
A terceira peça é o limite de comprimento, que não é detalhe de implementação: é o que garante a terminação. Sem limite, o laço do fecho não para para nenhuma linguagem que contenha cadeia não vazia. Nomeie a insuficiência — o que se calcula aqui é uma fatia da linguagem, uma janela sobre o conceito, não o conceito.
Termine rodando a bateria de verificação de identidades e note em voz alta o terceiro caso: além dos dois que devem conferir, incluímos um que deve divergir. Uma bateria em que tudo passa não prova que a verificação funciona — pode ser que ela sempre responda “confere”.
Bloco seguinte — a álgebra e o que ela não consegue fazer
Monte no quadro apenas as identidades que se usam para raciocinar, não a tabela inteira: os neutros e absorventes, a distributividade sobre a união, o desdobramento do fecho r^* \equiv \varepsilon \mid rr^* e a idempotência r^{**} \equiv r^*. Diga que o desdobramento é a forma recursiva do fecho e a base do algoritmo que constrói autômatos a partir de expressões, e que a idempotência será a chave do último bloco.
Faça uma demonstração inteira, e escolha (r\mid s)^* \equiv (r^*s^*)^*, porque as duas inclusões têm dificuldades diferentes. Escreva A = L(r) e B = L(s). Da esquerda para a direita: toda w é concatenação de cadeias w_i, cada uma em A ou em B; se w_i \in A, então w_i \in A^*B^* tomando a parte de B vazia. Pare exatamente aqui e aponte o dedo para o passo: precisamos de \varepsilon \in B^* para que isso funcione, e sem a cadeia vazia no fecho a inclusão falharia. É a melhor evidência disponível de que a distinção martelada na primeira aula é o que faz as demonstrações fecharem.
Feche o bloco com a limitação, que é o ponto mais importante dele. A manipulação algébrica é excelente para demonstrar equivalências e péssima para refutá-las: não achar o caminho não demonstra que as expressões diferem. Para refutar, o instrumento é outro — exibir uma cadeia que pertence a uma linguagem e não à outra. Uma cadeia é uma testemunha, e uma testemunha encerra a questão.
Três fatos completam o quadro e devem ser dados com autoria e data, porque é isso que os torna verificáveis pela turma. Redko demonstrou, em 1964, que nenhum conjunto finito de identidades puramente equacionais é completo para a equivalência de expressões regulares; Salomaa obteve sistemas completos em 1966, acrescentando uma regra de inferência com hipótese. A regra de Arden, apresentada por Dean Arden em 1961, resolve X = AX \cup B com solução única X = A^*B quando \varepsilon \notin A — e a hipótese é necessária: com A = \{\varepsilon\} e B = \emptyset, qualquer X satisfaz a equação. E decidir se duas expressões denotam a mesma linguagem é decidível, mas PSPACE-completo, resultado de Stockmeyer e Meyer publicado em 1973.
Extraia a consequência metodológica, que a turma vai precisar na hora de confiar demais no programa do bloco anterior: concordância até um comprimento dado é evidência, não demonstração — duas expressões podem coincidir até o comprimento dez e divergir no onze. A decisão de verdade chega no módulo 5, com a unicidade do autômato mínimo.
Bloco de fechamento — a fronteira, e a volta ao gancho
Volte ao quadro da abertura e pague a dívida, na ordem em que ela foi contraída.
Primeiro, o lado de dentro: quantificadores, contadores, classes com faixa e negação, ponto, classes nomeadas, agrupamento e alternação. Todos são açúcar, e o critério cabe numa pergunta — isto pode ser expandido nos seis construtores?. Trate as âncoras de início e fim de texto como o caso interessante: falam sobre posição e não sobre a cadeia, mas o que expressam continua na classe regular, e existem porque a maioria das bibliotecas resolve o problema de busca e não o de reconhecimento. Num compilador, em que se reconhece um lexema completo a partir de uma posição, elas não fazem falta.
Depois o lado de fora, em três famílias. Retrovisores, pelo argumento da memória ilimitada já trabalhado na terceira questão; registre que Alfred Aho, no capítulo sobre algoritmos de busca de padrões em cadeias do Handbook of Theoretical Computer Science, publicado em 1990, consignou que decidir se uma cadeia casa com um padrão contendo retrovisores é NP-completo. Olhares adiante e atrás em versão geral. E construções recursivas, que nem fingem — são um mecanismo de pilha dentro da notação de padrões, e o que descrevem vive no andar de cima da hierarquia.
Agora feche o gancho. Existem duas estratégias de reconhecimento: converter o padrão em máquina e passar a entrada uma vez, com tempo proporcional ao comprimento e independente da forma do padrão; ou retroceder, tentando alternativas e voltando quando falham. A segunda é a que suporta retrovisores e olhares, e é a que quase toda biblioteca de propósito geral adota. Com (a^*)^*b sobre trinta letras a e nenhum b, cada partição diferente dos a entre as duas repetições é uma alternativa distinta, e o reconhecedor por retrocesso as tenta todas antes de concluir que não há casamento. Pela idempotência do fecho, a expressão é equivalente a a^*b, reconhecida trivialmente. Mesma linguagem, mesma biblioteca, custos incomparáveis — a diferença está na estratégia combinada com a forma do padrão.
Termine com o caso real, que é o que a turma leva para casa: em 2 de julho de 2019, a Cloudflare publicou um relatório atribuindo uma interrupção global do seu serviço a exatamente esse fenômeno — uma regra recém-implantada continha um padrão com retrocesso catastrófico, e o consumo de processamento derrubou o serviço em escala mundial. A lição é de método, e vale enunciá-la olhando para as três palavras do canto do quadro: o defeito não estava no conjunto descrito, nem apenas na notação usada, e sim na combinação de uma notação que permite construções fora da classe regular com uma estratégia de reconhecimento que paga caro por certas formas de padrão. Quem conhece a fronteira prevê a categoria do problema; quem aprendeu por imitação, não.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — inventário das categorias léxicas da linguagem do grupo, notação precisa para cada uma e os dois corpora por categoria, com casos de fronteira escolhidos por serem difíceis.
A entrega deste módulo não tem código, e essa é a primeira coisa a dizer em voz alta na abertura da tutoria — porque metade dos grupos vai chegar querendo começar o analisador léxico, e o analisador léxico está cinco módulos adiante, sobre uma teoria que a turma ainda não tem. O que se avalia aqui é precisão de especificação, e só.
Tenha a especificação da sua própria linguagem projetada durante as duas sessões, com as seis categorias visíveis: nomes, números, textos entre aspas, padrões entre barras, sinais de pontuação e espaços. O grupo que vê o formato pronto — nome da categoria, notação, observação registrando a decisão de projeto, corpus de aceitação, corpus de rejeição — reproduz o formato de imediato. O grupo que só ouve a descrição da tarefa entrega prosa.
Primeira sessão de tutoria — inventariar as categorias e escrever a notação
Comece pelo inventário, e faça-o a partir do material que o próprio grupo já produziu: os programas de exemplo escritos na tutoria do módulo anterior. A instrução é literal e vale ditá-la — passem o dedo sobre cada caractere do exemplo e digam a que categoria ele pertence; o que sobrar sem categoria é categoria faltando. É um procedimento mecânico e é justamente por isso que funciona, enquanto “pensem nas categorias da linguagem de vocês” produz três categorias e esquece quatro.
Duas categorias somem em quase todo inventário e vale ir atrás delas antes que o grupo declare o inventário fechado. A primeira é o espaço em branco, que ninguém enxerga como símbolo por não ver nada no lugar — e é ele que informa onde um nome termina; sem espaço descrito, a especificação não diz o que separa duas palavras adjacentes. A segunda é o comentário, quando o grupo pretende ter comentários e não os escreveu no exemplo.
Fechado o inventário, proíba a prosa. A regra da sessão é que nada vai para o documento em forma de frase: cada categoria entra como expressão. Vai aparecer resistência, e o argumento que a desmonta é o teste da cadeia esquisita — escolha você a cadeia e peça ao grupo que a classifique. Se a resposta demorar, a especificação é frouxa; se a resposta vier de consultar a intenção original em vez da expressão escrita, a especificação está errada, porque o que vai valer quando o reconhecedor existir é a expressão.
Enquanto os grupos escrevem, projete três decisões da minha especificação e leia as observações em voz alta, porque são as três que os grupos vão reencontrar sozinhos e não vão saber resolver. A primeira: a categoria dos nomes casa também com as palavras reservadas da linguagem — a palavra que declara um padrão é um nome perfeitamente válido segundo a expressão que escrevi. Isso não é defeito e não se conserta agora; o desempate por prioridade é assunto do módulo 7, e o que se faz aqui é registrar o fato na observação para não parecer descuido a quem reler. A segunda: o literal de padrão é reconhecido como bloco opaco, de delimitador a delimitador, sem que a especificação olhe para o que há dentro — quem analisa o interior é outro módulo, e misturar as duas coisas produz uma especificação impossível de ler. A terceira: a pontuação inclui operadores de dois caracteres, e é essa decisão, e nenhuma outra, que cria a necessidade do casamento mais longo; sem ela, o operador de comparação com igualdade seria lido como dois sinais separados e a condição seria analisada errado sem que nada acusasse.
Feche a sessão com uma rodada rápida de leitura cruzada. Cada grupo entrega a especificação parcial ao grupo vizinho e recebe a do vizinho, e a tarefa é uma só: encontrar uma cadeia que a especificação alheia não classifica sem hesitação. Isso rende mais do que a sua correção individual grupo a grupo, e rende porque o leitor externo não tem acesso à intenção — é exatamente a situação em que a especificação vai ser usada.
Segunda sessão de tutoria — os corpora e os casos de fronteira
A segunda sessão é sobre os dois conjuntos por categoria, e o padrão de erro aqui é previsível: os grupos escrevem corpora fáceis. O corpus de aceitação vem cheio de casos típicos, o de rejeição vem cheio de coisas obviamente absurdas, e o conjunto inteiro não testa nada, porque qualquer expressão minimamente razoável passa nele.
Corrija isso com uma exigência numérica explícita, dada na abertura da sessão: pelo menos metade das cadeias de cada corpus tem de ser um caso de fronteira, e caso de fronteira é uma cadeia que quase satisfaz a especificação. Dê os meus como modelo, porque eles são concretos e cada um carrega uma decisão. Na categoria dos números eu rejeito a cadeia que começa pelo separador decimal sem dígito antes, e rejeito a que tem dígito antes e nada depois — as duas parecem número e nenhuma satisfaz a expressão, porque exijo pelo menos um dígito de cada lado. Aceito a cadeia com zeros à esquerda, e aceito de propósito: rejeitá-los exigiria uma expressão bem maior e não traz ganho para esta linguagem. Rejeito a notação científica, e a coloquei no corpus justamente porque é a extensão que todo mundo pede depois, e quero registrado que ela não faz parte da linguagem. E rejeito o sinal positivo enquanto aceito o negativo, o que é assimétrico e proposital — assimetria não registrada parece erro para quem lê depois.
A intervenção mais eficaz desta sessão não é apontar a falha na especificação alheia. É escolher você a cadeia e pedir que o grupo a classifique na hora, na frente da equipe inteira. A hesitação revela a indefinição melhor do que qualquer correção que você escreva. Tenha meia dúzia de cadeias prontas antes de entrar na sala, adaptadas ao domínio de cada grupo — a cadeia de tamanho zero, o sinal isolado, o separador decimal sem dígitos, o delimitador de texto que abre e não fecha, o nome que começa por dígito.
Circule cobrando o revezamento de papéis, e note que num módulo sem código a instituição do revezamento é mais fácil e igualmente necessária: quem escreve a expressão é o piloto, quem produz as cadeias de fronteira contra ela é o navegador, e os papéis trocam a cada categoria concluída. Esse arranjo tem uma vantagem própria — o navegador está tentando quebrar o que o piloto acabou de escrever, que é exatamente a postura que a tarefa pede.
Reserve o fim da sessão para o ponto que os grupos precisam ouvir explicitamente: os corpora ainda não são executáveis. Não existe reconhecedor, e não existirá neste módulo. Eles são contrato, escrito antes da implementação e de propósito. No módulo 3 o primeiro reconhecedor aparece e passa a consumi-los, e no módulo 5 a ferramenta completa os verifica todos. Escrever o teste antes do código não é formalidade aqui: é o que vai permitir, três módulos adiante, saber se o que foi construído está certo, em vez de apenas observar que roda.
O que conferir antes de aceitar a entrega
Confira cada especificação contra os mesmos itens, na mesma ordem, para todos os grupos. Toda “palavra” dos programas de exemplo do grupo cai em alguma categoria, sem sobra. Cada categoria está descrita por expressão e não por frase. Cada categoria carrega uma observação registrando a decisão de escopo que a acompanha. Cada corpus tem casos de fronteira em quantidade, e não apenas casos típicos. E não há categoria descrita por um padrão que exija lembrar conteúdo já lido — se aparecer uma, o grupo saiu da classe regular sem perceber, e essa é a conversa mais valiosa que você terá na tutoria inteira.
Registre no seu diário, por grupo, quais decisões de escopo foram cortadas e por quê. A lista mais frequente é conhecida: sequências de escape dentro de texto, notação científica em números, identificadores com maiúsculas e comentários aninhados. Cortar cedo é barato e mantém o semestre viável; o que não pode acontecer é o corte não estar registrado, porque no módulo 12 ninguém lembra se a ausência foi decisão ou esquecimento.
Entregáveis e Avaliação
A entrega do módulo é um documento e não tem código: a especificação léxica completa da linguagem do grupo, com todas as categorias descritas em notação de expressões regulares e, por categoria, o conjunto de cadeias que devem ser aceitas e o das que devem ser rejeitadas, com os casos de fronteira identificados como tais. Avalia-se a precisão da especificação, não o volume dela.
Confira cada entrega contra os mesmos itens, na mesma ordem, para todos os grupos: toda “palavra” dos programas de exemplo cai em alguma categoria, sem sobra; cada categoria está descrita por expressão e não por frase; cada uma carrega uma observação registrando a decisão de escopo; os corpora trazem casos de fronteira em quantidade; e nenhuma categoria depende de lembrar conteúdo já lido, o que indicaria saída não percebida da classe regular.
Registre no componente contínuo a pontualidade da entrega, a contribuição nas três discussões em duplas e o engajamento nas atividades colaborativas da tutoria — em especial na leitura cruzada de especificações, que é avaliável e costuma ser tratada como formalidade. Deixe claro à turma que a ausência de código aqui é decisão, não folga: o analisador léxico depende de teoria que só chega no módulo 7.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as três votações das aulas teóricas, com a projeção anônima. A questão do fecho de Kleene do conjunto vazio é o melhor termômetro do módulo: espere maioria na alternativa errada no primeiro voto e trate o segundo como medida de quantos conseguem operar com uma definição em vez de reconhecê-la. Se a maioria permanecer errada depois da discussão em duplas, não siga adiante — refaça a definição no quadro, porque a discussão entre pares só corrige quando há quem tenha entendido.
Guarde os dois histogramas de cada questão e compare-os com os do módulo anterior. É a primeira comparação disponível entre um módulo panorâmico e um módulo instrumental, e a queda na convergência do primeiro voto é esperada — é sinal de conteúdo que exige operação, não de turma pior. Use o dado para calibrar quanto de revisão de vocabulário formal levar para a abertura do módulo 3.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. Este é o módulo em que o número deixa de ser inflado pela curiosidade inicial, e a comparação com o módulo anterior passa a ter valor diagnóstico real.
Pontos de Atenção Específicos
A distinção entre o vazio e o que contém a cadeia vazia precisa de repetição deliberada. Ela aparece em quatro pontos do roteiro — na potência zero, no fecho do vazio, na cadeia a pertencente à linguagem de (a\mid b)^*a e no passo da demonstração por dupla inclusão — e cada aparição deve ser nomeada como sendo a mesma coisa outra vez. É o que os módulos 3 a 6 cobram disfarçado de transição vazia e de produção que deriva a cadeia vazia.
O formalismo vira liturgia se nenhum caso o testa. O risco deste módulo é o oposto do anterior: definições impecáveis que ninguém consegue usar. Verifique no fechamento — se a turma não conseguir decidir, olhando para a expressão do número, se a cadeia com zeros à esquerda é aceita, as definições não foram operacionalizadas.
Não antecipe o autômato. Alguém sempre pergunta, no argumento de contagem ou na fatia por comprimento, como se reconhece de verdade. Responda que a máquina é o assunto do próximo módulo, que ela tem memória finita e não volta atrás, e siga. Ceder aqui consome os blocos da álgebra e adianta mal um conteúdo que tem duas aulas reservadas.
Cuidado com a digressão sobre a biblioteca preferida da turma. No bloco da fronteira, a pergunta “mas na linguagem X funciona” aparece sem falta, às vezes com o estudante já testando no celular. Reconduza com a pergunta operacional — isto pode ser expandido nos seis construtores? — e transforme a curiosidade em tarefa para a abertura do módulo seguinte: quem quiser, traga uma construção da sua biblioteca preferida e classifique-a como açúcar ou fora da classe.
O bloco de construção ao vivo não é demonstração. Se metade da sala estiver olhando em vez de digitando, pare e espere. O tipo com seis casos digitado à mão é o que torna concreta a decisão de não acrescentar um caso para o sinal de mais — decisão que será cobrada no módulo 4 e que ninguém respeita se não a tiver escrito uma vez.
A frouxidão da especificação não se manifesta neste módulo. Este é o ponto de gestão mais importante do módulo. Uma especificação vaga passa despercebida agora, porque não há reconhecedor que a contradiga, e cobra o preço no módulo 3, quando o grupo não tem contra o que verificar o que construiu. Por isso a intervenção na tutoria é a cadeia de fronteira escolhida por você, e não a leitura complacente do documento entregue.