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/>1296 estados"]
M05["Módulo 5<br/>Determinização e<br/>minimização<br/>FECHA O MOTOR"]
M06["Módulo 6<br/>Limites das<br/>linguagens regulares"]
M07["Módulo 7<br/>Análise léxica<br/>marco de consolidação"]
M03 --> M04 --> M05 --> M06 --> M07
subgraph ENTREGA["O que o módulo 5 deixa pronto"]
D1["Construção de subconjuntos<br/>com fecho vazio tratado"]
D2["Minimização por<br/>refinamento de partições"]
D3["Unicidade do mínimo:<br/>equivalência decidível"]
D4["Exportação visual<br/>como instrumento<br/>de depuração"]
end
M05 --- ENTREGA
D3 -.->|"critério de não regularidade"| M06
D1 -.->|"motor reusado nos dois níveis"| M07
D4 -.->|"depuração do resto do semestre"| M07
Módulo 05: Plano de Aula — Determinização e Minimização
Documento exclusivo do professor. Este é o guia operacional das seis aulas do módulo 5: 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 de votar.
Visão Geral do Módulo
Onde este módulo fica — é o que fecha o motor de autômatos e paga a conta deixada pelo módulo anterior.
Este módulo tem uma vantagem rara: ele começa com uma dívida já contraída diante da turma. O módulo 4 terminou com autômatos corretos e absurdamente grandes, e com uma pergunta que ficou explicitamente em aberto — se o não determinismo aumenta o poder de reconhecimento. As duas aulas teóricas daqui são a resposta às duas coisas ao mesmo tempo, e conduzi-las como resolução de pendência custa menos motivação do que apresentá-las como assunto novo.
O eixo conceitual, porém, não é o algoritmo de determinização, que é fácil. É a indistinguibilidade. É ali que a turma trava, e trava sempre pelo mesmo motivo: confunde estrutura com comportamento. Reserve o bloco mais longo da segunda aula para isso e não o comprima para caber o resto — se algum bloco tiver de ser encurtado, encurte o de visualização, cujo conteúdo se recupera na tutoria, e nunca o de distinguibilidade.
O terceiro fio é a unicidade. Ela é o resultado que transforma o capítulo inteiro de “técnica de implementação” em “ferramenta de decisão”, e é o que paga uma segunda dívida, esta do módulo 2, quando a comparação de duas expressões regulares foi apresentada como evidência e declarada insuficiente. Um estudante que sai daqui sabendo minimizar mas não sabendo dizer o que a minimização decide levou metade do módulo.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Completar o caminho da notação até a máquina executável e eficiente. Estabelecer o resultado de unicidade do autômato mínimo e o que ele permite decidir. Dotar o projeto de uma ferramenta de visualização que servirá de instrumento de depuração pelo resto do semestre.
Competências a desenvolver. Capacidade de avaliar um algoritmo pelo comportamento típico e pelo pior caso separadamente, sem confundir os dois. Capacidade de reconhecer, num resultado de unicidade, uma ferramenta de decisão prática e não apenas uma curiosidade teórica.
Habilidades a adquirir. Aplicar a construção de subconjuntos manualmente e implementá-la, tratando corretamente as transições vazias. Identificar e eliminar estados inalcançáveis. Distinguir estados equivalentes de estados distinguíveis e aplicar o algoritmo de particionamento. Explicar a unicidade do autômato mínimo e usá-la para decidir equivalência de linguagens. Exportar um autômato para visualização.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a ordem importa: cada bloco resolve uma insuficiência que o anterior deixou visível.
Bloco de abertura — a conta do módulo passado
Entre projetando a tabela de contagem de estados do seu próprio projeto, sem comentário nenhum, e deixe-a no quadro pelas duas aulas. As seis categorias léxicas da linguagem de referência somam 1296 estados depois da construção de Thompson: duzentos e cinquenta para o identificador, cento e sessenta e oito para o número, trezentos e noventa e dois para o texto entre aspas.
Faça uma pergunta só: “quantos estados vocês desenhariam à mão para reconhecer um identificador — uma letra seguida de letras, dígitos e sublinhados?”. Alguém responde dois, e responde depressa, porque é óbvio. Escreva 250 e 2 lado a lado no quadro e não explique nada ainda. Diga apenas que ninguém escolheu aqueles duzentos e cinquenta estados: eles vieram das seis regras da construção, aplicadas sem exceção, e que as duas aulas existem para desfazer o que a uniformidade da construção criou.
Feche o bloco declarando a segunda dívida, a do módulo 4: ficou pendente saber se o não determinismo dá poder de reconhecimento a mais. Diga que a resposta é não, que a demonstração é um algoritmo, e que esse algoritmo é o primeiro assunto da aula. Duas pendências abertas e nenhuma respondida — é a melhor abertura que este módulo permite.
Bloco seguinte — a construção de subconjuntos, traçada à mão
Comece pela observação que dispensa o algoritmo de parecer engenhoso: cada estado do autômato determinístico é um conjunto de estados do original, e é exatamente o conjunto que a simulação do módulo 4 carregava durante a execução. Verbalize a diferença, porque é ela que o estudante não vê sozinho: o cálculo é o mesmo, o que muda é quando ele acontece — lá, a cada símbolo lido, a cada execução; aqui, uma vez só, na construção.
O traçado à mão é obrigatório e tem de ser feito no quadro, com a fila visível. Use o autômato não determinístico sobre \{a,b\} com estados \{0,1,2,3\}, inicial 0, final 3, em que de 0 saem duas transições vazias, para 1 e para 2; de 1 sai uma transição por a de volta para 0; de 2 sai uma transição por b para 3. Antes de determinizar, pergunte que linguagem é essa e espere a resposta: a^*b.
Conduza o traçado assim, escrevendo cada passo:
O estado inicial do determinístico é E(\{0\}) = \{0,1,2\}, que chamo de A e coloco na fila. Expandindo A por a: mover dá \{0\}, porque só 1 tem transição por a; fechando, E(\{0\}) = \{0,1,2\}, que é o próprio A. Expandindo A por b: mover dá \{3\}; fechando, E(\{3\}) = \{3\}, conjunto novo, que chamo de B. Expandindo B: não há transição saindo de 3, os dois movimentos dão vazio, nada é declarado. Como 3 \in F, o conjunto B é final; A não é. A fila esvazia com dois estados.
Pare e faça a leitura: quatro estados viraram dois, e o resultado é exatamente o que qualquer pessoa desenharia para a^*b. As transições vazias, que na simulação custavam um cálculo de fecho por símbolo lido, desapareceram — foram absorvidas na definição dos conjuntos.
Antes de sair do bloco, escreva no quadro o erro que a turma inteira vai cometer na tutoria: a ordem é mover primeiro, fechar depois. Quem calcula o fecho só no estado inicial produz um autômato que rejeita cadeias válidas, e o defeito só se manifesta em expressões com estrela ou opcional no meio — que são justamente as da especificação léxica de todos os grupos.
Bloco seguinte — o traçado em que o autômato cresce
Se você parar no exemplo anterior, a turma sai com a impressão de que determinizar encolhe, e essa impressão custa caro no bloco seguinte. Faça o segundo traçado imediatamente.
Tome o autômato não determinístico das cadeias sobre \{a,b\} cujo penúltimo símbolo é a: \delta(q_0,a) = \{q_0,q_1\}, \delta(q_0,b) = \{q_0\}, \delta(q_1,a) = \delta(q_1,b) = \{q_2\}, com F = \{q_2\}. Três estados. Traçado no quadro: A = \{q_0\}; por a vai a \{q_0,q_1\} = B, por b volta a A. De B, por a vai a \{q_0,q_1,q_2\} = C, por b a \{q_0,q_2\} = D. De C, por a volta a C, por b a D. De D, por a vai a B, por b a A. Finais: C e D, os que contêm q_2. Três estados viraram quatro.
Agora peça à turma que interprete cada estado, e não siga antes de ouvir a resposta certa: A é “o último não foi a e o anterior não interessa”; B, “o último foi a e o penúltimo não era”; C, “os dois últimos foram a”; D, “o último não foi a, mas o penúltimo era”. O determinístico está lembrando os dois últimos símbolos, e por isso tem quatro estados. Conclua com a frase que sustenta o bloco seguinte: a adivinhação foi trocada por memória, e memória custa estados.
Bloco seguinte — o pior caso, medido
Este bloco é o de honestidade técnica, e a tentação é dramatizá-lo ou omiti-lo. Faça nem uma coisa nem outra.
O limite superior sai de graça: os estados do resultado são subconjuntos de um conjunto de n elementos, logo há no máximo 2^n deles. Escreva no quadro que para n = 40 isso já passa de um trilhão, e que um autômato de Thompson com quarenta estados é pequeno — a categoria menor do projeto de referência, a do espaço em branco, tem trinta.
Em seguida mostre que o limite é essencialmente apertado, com a família L_k das cadeias sobre \{a,b\} cujo k-ésimo símbolo contado do fim é a. Um não determinístico a reconhece com k+1 estados, adivinhando; todo determinístico precisa de pelo menos 2^k. Faça o argumento no quadro, porque ele é curto e antecipa a distinguibilidade da segunda aula: para u \neq v de comprimento k, seja i a primeira posição em que diferem, com u_i = a e v_i = b; tome z com i-1 símbolos quaisquer; o k-ésimo símbolo de uz contado do fim está na posição k + i - 1 - k + 1 = i, logo uz \in L_k e vz \notin L_k. Duas cadeias de comprimento k nunca podem levar ao mesmo estado, e há 2^k delas.
Projete então a medição do seu próprio projeto sobre essa família, que é o que torna o teorema observável:
k Thompson determinizado minimo
1 16 5 4
2 22 9 8
3 28 17 16
4 34 33 32
5 40 65 64
6 46 129 128
7 52 257 256Chame a atenção para duas colunas. A do determinizado dobra a cada incremento de k e vale 2^{k+1}+1; a do mínimo vale 2^{k+1}. O expoente é k+1, e não k, porque esta família conta o k-ésimo símbolo antes do fim, obrigando a lembrar k+1 símbolos — a formulação canônica do teorema numera o último símbolo como o primeiro e chega a 2^k pela mesma razão. E o ponto que vale o bloco: a minimização não ajuda aqui, porque o autômato já é mínimo. Não há desperdício a cortar; a linguagem exige mesmo essa memória.
Feche contrastando com a tabela da abertura, que continua no quadro: nas seis categorias reais a determinização encolhe, de 1296 para 332 estados. Explique por quê, com o identificador: [a-z] vira vinte e seis fragmentos alternativos, mas depois de ler um a ou um q o conjunto alcançado é o mesmo conjunto, porque os caminhos convergem para a mesma junção; a construção sob demanda consulta o mapa, encontra o conjunto já registrado e reutiliza o estado. Não há combinações genuinamente distintas a representar, e a explosão não ocorre.
Primeira questão de discussão em duplas. “A construção de subconjuntos aplicada a um autômato não determinístico de n estados: (a) sempre produz um autômato com mais estados que o original; (b) sempre produz um autômato com no máximo n estados, porque determinizar simplifica; (c) pode produzir até 2^n estados, e existem linguagens que forçam esse crescimento; (d) pode produzir até 2^n estados, mas a minimização posterior sempre desfaz o crescimento.”
Voto individual, discussão em duplas, novo voto — e não revele nada entre os dois. A resposta é (c). Quem vota (a) generalizou o segundo traçado; quem vota (b) generalizou o primeiro, e a existência dos dois traçados na mesma aula é o que torna esse erro corrigível pela dupla. O voto que interessa é (d), que costuma ser o segundo mais votado e é o mais bem-intencionado: ele supõe que minimizar resolve tamanho. A tabela da família L_k está no quadro e responde sozinha — a coluna do mínimo é 2^{k+1}, praticamente igual à do determinizado. Use esse confronto para fixar que determinizar e minimizar resolvem problemas diferentes.
Bloco de abertura da segunda aula — o desperdício que não é indistinguibilidade
Não recapitule. Abra perguntando o que ainda falta para transformar 332 estados em vinte, e organize a resposta em duas operações de naturezas diferentes, escritas lado a lado no quadro: descartar o que não serve e fundir o que se repete. Este bloco trata da primeira, que é curta e precisa vir antes.
Um estado é inalcançável quando nenhuma cadeia leva o autômato até ele; é morto quando nenhum final é alcançável a partir dele. Diga que a construção sob demanda nunca produz inalcançáveis, porque só cria estado ao alcançar o conjunto — e emende com a razão de escrever a remoção mesmo assim: autômatos escritos à mão, compostos ou lidos de arquivo podem ter órfãos, e o do módulo 3 é escrito à mão.
Insista num ponto que parece burocrático e não é, porque é o defeito silencioso mais provável da tutoria: a remoção de inalcançáveis vem antes do refinamento, nunca depois. Um estado inalcançável participa do refinamento como qualquer outro, tem assinatura, provoca separações, e pode sobreviver sozinho num bloco inflando a contagem final. O resultado continua reconhecendo a linguagem certa e deixa de ser mínimo — passa em todo teste de comportamento e quebra exatamente a unicidade, que é a razão de existir da minimização.
Registre por fim a decisão de representação e trate-a como decisão, não como detalhe: a minimização exige a forma completa durante o processamento, porque a assinatura precisa de um destino definido para cada símbolo; a saída pode voltar à forma parcial descartando o bloco morto. As duas convenções são corretas, e a única coisa proibida é misturá-las sem declarar. Avise que comparar um mínimo completo com um mínimo parcial produz uma diferença de exatamente um estado que não significa nada.
Bloco seguinte — distinguibilidade, e a intuição errada
Este é o bloco mais difícil do módulo. Comece pela pergunta, não pela definição: dado um autômato determinístico, quando dois estados podem ser tratados como um só?
Deixe a sala responder e anote as hipóteses. Elas quase sempre olham para dentro do estado — mesmas transições de saída, mesmos símbolos aceitos, posição parecida no desenho. Diga que todas essas respostas erram do mesmo jeito: olham a estrutura quando a pergunta é sobre comportamento. Só então escreva a definição, com w = \varepsilon destacada: dois estados são indistinguíveis quando, para toda cadeia w, um leva a final se e somente se o outro leva. Tomando w vazia, um final nunca é indistinguível de um não final — a separação mais barata que existe, e o ponto de partida do algoritmo.
Agora desmonte a intuição errada com o contraexemplo, no quadro. Autômato sobre \{a,b\} que reconhece as cadeias com pelo menos três ocorrências de a: estados 0, 1, 2 e 3, o número indicando quantos a já foram lidos, saturando em três; 3 é o único final; cada estado tem transição por a para o seguinte e por b para si mesmo. Os estados 0 e 1 têm transição pelos mesmos dois símbolos, ambos são não finais, ambos estão no meio da cadeia. E são distinguíveis: a cadeia aa leva 1 ao final 3 e leva 0 ao estado 2, que não é final. A testemunha é aa.
Complete com o lado contraintuitivo, que é o que a turma nunca deduz sozinha: dois estados cujas transições por um mesmo símbolo apontam para estados diferentes podem ser indistinguíveis, desde que esses destinos sejam, eles próprios, indistinguíveis. É essa circularidade que impede uma verificação local e obriga ao cálculo de ponto fixo do bloco seguinte. Escreva a leitura que resolve o assunto: um estado não é um ponto do desenho, é a linguagem que ele reconhece quando tomado como ponto de partida.
Segunda questão de discussão em duplas — a mais importante do módulo. “Num autômato determinístico completo, dois estados p e q são indistinguíveis quando: (a) têm transições definidas exatamente para os mesmos símbolos; (b) são ambos finais, ou ambos não finais, e têm o mesmo número de transições de saída; (c) para toda cadeia, o veredicto a partir de p é o mesmo que a partir de q; (d) suas transições, símbolo a símbolo, levam exatamente aos mesmos estados.”
A resposta é (c). Aplique o procedimento inteiro e reserve mais tempo de discussão do que nas demais questões do semestre. As alternativas (a), (b) e (d) são todas estruturais, e a (d) é a mais perigosa porque é suficiente sem ser necessária: estados que levam aos mesmos destinos são de fato indistinguíveis, e por isso quem vota (d) não está enganado sobre esse caso — está confundindo condição suficiente com definição. Se a turma convergir para (d) no primeiro voto, não abra discussão em duplas: volte ao contraexemplo dos destinos distintos porém equivalentes, porque a discussão só corrige quando existe na sala quem já tenha entendido.
Bloco de construção ao vivo — o refinamento de partições
Bloco de code-along. Peça que abram o editor e digitem junto; quem só assiste não aprende este bloco. Antes do código, faça o refinamento à mão no quadro, num autômato pequeno em que o algoritmo tenha algo a fazer.
Tome o autômato sobre \{a,b\} com estados 0, 1, 2, 2' e 3, inicial 0, único final 3, com transições: de 0, por a para 1 e por b para 0; de 1, por a para 2 e por b para 1; de 2, por a para 3 e por b para 2'; de 2', por a para 3 e por b para 2; e de 3, por qualquer símbolo para 3. Confirme com a turma que todos são alcançáveis.
A partição inicial é \{\{0,1,2,2'\},\{3\}\}, com blocos B_0 e B_1. Primeira rodada: 0 tem assinatura (B_0,B_0); 1 também; 2 tem (B_1,B_0); 2' também. O bloco B_0 se divide em \{0,1\} e \{2,2'\}, e a partição passa a \{\{0,1\},\{2,2'\},\{3\}\}, com blocos C_0, C_1 e C_2. Segunda rodada: 0 tem (C_0,C_0) e 1 tem (C_1,C_0), então C_0 se divide; já 2 tem (C_2,C_1) e 2' tem (C_2,C_1) — iguais, embora as transições por b levem a estados diferentes, porque os dois destinos estão no mesmo bloco. Pare aqui e diga em voz alta que este é o ponto do bloco inteiro. Terceira rodada: nada se separa, ponto fixo.
Quatro estados no fim, com 2 e 2' fundidos, e o resultado é o autômato de contagem que qualquer pessoa desenharia para “pelo menos três a”. Faça as duas leituras: o algoritmo redescobriu uma distinção semântica — quantos a já foram vistos — sem saber nada sobre contagem; e a separação de 0 e 1 só apareceu na segunda rodada porque a cadeia que os distingue tem comprimento dois. A rodada k calcula exatamente a distinguibilidade em k passos.
Só então construa o código ao vivo, com a instrumentação que imprime a partição a cada rodada — ela não é enfeite, é o que torna a estratificação por comprimento visível. Rode sobre o autômato determinizado do número, com quarenta e três estados, e projete a saída:
rodada 0: 2 bloco(s)
rodada 1: 4 bloco(s)
rodada 2: 5 bloco(s)
nenhuma separacao nova: ponto fixo alcancadoA rodada 1 é a instrutiva: ela separa os finais em dois grupos, e o que os distingue é que um aceita ponto adiante e o outro não — são a parte inteira e a parte fracionária, que o desenho à mão do módulo 3 já tinha separado por intuição. Diga isso explicitamente: o algoritmo redescobre a distinção sem saber o que é um número.
Encerre a construção escrevendo no quadro o defeito que mais aparece na tutoria deste módulo: a assinatura é de blocos de destino, não de símbolos. Quem monta a assinatura com o conjunto de símbolos para os quais há transição definida termina cedo, com um autômato pequeno demais, que reconhece um superconjunto da linguagem certa — e portanto passa em todos os testes positivos.
Bloco seguinte — unicidade, e o que ela decide
Aqui o módulo deixa de ser técnica e vira resultado. Enuncie a unicidade sem rodeio: entre todos os autômatos determinísticos completos que reconhecem uma linguagem regular, existe um de tamanho mínimo, e ele é único a menos de isomorfismo. Explique isomorfismo em uma frase — o mesmo desenho com os estados chamados por outros nomes.
O que a turma precisa levar não é a demonstração, é a consequência em duas etapas. Primeira: unicidade significa forma canônica, e forma canônica significa que comparar dois objetos vira comparar duas representações. Segunda: para comparar de fato é preciso fixar a numeração, e o procedimento é percurso em largura a partir do inicial visitando os símbolos em ordem, atribuindo números na ordem da descoberta. Dois isomorfos produzem numerações idênticas.
Projete agora a verificação cruzada do seu projeto, que é a demonstração empírica do teorema:
caminho 1 — desenhado a mao no modulo 3: 5 estados, minimizado para 5
caminho 2 — expressao regular via Thompson: 168 estados,
determinizado para 43, minimizado para 5
os dois minimos sao isomorfos? SIMDuas leituras, e a segunda vale o bloco. A primeira é que o desenho à mão já era mínimo — os cinco estados projetados no módulo 3 não tinham gordura. A segunda é o isomorfismo: dois caminhos completamente independentes, que não sabem um do outro, chegam ao mesmo objeto. Avise que o teste compara estrutura, não contagem: dois mínimos com cinco estados cada podem ter formas diferentes, e o teste os recusaria.
Feche pagando a dívida do módulo 2. Naquele módulo, comparar duas expressões regulares só era possível gerando as cadeias que cada uma denota até um comprimento escolhido, e ficou registrado que aquilo era evidência e não prova — duas expressões podem coincidir até o comprimento dez e divergir no onze. Agora existe o procedimento exato: converta as duas em autômatos, determinize, remova inalcançáveis, minimize e teste isomorfismo. Acrescente a consequência de projeto que interessa ao semestre: duas categorias léxicas cujas especificações se sobrepõem deixam de ser um defeito que aparece em entradas específicas e viram uma pergunta respondível antes de qualquer entrada existir.
Bloco de fechamento — o diagrama, e volta ao gancho
Comece com a mudança de patamar: até o módulo 4, os autômatos do projeto eram desenhados por pessoas e tinham uma dúzia de estados; conferir pela tabela era chato e viável. Acabou. Agora eles são produzidos por algoritmo, com dezenas ou centenas de estados, e conferir tabela é o tipo de tarefa em que a atenção falha em silêncio.
Apresente o formato DOT sem demora, no quadro, com duas convenções que valem seguir por serem as dos livros: estado final em círculo duplo e um nó invisível apontando para o inicial. Justifique o agrupamento de faixas com número: sem agrupar, o identificador teria trinta e sete arestas paralelas entre os mesmos dois estados.
Então conte o defeito real, porque é a melhor peça de argumentação do bloco. No projeto de referência, o rótulo da aresta da categoria de espaço em branco saiu como esp,n,r,t — o autômato estava reconhecendo as letras n, r e t. A causa estava no analisador da notação escrito no módulo 4: diante de \t, ele removia o significado especial da barra invertida e devolvia a letra t, em vez de traduzir para o caractere de tabulação. O autômato ficava bem formado, a determinização e a minimização funcionavam sobre ele, os testes de estrutura passavam, e a linguagem reconhecida estava errada. Nenhuma verificação anterior teria pego isso. O diagrama pegou.
Termine voltando ao quadro da abertura, onde 250 e 2 estão escritos desde o início da primeira aula, e complete a tabela com as três colunas:
categoria Thompson det. minimo reducao
IDENTIFICADOR 250 64 2 99.2%
NUMERO 168 43 5 97.0%
TEXTO 392 100 3 99.2%
PADRAO 392 100 3 99.2%
PONTUACAO 64 16 5 92.2%
ESPACO 30 9 2 93.3%
TOTAL 1296 332 20Mil duzentos e noventa e seis estados viram vinte, e o identificador chega exatamente aos dois que a turma respondeu na abertura. Diga a lição em uma frase e encerre: a expansão de Thompson é redundante por construção, e as duas etapas de hoje existem para desfazer redundância que ninguém quis criar — a construção não é ingênua, é uniforme, e a uniformidade cobra em tamanho o que entrega em simplicidade.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — determinização, minimização, exportação visual e a primeira verificação cruzada real do projeto.
O andaime já começou a diminuir. Nos módulos 3 e 4 você dava a estrutura da tarefa; aqui dá o objetivo e os critérios de conferência, e deixa o caminho por conta do grupo. Anuncie isso na abertura da primeira sessão, porque a redução de andaime só não é lida como abandono quando é declarada.
Tenha o seu projeto aberto e rodando durante as quatro aulas, e mantenha projetadas duas coisas: a tabela das seis categorias nas três etapas e a tabela da família de pior caso. A primeira é o alvo, a segunda é o antídoto contra a expectativa de que minimizar resolve tamanho — expectativa que reaparece na tutoria mesmo depois da aula teórica.
Primeira sessão de tutoria — determinizar, e medir
Abra cobrando o que os grupos vão querer pular: antes de escrever a determinização, escrever a medição. Peça que instrumentem a contagem de estados do autômato não determinístico de cada categoria e projetem os números da própria linguagem no quadro, um grupo de cada vez. É trabalho de poucas linhas e muda a sessão inteira: o grupo que vê a própria especificação somando algumas centenas de estados ataca o algoritmo com pergunta própria, e não porque foi mandado.
Circule com uma pergunta única e sempre a mesma enquanto implementam: “me mostre onde você calcula o fecho vazio”. A resposta separa na hora quem entendeu de quem copiou. O erro que você vai encontrar em pelo menos um terço da sala é fechar apenas no estado inicial e esquecer de fechar depois de cada movimento por símbolo. Não corrija de imediato: peça que testem uma expressão com estrela no meio, porque é onde o defeito se manifesta, e deixe o grupo ver a rejeição de uma cadeia que deveria ser aceita. A correção vale mais quando o sintoma foi observado.
O segundo ponto a cobrar é o mapa que leva cada conjunto de estados ao índice do estado correspondente. Grupos que criam um estado novo a cada expansão, sem consultar o mapa, produzem autômatos que não terminam de crescer em expressões com fecho. O sintoma é claro e vale antecipar em voz alta: se a determinização não parar, o problema não é a expressão, é o mapa.
Feche a sessão exigindo a coluna do meio preenchida para todas as categorias e uma frase escrita no diário: por que a determinização reduziu, ou por que não reduziu, naquela categoria específica. Grupos que apenas anotam o número não usam a medição para nada; a frase os obriga a olhar.
Segunda sessão de tutoria — minimizar, verificar e visualizar
Comece pela ordem, no quadro, antes de qualquer código: remover inalcançáveis, completar a forma, refinar, reconstruir, descartar o bloco morto se a convenção do grupo for a parcial. Escrita assim, a sequência parece burocrática; diga que ela é a diferença entre um autômato mínimo e um autômato quase mínimo que passa em todos os testes do grupo.
O defeito a caçar circulando é sempre o mesmo: assinatura montada com os símbolos em vez dos blocos de destino. Ele não aparece nos testes positivos, porque produz um autômato que aceita a mais. A forma barata de pegá-lo é comparar a contagem final com o desenho à mão do módulo 3 da mesma categoria — mínimo menor que o desenho manual é sinal de fusão indevida; mínimo maior é sinal de inalcançável não removido antes do refinamento. Ensine esse par de sintomas explicitamente, porque ele resolve a maioria dos casos sem depuração linha a linha.
Peça a instrumentação que imprime a partição a cada rodada. Não é enfeite de aula: é a única forma de o grupo ver o próprio algoritmo separando, e é o que permite responder à pergunta que sempre aparece — “como sei que parei na hora certa?”. A resposta é observável: quando uma rodada inteira não separa nada.
A segunda metade da sessão é a verificação cruzada, que é o item de maior valor do módulo e o mais frequentemente ausente da entrega. Cada grupo tem, para pelo menos uma categoria, dois caminhos independentes até o mesmo autômato: o desenho à mão do módulo 3 e a expressão regular passada por Thompson, determinização e minimização. Exija que os dois sejam minimizados e comparados por isomorfismo, com numeração canônica, e não por contagem. Diga em voz alta que contagem igual não é equivalência, e que é por isso que a função de isomorfismo existe.
Reserve o fim da sessão para a exportação visual e trate-a como infraestrutura, não como entrega decorativa. Exija o diagrama aberto na sua frente, não o arquivo no repositório. Se o Graphviz não estiver instalado na máquina do grupo, o arquivo de descrição continua sendo texto legível e a conferência pode ser feita nele mesmo — foi assim que o defeito da tabulação apareceu no projeto de referência, e vale contar essa história de novo aqui, com o grupo olhando o próprio rótulo de aresta.
Encerre com o registro no diário: os três números por categoria, a decisão sobre a convenção de totalidade, o resultado do teste de isomorfismo e, se houver, a categoria em que os dois caminhos divergiram — divergência é achado, não fracasso, e o grupo que a encontrou fez a verificação de verdade.
O que este módulo fecha, e o que é preciso dizer à turma
Diga explicitamente, ao fim da última sessão, que o motor está pronto: expressão regular entra, autômato mínimo sai, e há como provar que o resultado está certo. Esse é o primeiro artefato do semestre que faz algo completo, e a turma merece ouvir isso nomeado.
Emende, na mesma frase, o que vem depois — o módulo 6 vai mostrar o que essa ferramenta não consegue fazer, e a falha será demonstrada com o motor que o próprio grupo acabou de construir. Grupos que saem daqui com a ferramenta funcionando vivem o módulo 6 como descoberta; grupos que saem com pendência de implementação vivem como mais uma tarefa atrasada. É por isso que a pendência aqui não pode ser negociada para depois.
Entregáveis e Avaliação
Ao fim do módulo, cada grupo entrega a ferramenta completa que converte expressão regular em autômato determinístico mínimo, a exportação visual funcionando com os diagramas salvos, a tabela de contagem de estados nas três etapas por categoria léxica, e a verificação de que o autômato mínimo aceita e rejeita exatamente o mesmo que o reconhecedor manual do módulo 3.
Confira as entregas na mesma ordem para todos os grupos, e comece pelo que é mais rápido de falsificar. Peça o diagrama de uma categoria à escolha do grupo e depois peça o de outra, escolhida por você — grupos que geraram um arquivo isolado à mão travam na segunda. Em seguida abra a tabela de contagens e olhe a coluna do meio: se a determinização não reduziu nada em nenhuma categoria, ou o analisador da notação não está expandindo classes de caracteres, ou a construção não está consultando o mapa de conjuntos e cria estado novo a cada vez. Só então rode a verificação cruzada contra o reconhecedor do módulo 3, que é o item de maior peso da entrega e o mais frequentemente ausente.
Exija que a remoção de inalcançáveis exista como função separada e aplicável a qualquer autômato, mesmo que a determinização não produza nenhum. É o item que os grupos mais questionam por parecer inútil, e a resposta é datada: no módulo 7 o analisador léxico vai compor autômatos de categorias distintas, e composição produz órfãos.
Registre no componente contínuo a pontualidade da entrega, a contribuição nas duas discussões em duplas e o engajamento na tutoria. Diga à turma que a entrega daqui é a base do marco de consolidação do módulo 7: quem fecha este módulo com o motor verificado chega ao analisador léxico com trabalho de integração; quem entrega uma minimização que ninguém conferiu chega com trabalho de reconstrução.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as duas votações, mantendo a projeção anônima. A leitura que interessa neste módulo está na segunda questão, a da indistinguibilidade, e o sinal a observar não é o acerto: é a concentração em (d). Uma turma dividida entre (c) e (d) no primeiro voto está em boa forma, e a discussão em duplas resolve. Uma turma concentrada em (d) precisa que você refaça o contraexemplo antes de qualquer discussão, porque nesse caso a dupla não tem de quem aprender.
Guarde os dois histogramas dessa questão e compare a distância entre o primeiro e o segundo voto com a mesma distância medida no módulo 4. Se a distância encolheu, a turma está discutindo menos, e o motivo mais provável é acúmulo de pendência de implementação — vale checar isso na primeira sessão de tutoria em vez de atribuir a desinteresse.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. A queda aqui é sinal comum e enganoso: costuma indicar que o estudante parou na seção de distinguibilidade, não que abandonou o módulo. Se o número cair, retome o assunto na abertura da tutoria com o traçado de refinamento em vez de cobrar leitura.
Pontos de Atenção Específicos
O algoritmo é fácil e o conceito não é. O risco número um deste módulo é gastar a segunda aula polindo a implementação do refinamento e sair sem que a turma saiba dizer o que é indistinguibilidade. Se precisar cortar algo, corte o bloco de visualização, cujo conteúdo se recupera inteiro na tutoria, e nunca o bloco de distinguibilidade.
Não deixe a impressão de que determinizar encolhe. Os dois traçados da primeira aula existem justamente para impedir isso, e precisam ser feitos os dois, no mesmo bloco de tempo, sem que o segundo fique para depois. A turma que só vê o primeiro vota errado na questão do pior caso e, o que é pior, não desconfia do tamanho do próprio autômato na tutoria.
Minimizar não é a solução para tamanho. Esta confusão é persistente e reaparece na tutoria travestida de otimização. O antídoto é a tabela da família L_k, em que a coluna do mínimo é praticamente igual à do determinizado — deixe-a projetada durante a tutoria da segunda sessão, não só na aula teórica.
A ordem entre remover inalcançáveis e refinar não é preferência. Quem inverte obtém um autômato correto e não mínimo, que passa em todos os testes de comportamento do grupo. É o defeito mais silencioso do módulo, e a única forma de pegá-lo na tutoria é pela contagem: um mínimo com mais estados do que o desenho à mão da mesma categoria é sinal de inversão.
Cuidado com a digressão sobre Hopcroft. Alguém sempre pergunta por que não implementar o algoritmo mais rápido. Responda com os números: o de Moore custa da ordem de O(k n^2) e o de Hopcroft, O(k n \log n), e para os quarenta e três estados do maior autômato do projeto a diferença é imperceptível. Acrescente a razão didática, que é a que decide: a partição de Moore é observável rodada a rodada e corresponde exatamente à distinguibilidade em k passos, que é o conceito do módulo. E registre que a escolha é consciente — fazer a escolha e anotar o motivo vale mais do que implementar o mais rápido por reflexo.
Brzozowski é armadilha de aula. A construção por reversões e determinizações sucessivas é curta, elegante e tem pior caso exponencial. Se aparecer, mencione e siga: desenvolvê-la consome o bloco de unicidade.
A visualização será tratada como enfeite se você não intervier. Grupos apressados a deixam por último e entregam um arquivo que ninguém abriu. Exija o diagrama aberto na sua frente durante a tutoria, não o arquivo no repositório. O defeito da tabulação no projeto de referência é o argumento mais eficaz que você tem, e ele só funciona se for contado antes da entrega, não depois.