flowchart LR
M02["Módulo 2<br/>Expressões regulares<br/>descrevem, mas<br/>não decidem"]
M03["Módulo 3<br/>Autômato finito<br/>determinístico<br/>A PRIMEIRA MÁQUINA"]
M04["Módulo 4<br/>Não determinismo e<br/>construção de Thompson"]
M05["Módulo 5<br/>Determinização e<br/>minimização"]
M07["Módulo 7<br/>Análise léxica"]
M02 --> M03 --> M04 --> M05 --> M07
subgraph ENTREGA["O que o módulo 3 deixa pronto"]
D1["Definição formal e<br/>função de transição<br/>estendida"]
D2["Método de projeto<br/>manual, do diagrama<br/>à tabela"]
D3["Estrutura de dados:<br/>estados por índice,<br/>tabela esparsa"]
D4["Reconhecedor verificado<br/>contra os conjuntos de<br/>cadeias do módulo 2"]
end
M03 --- ENTREGA
D2 -.->|"vira gabarito"| M04
D3 -.->|"herdada pelos algoritmos"| M05
D4 -.->|"motor do analisador léxico"| M07
Autômatos Finitos Determinísticos — Plano de Aula
Documento exclusivo do professor. Guia operacional das seis aulas do módulo 3: 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 o inventário de erros de projeto vale como diagnóstico, não como aviso prévio.
Visão Geral do Módulo
Onde este módulo fica — é a virada do gerador para o reconhecedor, e a primeira vez que o projeto compila alguma coisa.
O módulo 2 terminou com uma dívida deliberada: a turma sabe descrever conjuntos infinitos de cadeias e não sabe decidir pertinência. Este módulo paga a dívida trocando de objeto — do lado dos geradores para o dos reconhecedores. É a primeira máquina do curso, e a mais fraca de todas.
A armadilha de condução é o oposto da do módulo 1: lá o risco era virar lista, aqui é virar formalismo. A quíntupla é fácil de escrever no quadro, fácil de copiar e não ensina nada sozinha — quem recita M = (Q, \Sigma, \delta, q_0, F) e não desenha o autômato dos números decimais não aprendeu o módulo. A habilidade central é motora, adquire-se projetando, e o roteiro reserva o bloco mais longo da segunda aula para isso.
É também o primeiro módulo com código de verdade no projeto, e as decisões de representação atravessam o semestre. Estados por índice em vez de referência, símbolo em tipo sem sinal, tabela esparsa dentro do compilador — cada escolha é barata agora e cara a partir do módulo 5, quando os autômatos passam a ser construídos por algoritmo. Conduza a tutoria sabendo disso e resista à vontade de prescrever: o plano global manda conduzir por perguntas, e um grupo que descobre sozinho por que precisa comparar dois estados aprende o que a prescrição não ensinaria.
Objetivos, Competências e Habilidades
Objetivos de aprendizagem. Introduzir o primeiro modelo de máquina do curso e estabelecer a correspondência entre sua definição matemática e a estrutura de dados que a realiza. Desenvolver a habilidade de projetar autômatos a partir da descrição informal de uma linguagem.
Competências a desenvolver. Capacidade de transitar entre a formulação matemática de um modelo e sua implementação, reconhecendo que são a mesma coisa expressa em registros diferentes. Capacidade de escolher representações de dados com base em consequências previstas, e não por hábito.
Habilidades a adquirir. Definir formalmente um autômato finito determinístico e explicar o papel de cada componente. Converter entre diagrama de estados e tabela de transição em ambos os sentidos. Projetar o autômato de uma linguagem descrita informalmente, tratando corretamente o estado de erro e a completude da função de transição. Implementar o reconhecimento de cadeias a partir da descrição do autômato.
Estrutura das Aulas
Aulas 1 e 2 — Aula Teórica
Roteiro por blocos — a ordem importa, porque cada bloco responde a uma insuficiência deixada pelo anterior.
Bloco de abertura — decidir à mão, sem máquina
Escreva no quadro, sem introdução, a expressão da categoria de números vista no módulo anterior — sinal de menos opcional, repetição não vazia de dígitos e, opcionalmente, separador decimal seguido de outra repetição não vazia — e ao lado seis cadeias: -0.5, 007, 5., .5, 1.2.3 e 1e10. Peça que cada estudante, sozinho e no papel, marque quais são aceitas. Dê pouco tempo e passe entre as carteiras: quase todos acertam.
Então faça a pergunta que abre o módulo: qual foi o procedimento que vocês usaram? Peça a alguém que descreva em voz alta o que fez, como se instruísse uma máquina. A descrição sempre sai truncada — “olhei se tinha ponto”, “vi se terminava certo” — e é o truncamento que interessa: vocês decidiram seis cadeias curtas por inspeção, ninguém sabe dizer como faria com uma cadeia de dez mil símbolos, e nenhum de vocês descreveu um procedimento executável.
Feche nomeando a troca de objeto que o módulo realiza, e escreva as duas palavras no canto do quadro para não apagar durante as duas aulas: gerador e reconhecedor. A expressão gera e é boa para especificar; falta a máquina que testa. Avise que as seis cadeias voltarão no fim da segunda aula, decididas por um programa.
Bloco seguinte — o que “memória finita” quer dizer, e as datas
Comece desmontando a expressão “memória finita”, porque ao pé da letra ela não distingue nada — todo computador real tem memória finita. O que caracteriza o modelo é ter memória limitada por uma constante fixada antes de ver a entrada: o número de estados é escolhido quando a máquina é projetada e não muda porque a entrada cresceu. Uma cadeia de dez símbolos e uma de dez milhões passam pela mesma máquina.
Daí extraia a frase que sustenta os três módulos seguintes, e dite-a devagar para que copiem: tudo o que a máquina sabe sobre o que já leu está codificado em qual estado ela ocupa. A consequência é o critério de projeto: se dois prefixos levam ao mesmo estado, a máquina os trata como indistinguíveis daí em diante. Diga em voz alta que é a base do algoritmo de minimização do módulo 5 e o mecanismo da demonstração de impossibilidade do módulo 6, e que quem guardar uma frase do módulo deve guardar essa.
As origens merecem um trecho curto de quadro, com as datas escritas porque elas são o argumento. Em 1943 McCulloch e Pitts modelaram o neurônio como dispositivo de limiar com estados discretos. Em 1951, num relatório técnico publicado de forma ampla em 1956 na coletânea Automata Studies organizada por Shannon e McCarthy, Kleene caracterizou que classe de conjuntos de cadeias essas redes representam — as linguagens regulares — e introduziu a notação de onde vêm as expressões regulares. Entre 1954 e 1956, na engenharia de circuitos sequenciais, Huffman, Mealy e Moore chegaram independentemente ao mesmo formalismo, e o procedimento de minimização do módulo 5 é essencialmente o de Moore. Em 1959 Rabin e Scott introduziram o autômato não determinístico e mostraram que ele não reconhece nada além do determinístico, resultado pelo qual receberam o Prêmio Turing em 1976. Diga o ponto: quatro comunidades que não se falavam convergindo para o mesmo objeto em treze anos é sinal de que a quíntupla não é convenção de livro-texto.
Bloco seguinte — a quíntupla e os dois detalhes que a turma atropela
Escreva a definição no quadro e não a comente linha a linha, porque o comentário exaustivo faz o bloco desandar. Detenha-se em dois pontos apenas, que são os que produzem erro depois.
O primeiro é a totalidade de \delta: a definição exige destino para todo par de estado e símbolo. Pergunte quantas células tem a tabela de um autômato com cinco estados sobre um alfabeto de duzentos e cinquenta e seis símbolos, deixe alguém fazer a conta — 5 \times 256 = 1280 — e então pergunte quantas eles pretendem desenhar. O desconforto entre a exigência e a prática é o gancho do bloco sobre estado morto; declare a pendência e siga.
O segundo é a assimetria entre um estado inicial e um conjunto de finais. Não a apresente como convenção: pergunte por que a definição não é simétrica. A resposta é o determinismo — vários iniciais introduziriam escolha no primeiro instante, e escolha é o que o determinismo proíbe, ao passo que um conjunto de finais pede apenas um teste de pertinência ao fim.
Termine com a verificação instantânea que evita um erro de projeto inteiro: o estado inicial é final se e somente se a cadeia vazia pertence à linguagem. Peça que apliquem à categoria de identificadores, onde o inicial não é final, e às cadeias com número de ocorrências de a múltiplo de três, onde zero é múltiplo de três e o inicial é final.
Bloco seguinte — pôr a máquina em movimento, com traçado no quadro
A definição descreve o dispositivo parado; este bloco o põe a andar. Introduza a configuração instantânea como o par formado pelo estado corrente e pela porção não lida da entrada, e faça a turma notar que são duas componentes, sem fita e sem pilha — a pequenez da configuração mede o poder do modelo, e é o que cresce no módulo 9.
Escreva então a função de transição estendida por indução:
\hat\delta(q, \varepsilon) = q, \qquad \hat\delta(q, wa) = \delta\big(\hat\delta(q, w),\, a\big),
e insista na ordem de leitura, que é a confusão mais comum: para saber onde wa leva, descubra primeiro onde o prefixo w leva e só então dê um passo com a — a recursão desce pelo prefixo, não pelo primeiro símbolo.
Com isso no lugar, a aceitação cabe numa linha — a cadeia é aceita quando \hat\delta(q_0, w) \in F — e o bloco se paga com três traçados completos no quadro, sobre a tabela do número que você vai construir no bloco de projeto. Antecipe-a aqui, por faixas: de q_0, o sinal leva a q_1 e dígito leva a q_2; de q_1, dígito leva a q_2; q_2 é final, dígito o mantém e o separador leva a q_3; de q_3, dígito leva a q_4; q_4 é final e dígito o mantém.
Sobre -0.5: q_0 \xrightarrow{-} q_1 \xrightarrow{0} q_2 \xrightarrow{.} q_3 \xrightarrow{5} q_4, e q_4 \in F, aceita. Sobre 5.: q_0 \xrightarrow{5} q_2 \xrightarrow{.} q_3, a entrada acabou e q_3 \notin F, rejeita. Sobre 1e10: q_0 \xrightarrow{1} q_2, e para a letra não há transição declarada — a computação nem chega ao fim da cadeia.
Pare aqui e nomeie o que a sala acabou de ver: duas maneiras estruturalmente diferentes de rejeitar. Uma é chegar ao fim da entrada num lugar que não vale; a outra é encontrar um símbolo que não pertence. Para a definição de linguagem reconhecida são a mesma coisa; para quem escreve mensagens de erro, são “faltou alguma coisa” e “isto não pertence aqui”, e o analisador léxico do módulo 7 as reporta de formas diferentes. A informação que as distingue existe exatamente no instante em que a máquina para, e é perdida por um reconhecedor que devolva apenas um valor booleano.
Primeira questão de discussão em duplas. “Um autômato lê a cadeia w e, no terceiro símbolo, passa por um estado final; ao consumir o último símbolo de w, encontra-se num estado não final. A cadeia w é: (a) aceita, porque a computação passou por estado final; (b) rejeitada; (c) aceita apenas se nenhum símbolo posterior tiver transição indefinida; (d) indeterminada, porque a definição não cobre esse caso.”
Voto individual primeiro, sem comentário seu; discussão em duplas; segundo voto. A resposta é (b): a aceitação depende apenas do estado em que a computação termina. Quem vota (a) descreve o que faz ao traçar autômatos à mão — dá a cadeia por aceita assim que encosta num círculo duplo —, e essa é uma das principais fontes de erro em traçado manual; diga isso à turma quando o resultado aparecer. Quem vota (c) confunde o critério de aceitação com o modo de rejeição. Não revele a resposta antes da discussão em duplas.
Bloco de fechamento da primeira aula — as duas representações
Apresente diagrama e tabela como divisão de trabalho, não como preferência: o diagrama exibe a topologia e serve ao raciocínio humano, a tabela exibe a função de transição e serve à máquina. Recomende com ênfase projetar no diagrama e implementar a partir da tabela derivada dele, porque escrever a tabela direto produz, com regularidade quase cômica, estados inalcançáveis e finais no lugar errado — o desenho torna esses defeitos visíveis e a tabela os esconde.
Construa no quadro, com a sala, a tabela do autômato de três estados sobre \{a, b\} que reconhece as cadeias com número de ocorrências de a múltiplo de três: de q_0, a leva a q_1 e b leva a q_0; de q_1, a leva a q_2 e b leva a q_1; de q_2, a leva a q_0 e b leva a q_2; e q_0 é inicial e final. Faça a turma ler a estrutura ali: a coluna de b é a diagonal porque b não altera a contagem, e a de a é a permutação cíclica.
Termine com a conferência de contagem, que pega quase todo erro de conversão: a tabela de um autômato com n estados sobre alfabeto de k símbolos tem exatamente n \times k células, aqui 3 \times 2 = 6. Deixe a sala com a pergunta que abre a segunda aula: e quando a tabela do número tiver travessões no lugar de destinos, a conta ainda fecha?
Bloco de abertura da segunda aula — o estado que ninguém desenha
Retome pela pendência, não por resumo. Escreva a tabela do número com travessões nas posições sem destino e pergunte se aquilo é um autômato segundo a definição da aula anterior. A resposta correta é não; a resposta útil é que se trata de abreviação legítima, e a legitimidade tem condição.
Enuncie o completamento: acrescenta-se um estado novo d, não final, e manda-se para ele toda transição ausente, inclusive as que saem dele próprio, o que o torna absorvente. A linguagem não muda e o custo é um estado. Esboce o argumento sem escrever a indução: se a computação original consome a cadeia inteira, os dois autômatos percorrem os mesmos estados; se ela trava num prefixo, o completado entra em d e ali permanece, terminando fora do conjunto de finais. Registre as duas condições sem as quais nada disso vale — d não final e absorvente.
A leitura que interessa é que o estado morto sempre existe, mesmo quando não desenhado, e que exibi-lo ou omiti-lo é escolha de representação, não de semântica. Dê o número que a torna concreta: completar o autômato do número sobre um alfabeto de duzentos e cinquenta e seis símbolos produz seis estados com destino declarado para todos, isto é, 6 \times 256 = 1536 transições. A esparsa guarda só as declaradas — onze de q_0, dez de q_1, onze de q_2, dez de q_3 e dez de q_4, cinquenta e duas ao todo — com o mesmo comportamento: cerca de quatro por cento das células de uma matriz densa de 5 \times 256 = 1280 posições.
Feche com o critério que sobrevive ao módulo: a pergunta não é qual representação é melhor, é quantas vezes a tabela é consultada e quantas vezes é transformada. Dentro do compilador, cada transformação percorre as transições existentes; no artefato final, executado uma vez por símbolo lido, a matriz densa ganha.
Bloco seguinte — projetar autômatos, o bloco mais longo
Este é o núcleo da segunda aula e não pode ser comprimido. Comece pela pergunta de projeto, escrita no quadro e mantida à vista: lido um prefixo da entrada, qual é a menor informação sobre ele que preciso reter para decidir corretamente o resto da computação? Cada resposta possível é um estado.
Mostre a força do “menor” com dois casos curtos. Para as cadeias sobre \{a,b\} terminadas em a, basta lembrar se o último símbolo foi a: duas respostas, dois estados, autômato pronto antes do desenho. Para as cadeias com tantos a quanto b, a resposta é a diferença entre as contagens, um inteiro sem limite: infinitas respostas, e não há autômato finito. Marque que o método não apenas falha, ele avisa que vai falhar, e pelo motivo certo — é a intuição que o módulo 6 transforma em demonstração.
Enuncie os quatro movimentos e conduza o caso trabalhado seguindo-os na ordem, porque a ordem é o que separa projeto de tentativa e erro: listas de aceitação e rejeição antes do desenho; estados nomeados por significado e não por número; finais marcados antes das transições; completude conferida estado por estado.
O caso é o dos números decimais. Primeiro as listas: aceitas 0, 42, -7, 3.5, -0.25 e 007; rejeitadas a cadeia vazia, o sinal sozinho, .5, 5., 1.2.3, 1e10 e +3. Diga em voz alta que aceitar 007 é uma decisão, não um fato — é o tipo de coisa que o grupo descobre por acidente no módulo 7 se não decidir agora.
Depois os estados, nomeados: “não li nada” (não final); “li o sinal e nenhum dígito” (não final, porque o sinal sozinho não é número); “estou na parte inteira” (final); “li o separador e nenhum dígito depois” (não final); “estou na parte fracionária” (final). Cinco estados, e a numeração vem só quando o desenho estabilizar.
Agora percorra a lista de rejeições com a sala, mostrando por qual dos dois modos cada uma falha: o sinal sozinho e 5. param em estado não final; .5 trava no primeiro símbolo, porque do inicial não há transição por separador; 1.2.3 trava no segundo separador; 1e10 trava na letra; +3 trava porque o sinal de mais não está no alfabeto. É a verificação completa do projeto, feita à mão, e é o que os grupos farão na tutoria.
O ponto pedagógico está nos dois estados intermediários: eles existem para exigir que venha pelo menos mais um dígito. Generalize, porque o padrão reaparece o semestre inteiro — toda vez que uma construção opcional exige “pelo menos um” de alguma coisa, é preciso um estado não final entre o gatilho e a repetição.
Segunda questão de discussão em duplas. “No autômato dos números decimais, alguém propõe economizar um estado fazendo a transição do estado inicial pelo sinal levar diretamente ao estado da parte inteira. Qual é a consequência? (a) nenhuma, a linguagem reconhecida é a mesma; (b) o autômato passa a aceitar o sinal sozinho; (c) o autômato deixa de aceitar -7; (d) o autômato passa a aceitar +3.”
A resposta é (b): o estado da parte inteira é final, e o sinal sozinho passaria a terminar em aceitação. Quem vota (a) é a maioria no primeiro voto, e é isso que torna a questão útil — a economia parece boa e nada a contradiz, exceto a lista de rejeições escrita antes do desenho. Quem vota (c) confunde acrescentar caminho com remover caminho; quem vota (d) esqueceu que o sinal de mais não está no alfabeto. Feche nomeando o erro: estado final prematuro.
Encerre o bloco com o contraste do identificador — uma letra minúscula seguida de qualquer sequência de letras, dígitos e sublinhados —, que custa dois estados contra cinco do número embora a expressão não seja menor: a dificuldade de um autômato não é medida pelo tamanho da descrição, e sim por quantas vezes a decisão depende do que já foi lido. Some a ela a observação sobre o autômato da primeira aula, que parece contar e não conta: ele guarda o resto por três. Contar módulo k custa k estados; contar sem módulo é impossível.
Do inventário de erros, trate apenas o item que quase todos erram: o retorno indevido ao estado inicial. Tome as cadeias sobre \{a,b\} que não contêm abb — a pergunta de projeto pede lembrar quanto do padrão proibido já foi visto no final do prefixo, o que dá quatro respostas — e mostre que, do estado “vi a no fim”, ler outro a não volta ao inicial: esse novo a pode iniciar uma ocorrência. É o mesmo problema do fechamento de comentário de bloco.
Terceira questão de discussão em duplas. “Qual destas não é reconhecível por um autômato finito determinístico? (a) as cadeias sobre \{a,b\} com número de ocorrências de a múltiplo de três; (b) as cadeias sobre \{a,b\} que não contêm abb; (c) as expressões com parênteses balanceados, sem limite de profundidade; (d) as expressões com parênteses balanceados até profundidade quatro.”
A resposta é (c), e o contraste com (d) é o objetivo da questão: a versão limitada é reconhecível com um estado por nível de profundidade, e a irrestrita não é, porque exigiria lembrar um número sem limite. Essa diferença é o que separa, na prática, um comentário de linha de um comentário de bloco aninhável, e é o assunto do módulo 6.
Bloco de construção ao vivo — da definição à estrutura de dados
Este é o primeiro code-along com código que fica, e o plano global pede que seja completo: da tabela no quadro até o reconhecedor rodando. Avise a sala para abrir o editor e digitar junto, circule para conferir e não pergunte “todo mundo conseguiu?”, que sempre recebe silêncio afirmativo. Verbalize cada decisão enquanto digita, e verbalize também a alternativa descartada — é isso que estabelece o padrão de qualidade do semestre.
Estados são índices num vetor, nunca ponteiros. Diga por quê antes de digitar: um autômato é um grafo dirigido com ciclos — o estado da parte inteira aponta para si mesmo —, e com referências aparecem as perguntas de propriedade e a cópia deixa de ser trivial. Com índices, copiar é copiar dois vetores, comparar estados é comparar inteiros, e os conjuntos que a determinização vai exigir no módulo 5 serão conjuntos de inteiros. Alguém vai propor a modelagem por objetos; responda que esta é uma das poucas decisões do semestre a tomar sem experimentar a alternativa, porque o custo de descobrir empiricamente é uma reescrita com todos os algoritmos já escritos por cima.
O símbolo é de tipo sem sinal. Parece detalhe e produz defeito silencioso: um byte acima de cento e vinte e sete vira valor negativo com o tipo de caractere assinado, o mapa de transições passa a ordenar errado, e isso atravessa qualquer bateria de testes escrita sem acentos. Fixe o tipo num ponto só e converta na fronteira em que a cadeia é lida.
O reconhecimento é laço, não recursão. Escreva a definição indutiva ao lado e diga que o laço é a mesma recorrência calculada de baixo para cima — a indução desenrolada. A recursão literal daria profundidade igual ao comprimento da cadeia, e no módulo 7 isso roda sobre arquivos inteiros. Anote a correspondência em comentário ao vivo.
A transição ausente devolve um sentinela, verificado no topo de cada iteração: uma vez sem estado, sempre sem estado — o estado absorvente traduzido em código. Sem essa verificação, ou o programa acessa posição inválida, ou um valor lido por acidente corresponde a um estado válido e uma cadeia inválida acaba aceita.
Se couber, implemente também o traçado que devolve a sequência de configurações instantâneas: são poucas linhas e é o instrumento de depuração de todo o bloco de autômatos do curso.
Bloco de fechamento — os corpora viram executáveis, e volta ao gancho
Feche rodando na projeção a verificação do reconhecedor contra os conjuntos de cadeias escritos no módulo 2, com a saída aparecendo ao vivo: seis aceitas e sete rejeitadas na categoria de números, seis aceitas e cinco rejeitadas na de identificadores, nenhuma divergência. Diga o que mudou de estatuto: aqueles conjuntos eram um contrato que ninguém podia conferir e agora são um teste que roda.
Chame a atenção para dois casos que não são triviais: 007 foi aceito porque a decisão sobre zeros à esquerda foi tomada explicitamente no módulo 2, e Email foi rejeitado entre os identificadores porque o alfabeto não inclui maiúsculas. Os dois documentam decisões declaradas, não acasos.
Termine voltando às duas palavras do canto do quadro e às seis cadeias da abertura. A expressão gerava e não decidia; agora há uma máquina que decide, em tempo proporcional ao comprimento da entrada, sem retrocesso e sem caso patológico. Anuncie o que vem: no módulo 4 a expressão passa a virar autômato por algoritmo, e o trabalho de hoje vira gabarito — o autômato produzido pelo algoritmo terá de reconhecer exatamente as mesmas cadeias, e é contra este que será conferido.
Aulas 3 a 6 — Tutoria do Projeto Integrador
Quatro aulas de tutoria — autômato de uma categoria léxica projetado à mão, reconhecedor implementado e verificação contra os conjuntos de cadeias do módulo 2.
O andaime ainda é alto neste módulo, mas menos do que no módulo 1: você fornece o método e o critério, e não mais o modelo pronto. Tenha o projeto de referência aberto e projetado nas duas sessões, e use-o como se usa um gabarito — mostrando o formato da entrega, não a resposta da categoria de cada grupo.
Uma advertência de condução vale para as quatro aulas. A tentação dos grupos é abrir o editor na primeira sessão e projetar o autômato “enquanto implementa”. Corte isso sem negociar: quem implementa antes de desenhar produz um reconhecedor que codifica um autômato que ninguém sabe desenhar, e a entrega do documento fica sendo engenharia reversa do próprio código. A ordem — papel, depois teclado — é ela própria conteúdo deste módulo.
Primeira sessão de tutoria — o papel antes do teclado
Abra pedindo que cada grupo escolha a categoria e defenda a escolha em uma frase, antes de qualquer desenho. Passe grupo a grupo com a mesma pergunta: quantas vezes, nessa categoria, a decisão depende do que já foi lido? Se a resposta for “uma”, o autômato terá dois estados e o exercício não ensina nada — mande escolher outra. Quem escolheu a categoria de números, de textos delimitados ou de padrões tem material; quem escolheu pontuação ou espaço, não.
Fechada a escolha, proíba o desenho até que as duas listas estejam escritas. Cadeias que devem ser aceitas, cadeias que devem ser rejeitadas, com os casos de fronteira explícitos: a cadeia vazia, cadeias de um símbolo, cadeias truncadas no meio de uma construção, cadeias com o símbolo certo no lugar errado. Circule conferindo o tamanho da lista de rejeições — grupo que escreveu oito aceitas e duas rejeitadas escreveu a lista para concordar com o autômato que já imaginou. As rejeições são onde o projeto é decidido, e é onde a lista tem de ser generosa.
Só então libere o desenho, exigindo os quatro movimentos na ordem. Cobre em voz alta o segundo, que é o mais negligenciado: estados nomeados por significado, não por número. Ande pela sala lendo os nomes; onde estiver escrito q_3 sem nome ao lado, pergunte o que aquele estado quer dizer, e a resposta indecisa é o diagnóstico de que o desenho está sendo feito por tentativa e erro.
Reserve a última parte da sessão para a conferência cruzada. Cada grupo entrega o diagrama a outro grupo, junto com as duas listas, e o grupo receptor traça as cadeias à mão e devolve o veredito. Duas coisas acontecem com regularidade e valem ser antecipadas por você: aparecem estados finais prematuros que o autor não via, e aparecem transições esquecidas em estados de repetição — o símbolo declarado no lugar em que aparece pela primeira vez e esquecido no laço. Instrução por pares aplicada a artefato, e é mais eficiente do que a sua correção individual, porque quem traça o autômato alheio aprende a traçar o próprio.
Feche pedindo a tabela de transição derivada do diagrama, com a conferência de contagem feita e anotada. Grupos que derivarem a tabela em casa costumam derivá-la do que lembram, e não do desenho.
Segunda sessão de tutoria — o reconhecedor e a verificação
Abra retomando as quatro decisões de representação da aula teórica, mas não as prescreva. Passe em cada grupo com as três perguntas do plano global, na ordem, e deixe que a resposta se forme: como você vai percorrer todos os estados; como vai comparar dois estados; como vai gravar essa descrição em arquivo. Grupo que respondeu às três sem hesitar escolheu bem. Grupo que travou na terceira quase sempre modelou estados como objetos ligados por referência, e a pergunta seguinte — quem é dono de quem, quando o estado da repetição aponta para si mesmo — costuma bastar.
Se, ainda assim, o grupo insistir na modelagem por referência, deixe prosseguir e registre no diário. É orientação do plano global e é a decisão pedagogicamente correta: o custo aparece no módulo 5, quando os conjuntos de estados da determinização exigirem comparação e chave estável, e a lembrança de ter sido avisado vale mais do que ter sido impedido.
Cobre desde a primeira linha que o reconhecedor seja genérico: recebe a descrição de um autômato e uma cadeia, e não embute o autômato do grupo. Vários grupos escrevem uma função que reconhece números com condicionais aninhados, ela passa em todos os testes e não serve para nada a partir do módulo 4. O critério de conferência é direto — se o programa não consegue rodar o autômato de outro grupo, não é um reconhecedor.
A segunda metade da sessão é a verificação contra os conjuntos do módulo 2, e é aqui que o módulo se paga. Insista em duas propriedades do relatório. A primeira: ele precisa saber reportar falha, e não apenas contar acertos. Peça, como exercício rápido, que cada grupo estrague deliberadamente uma marca de estado final e rode de novo; se o relatório continuar dizendo que está tudo certo, o relatório é decorativo e o grupo acabou de descobrir isso sozinho. A segunda: as divergências que aparecerem devem ser lidas antes de corrigidas — em metade dos casos o defeito está no autômato, e na outra metade a cadeia foi classificada errado no módulo 2, e as duas conclusões são entregas legítimas.
Aproveite as divergências reais que surgirem para retomar a distinção dos dois modos de rejeição, agora com o traçado impresso pelo programa na frente do grupo. É o melhor momento do módulo para isso, porque a distinção deixa de ser observação de aula e vira leitura de saída.
Fechamento e registro
Verifique o revezamento de papéis pessoalmente, e neste módulo com mais rigor do que no anterior, porque agora há teclado e o piloto tende a se fixar. A regra é trocar ao fim de cada peça — descrição do autômato, laço de reconhecimento, relatório de verificação —, e a conferência é você chegar e perguntar ao navegador o que a linha corrente faz. Se ele não souber, o par não estava programando em par.
Registre no diário, por grupo, três coisas: a categoria escolhida e quantos estados o autômato tem; a escolha de representação, com a anotação explícita quando ela contrariar a orientação; e se o relatório de verificação sobreviveu ao teste do defeito deliberado. As três se pagam adiante — a primeira no módulo 4, quando a construção automática for confrontada com este desenho; a segunda no módulo 5; e a terceira no módulo 7, quando a qualidade do relato de erro passa a ser critério explícito de avaliação.
Entregáveis e Avaliação
Cada grupo entrega três coisas: o documento com o diagrama de estados e a tabela de transição do autômato projetado à mão, com justificativa das escolhas; o código do reconhecedor funcionando; e o registro da execução sobre o conjunto de cadeias do módulo 2, com as divergências entre esperado e obtido documentadas e compreendidas, não ocultadas.
Confira as entregas contra sete itens, na mesma ordem para todos os grupos: as listas de aceitação e rejeição aparecem antes do desenho, e não como justificativa posterior; o estado inicial está corretamente marcado quanto à cadeia vazia; existe estado não final intermediário para cada exigência de “pelo menos um”; a tabela é derivada do diagrama e a contagem de células fecha; o reconhecedor decide qualquer autômato e qualquer cadeia, e não só o autômato do grupo; a execução está registrada com as contagens de aceitas e rejeitadas; e o código compila sem nenhum aviso sob o modo estrito.
Um critério merece firmeza: divergência documentada não é penalizada, e divergência ocultada é o defeito mais grave desta entrega, porque um relatório que só sabe contar acertos não prova nada. Anuncie isso na primeira sessão de tutoria, não na correção.
Registre no componente contínuo a pontualidade, a contribuição nas três discussões em duplas e o engajamento na tutoria, com atenção ao revezamento de papéis, que neste módulo passa a ter custo real porque há teclado envolvido.
Orientações Sobre o Aplicativo
Use o aplicativo da disciplina para as três votações, mantendo a projeção anônima. A que mais informa é a segunda, sobre a economia de um estado no autômato do número: convergir para (a) no primeiro voto é o normal, e a distância até o segundo voto mede quanto a lista de rejeições virou instrumento. Se a convergência para (a) persistir no segundo voto, não siga para o bloco de código — refaça o traçado do sinal sozinho no quadro, porque o erro reaparece intacto na entrega da tutoria.
A primeira questão é termômetro do traçado manual: proporção alta em (a) — cadeia aceita por ter passado por estado final — indica que a turma vai errar a verificação do próprio autômato na tutoria, e é sinal para circular pedindo traçados completos, não apenas o veredito. Guarde os pares de histogramas; a comparação com os do módulo 2 é o que calibra o módulo 4, que é menos tolerante a lacunas.
Acompanhe também o engajamento no estudo do material, que responde por metade do componente contínuo. O número tende a cair em relação ao módulo 2, porque o conteúdo deixa de ser notação e passa a exigir desenho no papel. Queda acentuada concentrada nos mesmos grupos costuma indicar grupo em que só um integrante constrói; cruze com o diário antes de tratar como desinteresse.
Pontos de Atenção Específicos
O módulo vira formalismo se você deixar. O risco número um é gastar as duas aulas na definição e chegar ao fim sem que ninguém tenha desenhado um autômato. Se apertar, corte profundidade no bloco das origens e no argumento do completamento, nunca no bloco de projeto.
O estado de erro implícito é o erro conceitual mais frequente. O plano global registra isso: estudantes desenham autômatos incompletos e se surpreendem quando a implementação falha. A advertência direta funciona mal; o que funciona é a questão de discussão e o traçado de 1e10 no quadro.
Não antecipe a minimização. Alguém vai perguntar como saber se o autômato desenhado é o menor possível. Responda que o autômato mínimo existe e é único, que a consequência é haver gabarito objetivo, e que o algoritmo é do módulo 5. Ceder aqui consome o bloco de código.
Na tutoria, conduza por perguntas e deixe o grupo errar. O plano global é explícito: grupos que representam estados por referências encadeadas terão dificuldade crescente a partir do módulo 5, e a orientação se faz perguntando como pretendem percorrer todos os estados, comparar dois estados e serializar a descrição. Quem insistir numa escolha ruim deve prosseguir, com o problema registrado no diário — prescrever a resposta transfere a decisão para você e a reescrita acontece do mesmo jeito, sem aprendizado.
A categoria escolhida pelo grupo pode ser fácil demais. Quem escolhe pontuação ou espaço entrega um autômato de dois estados e não exercita nada. Use o contraste entre cinco e dois estados da aula teórica como critério na primeira sessão: se o grupo já prevê dois estados, escolheu mal.
Cuidado com a digressão sobre bibliotecas de expressões regulares. A pergunta “por que a biblioteca da linguagem X trava com certas expressões” é legítima e aparece quase sempre. Responda em duas frases — essas bibliotecas não executam um autômato determinístico, e sim uma busca com retrocesso, de pior caso exponencial — e reconduza.