flowchart LR
M03["Módulo 3<br/>Autômatos finitos<br/>determinísticos<br/>desenhados à mão"]
M04["Módulo 4<br/>Não determinismo e<br/>construção de Thompson<br/>A NOTAÇÃO VIRA MÁQUINA"]
M05["Módulo 5<br/>Determinização e<br/>minimização"]
M07["Módulo 7<br/>Análise léxica"]
M03 --> M04 --> M05 --> M07
subgraph ENTREGA["O que o módulo 4 deixa pronto"]
D1["Analisador da notação<br/>de expressões regulares<br/>texto vira árvore"]
D2["Construção de Thompson<br/>árvore vira autômato<br/>não determinístico"]
D3["Fecho vazio e simulação<br/>por conjunto de estados"]
D4["Confronto contra o<br/>autômato manual do<br/>módulo 3 como gabarito"]
end
M04 --- ENTREGA
D3 -.->|"é a determinização<br/>feita sob demanda"| M05
D2 -.->|"inchaço de estados<br/>a ser cobrado"| M05
D1 -.->|"todas as categorias<br/>léxicas sem trabalho manual"| M07
Não Determinismo e a Construção de Thompson — Plano de Aula
Documento exclusivo do professor. Este é o guia operacional das seis aulas do módulo 4: 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 lê a resposta antes da aula, e a votação da abertura só produz efeito se ninguém souber que ela vai voltar no módulo 5.
Visão geral do módulo
Onde este módulo fica — é a passagem do autômato desenhado por uma pessoa ao autômato gerado por um programa.
Até o módulo 3 tudo o que reconhecia alguma coisa tinha sido desenhado à mão. Aqui isso acaba, e a mudança de patamar é o que dá sentido ao módulo: ao fim das seis aulas o projeto lê uma expressão regular escrita como texto e devolve um autômato executável, sem intervenção humana. As categorias léxicas que ficaram sem autômato no módulo passado deixam de exigir trabalho manual não porque alguém as desenhou, mas porque a máquina passou a fazê-lo.
O módulo tem dois eixos que a turma tende a confundir com um só. O primeiro é teórico: o não determinismo e a equivalência entre os modelos, resultado que contraria a intuição de todo mundo na primeira vez. O segundo é instrumental: a construção de Thompson e o analisador da notação que a antecede. Conduzir os dois como se fossem um assunto único é o erro mais fácil de cometer, e o sintoma é a turma sair achando que o não determinismo é “aquele jeito de montar autômato a partir de regex”.
Note também o que o módulo deliberadamente não entrega. A construção de subconjuntos fica para o módulo 5, e a tentação de antecipá-la é enorme, porque a simulação do autômato não determinístico já é o algoritmo funcionando sob demanda. Resista com precisão: deixe a turma perceber que a simulação refaz sempre o mesmo trabalho, e pare exatamente aí. Essa percepção madurada vale mais do que o algoritmo entregue antes da hora.
Objetivos, competências e habilidades
Objetivos de aprendizagem. Introduzir o não determinismo como recurso de especificação e estabelecer sua equivalência com o modelo determinístico. Construir a ponte automática entre a notação de expressões regulares e o modelo de máquina, eliminando a necessidade de projeto manual de autômatos.
Competências a desenvolver. Capacidade de reconhecer, num par de formalismos equivalentes, qual serve melhor a cada finalidade — especificar ou executar — e de projetar sistemas que usem cada um onde é adequado. Capacidade de apreciar construções composicionais e o que elas simplificam.
Habilidades a adquirir. Definir autômatos não determinísticos, com e sem transições vazias. Calcular o fecho vazio de um conjunto de estados. Enunciar a equivalência entre os modelos e explicar por que ela não é óbvia. Aplicar a construção de Thompson manualmente e implementá-la sobre a estrutura de uma expressão regular.
Estrutura das aulas
Aulas 1 e 2 — aula teórica
Roteiro por blocos — a ordem importa: cada bloco existe porque o anterior deixou uma insuficiência declarada.
Bloco de abertura — a máquina irresponsável
Chegue com o problema no quadro e nada mais: alfabeto de dois símbolos, e a linguagem das cadeias que contêm abb em algum lugar. Peça que a turma desenhe o autômato determinístico, em duplas, e circule enquanto desenham. Você vai encontrar sempre o mesmo travamento, e ele é o material da aula: estando no estado “vi o começo”, quando chega outro a, quase todo mundo devolve a máquina ao repouso. Pergunte a quem fez isso o que acontece com a cadeia aabb. A resposta cai sozinha — esse segundo a podia ser o início da ocorrência de verdade.
Só então desenhe ao lado a máquina irresponsável: quatro estados, laço de qualquer símbolo no repouso, saída simultânea por a para “vi o começo”, depois b, depois b, e aceita. Diga em voz alta que ela não decide nada e que foi desenhada sem nenhum raciocínio sobre o que fazer quando a tentativa fracassa.
Faça agora a pergunta que organiza o módulo, e não responda: isso é trapaça? Uma máquina que faz todas as escolhas ao mesmo tempo reconhece mais linguagens do que uma que se compromete a cada passo? Registre a votação no aplicativo antes de qualquer comentário seu. A maioria vota que sim, e é isso que você quer ter guardado para mostrar no módulo 5. Escreva a palavra conveniente no canto do quadro e não a apague durante as duas aulas.
Bloco seguinte — o formalismo e as duas leituras
Escreva a quíntupla e a única mudança que interessa:
\delta : Q \times \Sigma \to \mathcal{P}(Q).
Verbalize que a alteração é minúscula na escrita e enorme no significado: muda o que é executar o autômato, muda a estrutura de dados e muda o custo por símbolo. Aponte também o relaxamento que vem de brinde e que ninguém nota — conjunto vazio é a ausência de transição, então o estado de erro absorvente que a turma escreveu à mão no módulo 3 simplesmente desaparece da especificação.
Apresente as duas leituras lado a lado, porque a literatura troca entre elas sem avisar. A adivinhação com oráculo benevolente aceita quando existe um caminho que aceita, e é a leitura boa para demonstrar. A exploração simultânea acompanha o conjunto de todos os estados possíveis, é perfeitamente determinística, e é a única que se implementa. Escreva a transição estendida e insista na aceitação por interseção não vazia com o conjunto de estados finais — não se exige que todos os caminhos aceitem, basta um.
O exemplo numérico deste bloco tem de ser feito no quadro, símbolo a símbolo, sobre a máquina da abertura. Nomeie os estados q_0 (repouso), q_1 (vi o a), q_2 (vi o primeiro b) e q_3 (final), e simule a cadeia aabb partindo de \{q_0\}. Ao ler o primeiro a, o laço mantém q_0 e a saída simultânea acrescenta q_1, dando \{q_0, q_1\}. Ao ler o segundo a, de q_0 vem \{q_0, q_1\} e de q_1 não sai nada por a, resultando de novo em \{q_0, q_1\}. Ao ler o primeiro b, de q_0 vem \{q_0\} e de q_1 vem \{q_2\}, dando \{q_0, q_2\}. Ao ler o segundo b, de q_0 vem \{q_0\} e de q_2 vem \{q_3\}, dando \{q_0, q_3\}, que contém o estado final — cadeia aceita.
Pare no resultado e faça a observação que rende: repare que as duas “cópias” que estavam em q_0 nos dois primeiros passos se fundiram sozinhas, porque conjunto não guarda repetição. Essa fusão é o que a metáfora das cópias em paralelo esconde e é exatamente o que torna a simulação viável.
Primeira questão de discussão em duplas. “Na simulação de um autômato não determinístico sobre uma cadeia de n símbolos, quantos conjuntos de estados distintos podem aparecer, no máximo, se o autômato tem k estados? (a) k; (b) n; (c) 2^k; (d) não há limite, porque o conjunto pode crescer indefinidamente.”
Aplique o procedimento inteiro: voto individual sem comentário seu, discussão em duplas, segundo voto. A resposta é (c). Quem vota (d) é o alvo da questão — está lendo o conjunto ativo como memória ilimitada, e é exatamente esse engano que faz a equivalência entre os modelos parecer impossível. Não corrija na hora: guarde o resultado desta votação, porque ela é o degrau que você vai subir no bloco da equivalência. Quem vota (a) confunde o conjunto ativo com o estado ativo.
Bloco seguinte — transições vazias e o fecho
Introduza o segundo relaxamento pelo problema que ele resolve, não pela definição. Peça à turma que descreva como colar dois autômatos em sequência usando só transições que consomem símbolo: é preciso replicar, nos finais do primeiro, todas as transições que saem do inicial do segundo. Faça a pergunta que fecha o argumento: e se o autômato do segundo lado for gerado por outra parte do programa, que você não quer inspecionar? A quebra de encapsulamento é a justificativa da transição vazia, e apresentada assim ela deixa de parecer arbitrária.
Ao definir o fecho vazio, dê as duas formulações. A do menor conjunto fechado sob transições vazias é elegante e não diz como calcular; a por iteração diz. Anote as quatro propriedades e diga para que serve cada uma na prática: extensividade impede a versão errada mais comum, que devolve só os estados alcançados e esquece os de partida; idempotência autoriza aplicar o fecho uma vez em cada ponto do algoritmo; aditividade é o que a determinização vai explorar no módulo 5.
O ponto de atenção deste bloco merece ser dito com todas as letras, porque é o defeito que mais aparece no laboratório: a formulação recursiva natural do fecho não termina quando há ciclo de transições vazias, e ciclo de transição vazia não é patologia rara — a construção do bloco seguinte produz um por ocorrência do operador de repetição. Diga também o que não resolve: trocar recursão por pilha explícita não muda nada. O que garante a terminação é cada estado entrar na pilha no máximo uma vez.
Bloco seguinte — a equivalência, e por que ela não é óbvia
Volte à votação da abertura sem revelar o placar e enuncie o resultado: as linguagens reconhecidas por autômatos finitos determinísticos, por não determinísticos e por não determinísticos com transições vazias formam a mesma classe. O resultado é de Michael Rabin e Dana Scott, no trabalho de 1959 sobre autômatos finitos e seus problemas de decisão, um dos motivos pelos quais receberam o Prêmio Turing em 1976.
Insista em que o enunciado é sobre classes de linguagens e não diz nada sobre tamanho, custo de execução ou facilidade de escrita. É a confusão que sobrevive à aula se você não a atacar.
O sentido simples é imediato e cabe numa frase — leia cada destino único como um conjunto de um elemento. Dê ao sentido difícil o tempo que ele merece, e conduza-o pela objeção, não pela demonstração: o determinístico guarda um item e o não determinístico guarda uma coleção de tamanho variável, então parece haver diferença de capacidade de armazenamento. Aqui você colhe o que plantou na primeira questão de discussão: o conjunto ativo é sempre um subconjunto de Q, que é finito, logo há no máximo 2^{|Q|} conjuntos possíveis. Um autômato determinístico com 2^{|Q|} estados tem exatamente a memória necessária para lembrar de qual subconjunto se trata — e o nome do algoritmo do próximo módulo cai sozinho.
Feche com o limite exponencial, que não é folga da demonstração: para as cadeias cujo n-ésimo símbolo contado a partir do fim é um símbolo fixado, um autômato não determinístico com n+1 estados resolve adivinhando onde o sufixo começa, e o determinístico mínimo precisa de 2^n estados, porque tem de lembrar os últimos n símbolos lidos. Acrescente a boa notícia, senão a turma sai achando que determinizar é inviável: essa família existe para forçar o pior caso, e categorias léxicas reais não se parecem com ela.
Segunda questão de discussão em duplas. “Um autômato não determinístico com transições vazias reconhece a linguagem L. Sobre o autômato determinístico mínimo que reconhece a mesma L, é correto afirmar que: (a) ele pode não existir; (b) ele existe e nunca tem mais estados que o não determinístico; (c) ele existe e pode ter exponencialmente mais estados; (d) ele existe e tem exatamente o mesmo número de estados.”
A resposta é (c). Quem vota (b) trocou “mesma classe de linguagens” por “mesmo tamanho”, que é precisamente o deslize que o bloco tentou impedir — vale comentar isso em voz alta quando o histograma aparecer. Quem vota (a) ainda está com a intuição da abertura, de que o não determinismo acrescenta poder; esse voto deve praticamente desaparecer no segundo turno, e se não desaparecer, refaça o argumento de contagem antes de seguir.
Bloco de abertura da segunda aula — retomada pelo problema pendente
Não faça resumo. Aponte para a palavra conveniente no canto do quadro e pergunte o que ela ainda deve à turma. A dívida é esta: ficou estabelecido que o não determinismo é conveniente para especificar e inconveniente para executar, e que os dois modelos têm o mesmo poder — mas nada foi dito sobre quem produz o autômato não determinístico. Escreva a pergunta que abre a segunda aula: como é que uma expressão regular escrita como texto vira uma dessas máquinas, sem ninguém desenhar nada?
Bloco seguinte — a construção de Thompson
Enuncie a origem antes do algoritmo: Ken Thompson publicou em 1968 o algoritmo que traduz expressão regular em autômato não determinístico, no contexto de um mecanismo de busca em texto. São seis casos, um por construtor da definição indutiva.
Se você tiver de escolher uma única coisa para a turma levar deste módulo, escolha a invariante, e escreva-a no quadro: um fragmento normalizado tem exatamente um estado de entrada e um de saída, distintos; nada chega à entrada; nada parte da saída. Diga que as duas últimas condições são as que fazem o trabalho, porque garantem que o fragmento é uma caixa com um fio de entrada e um de saída, conectável sem que se saiba o que há dentro. É daí, e só daí, que sai a simplicidade dos seis casos.
Percorra os construtores desenhando, e em cada um pare no detalhe que a turma pularia. Na união, os dois estados novos são necessários: usar a entrada de um dos operandos como entrada comum faria essa entrada receber transição, e se aquele operando tiver uma repetição no topo, o laço de volta criaria caminhos que misturam as alternativas — não é sutileza teórica, é defeito. Na concatenação, nenhum estado novo e uma única transição vazia; registre a tentação de fundir os dois estados e o motivo de não fundir, que é a perda da invariante e a volta dos casos especiais nos outros cinco casos. Na estrela, os quatro saltos vazios, com o atalho direto respondendo pela repetição de zero ocorrências e o laço de volta respondendo por todas as demais — e é aqui que você fecha o círculo com o bloco do fecho: este é o caso que cria ciclos de transições vazias.
O exemplo numérico deste bloco é a construção manual completa de (a|b)^*abb, e ela precisa ser feita no quadro com a contagem acompanhando o desenho. Cada símbolo custa dois estados: são cinco símbolos, dez estados. A união custa dois, a estrela custa dois, e as três concatenações não custam nada. Total:
|Q| = 2n + 2u = 2 \times 5 + 2 \times 2 = 14.
Faça a turma conferir contando os círculos do desenho. Avise, porque alguém vai comparar com outro material e achar que errou: os livros que fundem os estados na concatenação chegam a onze, exatamente três a menos, um por concatenação. Não é divergência de teoria; é a escolha de preservar a invariante, e ela está tomada no nosso projeto.
Depois vem a má notícia, e ela é o gancho do módulo 5. Classes de caracteres não são construtores da teoria: são abreviações para uniões de símbolos, e a construção expande e paga por cada um. Uma classe com k símbolos custa 4k - 2 estados — faça a conta para os dez dígitos no quadro, 4 \times 10 - 2 = 38 estados para escrever [0-9]. E a classe negada depende do alfabeto inteiro: com o alfabeto de noventa e oito símbolos que o projeto declarou, negar um deles deixa noventa e sete, montados com noventa e seis uniões, dando 2 \times 97 + 2 \times 96 = 386 estados para um único átomo. Deixe o número no quadro. É o enunciado do problema que o próximo módulo resolve.
Terceira questão de discussão em duplas. “Por que a construção de Thompson não funde a saída do primeiro fragmento com a entrada do segundo na concatenação, economizando um estado? (a) porque a fusão produziria um autômato que reconhece outra linguagem; (b) porque o estado fundido deixaria de satisfazer a invariante de fragmento normalizado, e os outros casos precisariam de tratamento especial; (c) porque a fusão impediria o cálculo do fecho vazio; (d) porque a fusão só é possível quando nenhum dos fragmentos contém repetição.”
A resposta é (b). Esta é a questão mais difícil das três e o segundo voto costuma ficar dividido entre (a) e (b) — o que é bom, porque a discussão da diferença entre “está errado” e “quebra a invariante” é o conteúdo do módulo. Deixe claro no fechamento que a construção com fusão é correta: reconhece a mesma linguagem, e é o que vários livros fazem. O que ela custa é a uniformidade, e a uniformidade é o que permite escrever seis casos sem nenhuma inspeção do interior dos fragmentos.
Bloco de construção ao vivo — o analisador que ninguém anuncia
Este é o bloco de code-along, e ele começa por uma admissão que prende a turma: enunciei Thompson como uma tradução de expressão regular em autômato, e essa formulação esconde uma etapa que ocupa metade do trabalho. A construção opera sobre a árvore da expressão, e expressões chegam como texto. Pergunte quem já tinha percebido isso; poucos terão. Diga em seguida a circularidade, porque ela é agradável e ninguém a nota sozinho: estamos escrevendo um analisador sintático seis módulos antes de estudar análise sintática, e no módulo 10 o reconhecimento vai ser imediato.
Peça que abram o editor e digitem junto; quem só assiste não aprende este bloco. Pause ao fim de cada peça e verifique circulando, não perguntando à sala se todos conseguiram.
Construa primeiro o esqueleto do analisador por descida recursiva, uma função por nível de precedência, do mais fraco ao mais forte, cada uma chamando a seguinte, e o átomo voltando ao topo quando encontra parêntese. Diga a frase que justifica o desenho inteiro: nenhuma função conhece a tabela de precedências, porque a tabela é a ordem das chamadas.
Pare no ponto assimétrico, que é onde os grupos vão travar na tutoria. O laço da união pergunta se o próximo caractere é a barra vertical; o da concatenação não tem operador escrito para procurar e precisa perguntar o que para o laço — fim do texto, barra vertical e parêntese de fechamento. Escreva essa lista no quadro e diga o que acontece ao esquecer o parêntese de fechamento nela: a concatenação engole o fecho do grupo, o átomo que abriu nunca encontra o seu fechamento, e o erro é reportado três níveis acima apontando para o lugar errado. Se um analisador de descida recursiva reclamar de outro planeta, o conjunto de parada é o primeiro lugar a olhar.
Digite depois o nível do átomo, onde moram os detalhes chatos, e destaque o hífen dentro de classe, que é o erro clássico: em [a-z] ele é operador de faixa, em [a-] é símbolo literal, e a decisão exige olhar um caractere adiante e conferir que ele não é o colchete de fechamento. Escrito com descuido, [a-] consome o colchete como extremo superior da faixa.
A segunda peça é o fecho vazio com pilha explícita e conjunto de visitados. Ao digitar, verbalize o truque que vale a pena: a inserção no conjunto é o próprio teste — só empilhe o estado se a inserção disser que ele é novo. A terceira peça é a construção de Thompson propriamente dita, e aqui o code-along fica rápido, porque cada caso tem três ou quatro linhas; é a prova viva da invariante.
Encerre a construção rodando a demonstração do fecho sobre a*, que é o menor exemplo com ciclo — quatro estados, uma transição com símbolo e quatro vazias. Com a entrada nova em q_2, a saída nova em q_3 e o fragmento interno de q_0 a q_1, o fecho vazio de \{q_2\} sai como \{q_0, q_2, q_3\}, que já contém o final sem consumir símbolo algum — é exatamente isso que faz a* aceitar a cadeia vazia. Consumido um a, o conjunto passa a \{q_0, q_1, q_3\}, e a presença de q_0 é o laço de volta da estrela aparecendo no resultado, pronto para outro a. Projete a saída e deixe a turma ver o conjunto crescer e voltar; o desenho estático não produz esse efeito.
Bloco de fechamento — o confronto e a volta ao gancho
Rode a demonstração final ao vivo: o autômato gerado a partir da notação da categoria de números contra o autômato que foi desenhado à mão no módulo 3, sobre as treze cadeias do corpus daquela categoria — as seis que devem ser aceitas e as sete que devem ser rejeitadas. O relatório imprime cinco estados para o manual, cento e sessenta e oito para o gerado, treze veredictos iguais e nenhum divergente.
Explore os dois números na ordem certa. Primeiro o zero divergências, que é o que valida a implementação, e a observação metodológica que vem junto: o confronto compara veredictos, não conta acertos — um confronto que só verificasse concordância passaria se os dois autômatos estivessem errados do mesmo jeito, e um que só usasse as cadeias a aceitar daria nota máxima a um autômato que aceita tudo. As sete cadeias a rejeitar são as que têm poder de detecção. Depois o contraste de tamanho: cento e sessenta e oito contra cinco, para reconhecer exatamente a mesma linguagem. Pergunte de onde vem o inchaço e espere a resposta certa — os [0-9] da expressão, expandidos em dez símbolos cada.
Termine voltando à votação da abertura. Diga que a máquina irresponsável não era trapaça: era conveniência legítima, cobrada em tempo de execução, e que o preço dela está escrito no quadro em três lugares — os 386 estados de um átomo negado, os 168 da categoria de números e o fato de a simulação refazer o mesmo cálculo a cada entrada. Deixe a última frase como dívida declarada: no módulo 5 esse trabalho é feito uma vez só, guardado, e o número despenca.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — analisador da notação, construção de Thompson, fecho vazio e o confronto contra o autômato manual do módulo 3.
O andaime já começou a diminuir. No módulo 1 você deu critério, modelo e veredito; aqui dá o critério e o gabarito, e deixa o caminho por conta do grupo. Diga isso ao abrir a primeira sessão, porque a mudança é perceptível e sem aviso soa como desatenção: “eu digo o que a entrega tem de fazer e contra o que ela será conferida; como chegar lá é decisão de vocês”.
Tenha o seu próprio projeto aberto e projetado nas duas sessões, mas com o analisador da notação fechado. Este é o módulo em que mostrar o código pronto cedo demais custa a aprendizagem: a estrutura de uma função por nível de precedência é fácil de copiar e difícil de reinventar, e reinventá-la é o que faz o módulo 10 ser reconhecimento em vez de novidade. Mostre a saída do programa, não a fonte, até que o grupo tenha o seu esqueleto de pé.
Primeira sessão de tutoria — planejar, e descobrir o analisador escondido
Abra pedindo que cada grupo escreva no quadro do seu caderno a entrada e a saída da ferramenta deste módulo: entra texto, sai autômato. Deixe que planejem por conta própria por um tempo e circule ouvindo. O padrão é previsível: quase todos começam a planejar a construção de Thompson e nenhum planeja como a expressão sai do texto.
Não entregue a resposta. Faça a pergunta que a produz, sempre a mesma, grupo a grupo: “como o seu programa vai saber que o asterisco se aplica só ao último elemento, e não a tudo o que veio antes?” O grupo tenta responder com uma regra sobre caracteres, percebe que precisa saber qual é “o último elemento”, e daí sai sozinho que a expressão precisa virar estrutura antes de virar autômato. Esse momento vale mais do que qualquer aviso seu na aula teórica, e é por isso que a pergunta é feita aqui, e não lá.
A segunda decisão da sessão é o escopo da notação, e ela precisa sair escrita desta aula. Peça que cada grupo liste os operadores que vai suportar e, ao lado, os que decidiu não suportar com o motivo. Cobre a segunda coluna: uma lista só do que entra é intenção, não decisão. O critério de suficiência é objetivo e você o fornece — a notação precisa descrever as categorias léxicas que o próprio grupo especificou no módulo 2, e nada além disso. Grupos que quiserem suportar contadores ou retrovisores recebem o mesmo tratamento: retrovisores estão fora porque não são regulares, e contadores ficam de fora porque expandem para o que já existe.
Feche a sessão exigindo a decisão do alfabeto, que é a que passa despercebida e volta como defeito. Se a notação do grupo tem ponto ou classe negada, existe um universo implícito, e ele precisa ser declarado. Pergunte a quem usa ponto: “o ponto casa com quê, exatamente?” Se a resposta for “com qualquer caractere”, pergunte quantos são. Grupos que não declaram alfabeto descobrem o problema quando a construção pede a união de “todos os símbolos” e não há lista.
Segunda sessão de tutoria — construir, e fazer o autômato rodar
A ordem de construção não é indiferente, e vale impô-la nesta sessão: analisador primeiro, com a bateria de expressões inválidas funcionando, e só depois Thompson. Grupos que invertem passam a depurar dois componentes ao mesmo tempo, sem saber de qual lado está o defeito.
Cobre a bateria de inválidas antes de liberar o grupo para a construção, e forneça a lista mínima, porque ela é conteúdo e não burocracia: texto vazio, parêntese aberto sem fechar, parêntese fechado sem abrir, operador sem operando à esquerda, classe não fechada, classe vazia, faixa com extremos invertidos e barra invertida no fim do texto. Cada uma tem de produzir mensagem e posição. O argumento a dar em voz alta quando alguém reclamar do trabalho: uma bateria só de expressões válidas dá nota máxima a um analisador que aceita tudo.
Circulando durante a construção, você vai encontrar três defeitos com altíssima frequência, e reconhecê-los de longe economiza a sessão. O primeiro é o laço da concatenação sem o parêntese de fechamento no conjunto de parada — o sintoma é erro reportado em posição absurda, longe do problema real. O segundo é o hífen dentro de classe consumindo o colchete de fechamento como extremo de faixa. O terceiro, e o mais caro, é o fecho vazio sem marcação de visitado, que trava na primeira expressão com repetição; diante de um programa que não retorna, a primeira pergunta a fazer não é sobre o laço, é sobre a condição de inserção.
Cobre o revezamento de papéis com atenção redobrada neste módulo. A construção de Thompson é um trecho de código curto, elegante e muito atraente para quem programa com mais autonomia, e é exatamente o trecho que o grupo inteiro precisa entender. Se você vir um grupo em que a mesma pessoa digitou o analisador e está começando Thompson, troque as mãos você mesmo, na hora.
Fechamento — o confronto é a entrega, e o inchaço não é defeito
A última parte da tutoria é o confronto contra o gabarito, e ele é o item que fecha o módulo. Exija que a comparação use a categoria léxica cujo autômato o grupo desenhou à mão no módulo 3, e sobre o conjunto de cadeias que ele mesmo escreveu no módulo 2 — as de aceitação e, principalmente, as de rejeição. Se um grupo apresentar o confronto só com as cadeias a aceitar, devolva com uma frase: um autômato que aceita tudo passa nesse teste.
Peça também a contagem de estados dos dois lados, lado a lado, no relatório. Grupos ficam constrangidos com o número do autômato gerado e alguns começam a tentar reduzi-lo à mão. Corte isso na hora, com o argumento que a aula teórica já preparou: o inchaço é o resultado correto do algoritmo, é o preço da uniformidade, e reduzi-lo é o assunto do módulo seguinte, feito automaticamente e com prova de que o resultado é o menor possível. Tempo gasto aqui em economia manual é tempo perdido duas vezes.
Encerre com o diário, escrito nesta sessão e não na véspera. Neste módulo cobre uma entrada específica além das habituais: qual operador o grupo decidiu não suportar e o que essa decisão tornou impossível de descrever. É a anotação que o grupo vai reler no módulo 7, quando o analisador léxico precisar de todas as categorias, e é a evidência de que o corte foi consciente. Registre no seu próprio diário, por grupo, se o analisador ficou de pé antes de Thompson — o grupo que inverteu a ordem tende a chegar ao módulo 5 com o autômato gerado ainda não confiável, e a determinização sobre um autômato errado produz um resultado errado que parece certo.
Entregáveis e avaliação
Ao fim do módulo cada grupo entrega o código que lê uma expressão regular e produz o autômato não determinístico correspondente, o documento registrando quais operadores da notação a ferramenta suporta e por que essa escolha foi feita, e a evidência de funcionamento sobre as categorias léxicas da linguagem do próprio grupo.
Confira cada entrega contra seis itens, na mesma ordem para todos os grupos: o analisador aceita as expressões válidas da especificação do grupo e recusa as inválidas com posição; o documento de operadores diz o que ficou de fora e o motivo, e não apenas o que entrou; a construção tem um caso por construtor, sem tratamento especial escondido; o fecho vazio termina sobre uma expressão com repetição aninhada; existe simulação capaz de dar veredicto sobre uma cadeia; e o confronto contra o autômato manual do módulo 3 aparece com as cadeias a rejeitar, não só com as a aceitar.
O critério mais importante é o quinto e o sexto lidos juntos: sem simulação não há confronto, e sem confronto o grupo não tem como saber se traduziu certo. Um grupo que chegue ao fim do módulo com Thompson implementado e nenhuma forma de executar o resultado entregou um desenho, não uma tradução — trate isso como pendência a saldar antes do módulo 5, porque a determinização vai partir desse autômato.
Registre no componente contínuo do módulo a pontualidade da entrega, a contribuição nas três discussões em duplas da aula teórica e o engajamento nas atividades colaborativas da tutoria. Vale um aviso explícito à turma: o inchaço do autômato gerado não é defeito e não será penalizado. Grupos que gastarem a tutoria tentando economizar estados estarão fazendo, mal e à mão, o trabalho que o módulo 5 faz bem e automaticamente.
Orientações sobre o aplicativo
Use o aplicativo para as três votações e mantenha a projeção anônima. A votação da abertura — se a máquina irresponsável é mais poderosa — é diferente das demais: ela não tem segundo turno e não recebe resposta nesta aula. Registre-a, diga à turma que ficará guardada, e retome-a no módulo 5, quando a construção de subconjuntos tiver dado a resposta. Turmas reagem bem a esse tipo de dívida cumprida, e o efeito depende de você não entregar a resposta antes.
Nas duas questões com discussão em duplas, o dado que orienta a condução é a distância entre os dois histogramas. Na questão do número de conjuntos possíveis, uma turma que mantém a alternativa da memória ilimitada no segundo voto ainda não tem o argumento de contagem, e insistir no bloco da equivalência sem consertar isso é desperdício — refaça o argumento com k = 3 no quadro, enumerando os oito subconjuntos, antes de seguir. Na questão da fusão na concatenação, divisão entre duas alternativas no segundo voto é resultado saudável e não pede correção imediata; pede o comentário de fechamento.
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 costuma cair pela primeira vez no semestre, porque a carga de implementação sobe. A leitura útil não é o valor absoluto, e sim a comparação com o módulo 3: grupos cujo engajamento cai junto com o avanço do código costumam estar concentrando o trabalho em um integrante, e isso é para verificar na tutoria, com observação direta, não por inferência do número.
Pontos de atenção específicos
O analisador consome metade do módulo e não está no título. É o descompasso característico do módulo 4: o nome fala de Thompson e o trabalho real começa por ler a expressão. Se você não anunciar isso na aula teórica e de novo na sessão de planejamento, os grupos planejam a construção, começam pelo caso da união e travam ao descobrir que não têm árvore para percorrer.
Não antecipe a construção de subconjuntos. A pergunta “então por que não guardamos os conjuntos que a simulação calcula?” aparece, e é a pergunta certa feita antes da hora. Responda que é exatamente isso que o módulo 5 faz, nomeie o algoritmo e pare. Ceder consome o bloco de Thompson e adianta um algoritmo que a turma vai reencontrar sem o efeito de descoberta.
A confusão entre poder e tamanho sobrevive à aula. Depois de estabelecida a equivalência, alguém invariavelmente conclui que o autômato determinístico “é do mesmo tamanho”. Ataque isso duas vezes: no enunciado do teorema e de novo no fechamento, com os números do confronto na frente da turma. Cinco contra cento e sessenta e oito, mesma linguagem, é o argumento mais barato e mais eficaz que você tem.
Ciclo de transição vazia não é caso raro. Todo grupo que implementar a estrela vai criar um, e o fecho recursivo sem marcação trava na primeira execução. Antecipe na aula teórica e cobre na tutoria antes que o grupo passe uma sessão inteira depurando o laço errado — o defeito está na condição de inserção, nunca na estrutura do laço.
Escopo da notação: o risco é o excesso, não a falta. Grupos ambiciosos tentam suportar contadores, grupos de captura, retrovisores e âncoras. Corte com dois argumentos, e o primeiro é de conteúdo: retrovisores não são regulares, e suportá-los é sair da classe de linguagens que a disciplina estuda. O segundo é de escopo: contadores expandem para formas já suportadas e não ensinam nada de novo. A orientação é suportar o mínimo que descreva a própria especificação léxica do grupo, e registrar a decisão.
Cuidado com a digressão sobre expressões regulares de biblioteca. Alguém vai perguntar por que a biblioteca da linguagem aceita construções que a nossa notação recusa. A resposta é curta e vale a pena: motores de biblioteca implementam uma linguagem maior que a das expressões regulares da teoria, e é por isso que alguns têm comportamento de tempo exponencial em certos padrões, enquanto o autômato que estamos construindo dá veredicto em tempo proporcional à entrada. Duas frases, e reconduza — a comparação completa cabe no módulo 7, quando houver analisador léxico para medir.