LRM Prof. Mantovani ← Aulas da disciplina
Semana 4 · Aula 4 de 14

Análise léxica II — autômatos finitos

Como a especificação por expressão regular vira código executável: autômatos finitos determinísticos (AFD) e não determinísticos (AFN), o pipeline ER→AFN→AFD→código e o funcionamento interno de um scanner como uma máquina de estados.

📚 Compiladores🧪 1 simulador(es)📝 mini-quiz ao final
Objetivos da aula

O que você vai aprender

1

Diferenciar AFD e AFN e seus papéis.

2

Entender a conversão ER → AFN → AFD → scanner.

3

Traçar a execução de um autômato sobre uma entrada.

4

Reconhecer o papel de geradores como Lex/Flex.

1 · Motivação

Da regra ao programa

Na aula anterior, especificamos tokens com expressões regulares. Mas uma ER é uma descrição, não um programa. Como transformá-la em código que de fato lê caracteres e reconhece tokens?

A resposta são os autômatos finitos: máquinas de estados que executam o reconhecimento. Esta aula mostra a ponte entre a teoria (ER) e a implementação (código do scanner).

🔑
Um scanner é, no fundo, um autômato finito percorrendo o texto e mudando de estado a cada caractere.
2 · Mapa

O que veremos nesta aula

Autômato finito→AFD × AFN→Pipeline ER→código→Lex/Flex
  • O que é um autômato finito e seus componentes.
  • A diferença entre versões determinística e não determinística.
  • O caminho da ER ao código do scanner.
  • Como ferramentas reais automatizam isso.
3 · Definição

Autômato finito

Autômato finito. Máquina abstrata com um conjunto finito de estados, transições rotuladas por símbolos, um estado inicial e um ou mais estados de aceitação.

Formalmente é uma quíntupla (Q, Σ, δ, q0, F): estados Q, alfabeto Σ, função de transição δ, estado inicial q0 e estados finais F.

4 · Aprofundamento

Como o autômato reconhece

O autômato começa no estado inicial e, lendo a entrada caractere por caractere, segue a transição correspondente. Ao terminar a entrada, se estiver num estado de aceitação, a cadeia é aceita.

Para um scanner, "aceitar" significa "reconheci um token": o autômato emite o token e recomeça do estado inicial para o próximo lexema.

💡
Estados representam "o que já vi até agora". No reconhecedor de identificador, há um estado para "ainda nada", outro para "li uma letra, estou dentro de um identificador".
5 · Exemplo

AFD de identificador

O autômato que reconhece identificadores (letra seguida de letras/dígitos) tem dois estados úteis:

EstadoLê letraLê dígitoAceita?
INICIAL→ DENTRO(erro)não
DENTRO→ DENTRO→ DENTROsim

Começa em INICIAL; a primeira letra leva a DENTRO; daí em diante, letras e dígitos mantêm em DENTRO, que é estado de aceitação.

6 · Interativo

Passo a passo: reconhecendo "a1"

Passo 1
Estado INICIAL. Lê 'a' (letra) → vai para DENTRO.
Passo 2
Estado DENTRO. Lê '1' (dígito) → permanece em DENTRO.
Passo 3
Fim da entrada. Estado atual DENTRO é de aceitação.
Passo 4
O autômato emite o token <ID, "a1">.
7 · Definição

AFD e AFN

AFD. Autômato finito determinístico: para cada estado e símbolo, existe no máximo uma transição. Não há transições vazias (ε).
AFN. Autômato finito não determinístico: pode haver zero, uma ou várias transições por símbolo, e transições ε (sem consumir entrada).
8 · Aprofundamento

Por que existem os dois

O AFN é fácil de construir a partir de uma expressão regular, mas difícil de executar (precisa explorar várias alternativas ao mesmo tempo). O AFD é o contrário: trabalhoso de montar, mas trivial e rápido de executar.

💡
Por sorte, todo AFN tem um AFD equivalente (mesma linguagem). Construímos o AFN a partir da ER e depois o convertemos em AFD para executar. O melhor dos dois mundos.
9 · Analogia

Decidido × indeciso

🔧 Analogia
O AFD é como um motorista que, em cada cruzamento, sabe exatamente para onde ir. O AFN é um motorista indeciso que, num cruzamento, "se divide" e tenta todos os caminhos em paralelo, aceitando se qualquer um deles chegar ao destino. Executar o decidido é direto; o indeciso dá mais trabalho.
10 · Comparação

AFD × AFN

AFD (determinístico)AFN (não determinístico)
Transição por símboloNo máximo umaZero, uma ou várias (e ε)
Transições εNãoSim
ExecuçãoDireta e rápidaExplora alternativas
Construção a partir da ERIndiretaDireta (Thompson)
Uso típicoImplementação do scannerEtapa intermediária
11 · Fluxo

Da expressão regular ao scanner

ER→AFN
Thompson→AFD
subconjuntos→AFD mínimo→Código

Cada seta é um algoritmo clássico: Thompson constrói o AFN; a construção de subconjuntos determiniza; a minimização reduz estados.

12 · Aprofundamento

Os três algoritmos do pipeline

  • Thompson (ER → AFN): monta o AFN composicionalmente, com transições ε ligando os pedaços.
  • Construção de subconjuntos (AFN → AFD): cada estado do AFD é um conjunto de estados do AFN simultaneamente ativos.
  • Minimização (AFD → AFD mínimo): funde estados equivalentes, gerando o menor autômato que reconhece a mesma linguagem.
13 · Verifique

Verifique você mesmo: AFD ou AFN?

Um autômato em que o estado q0, lendo 'a', pode ir tanto para q1 quanto para q2 é:

Em um AFD, cada par (estado, símbolo) tem no máximo uma transição. Ter duas saídas com 'a' caracteriza não determinismo: é um AFN.
14 · Caso prático

Lex e Flex

Ferramentas como Lex e Flex automatizam todo o pipeline desta aula. Você fornece as expressões regulares e ações; elas geram o código C do scanner.

✅
Internamente, o Flex constrói o AFD a partir das suas ERs e gera uma tabela de transições compacta. Na prática, ninguém desenha autômatos à mão para produção: descreve-se em ER e a ferramenta cuida do resto.
15 · Erros comuns

Confusões sobre autômatos

⚠️
Cuidado. Transições ε existem só no AFN, nunca no AFD. E "não determinístico" não significa "aleatório": significa que há escolhas; o AFN aceita se algum caminho de escolhas levar à aceitação.

Outro engano: achar que o AFD equivalente sempre tem o mesmo número de estados do AFN. Em geral tem mais (no pior caso, exponencialmente mais).

16 · Boas práticas

Implementando o scanner

✅
Dica. Um scanner eficiente representa o AFD como uma tabela de transições (matriz estado × símbolo → estado). O laço principal vira: ler caractere, consultar a tabela, atualizar o estado. Simples, rápido e fácil de gerar automaticamente.
17 · Revelar

Reflita: ER e AFD são equivalentes?

Toda expressão regular tem um AFD equivalente, e todo AFD tem uma ER equivalente?
Sim, nos dois sentidos. ERs, AFNs e AFDs descrevem exatamente a mesma classe: as linguagens regulares (tipo 3 de Chomsky). É o teorema de Kleene. Por isso podemos ir da ER ao AFN, do AFN ao AFD e de volta — todos reconhecem o mesmo conjunto de cadeias, mudando só a forma e a eficiência.
18 · Flashcards

Termos-chave da aula

AFDvirar
Autômato com no máximo uma transição por (estado, símbolo) e sem ε. Rápido de executar.
AFNvirar
Autômato com várias transições possíveis e transições ε. Fácil de construir da ER.
Thompsonvirar
Algoritmo que constrói um AFN a partir de uma expressão regular.
Subconjuntosvirar
Construção que determiniza um AFN, produzindo um AFD equivalente.
19 · Conexões

Onde isto se encaixa no curso

Esta aula fecha o estudo do léxico:

  • Vem da aula 3: as ER que especificam os tokens.
  • Concretiza a aula 2: autômatos finitos são o reconhecedor do tipo 3 (regular).
  • Prepara a aula 5: a sintaxe, tipo 2, precisará de um reconhecedor mais poderoso (autômato com pilha).
20 · Síntese

Resumo visual

🔑
AFD: uma transição por símbolo, rápido. AFN: várias e ε, fácil de construir. O pipeline ER→AFN→AFD→código (Thompson, subconjuntos, minimização) é a base dos geradores de scanner como Lex/Flex. ER, AFN e AFD descrevem a mesma classe: as linguagens regulares.
21 · Simulador

Experimente pensando em estados

Use novamente o playground léxico, agora com olhar de autômato: a cada caractere digitado, pergunte-se em que estado o reconhecedor estaria. Quando ele "aceita" e emite um token? Quando rejeita?

Acompanhar a tokenização caractere a caractere é a melhor forma de internalizar como um AFD percorre o texto.

Mão na massa · colaborativo

Atividade em grupo · Desenhando o autômato

Em grupos, desenhem no papel/quadro o AFD que reconhece números reais.

⏱️ 30 min👥 grupos de 3–4🧩 laboratório

Roteiro

  1. Padrão alvo: dígito+ ( . dígito+ )? (ex.: 12, 3.14).
  2. Desenhem os estados e transições; marquem os estados de aceitação.
  3. Tracem a execução para "3.14" e para a entrada inválida "3." (ponto sem dígito).
  4. Confiram que o estado de aceitação não é atingido por "3.".
Desenhistaesboça o autômato
Executortraça as entradas
Críticobusca casos que quebram
📤 Entrega: Diagrama do AFD + traços de execução para uma entrada válida e uma inválida.
Teste seu conhecimento

Mini-quiz · Aula 4

20 questões sobre esta aula. Escolha e veja a explicação na hora.

0/20

📌 Resumo — leve isto para a prova