Tudo igual ao DFA, exceto: δ : Q × Σ → 𝒫(Q) = a função de transição retorna um conjunto de estados (pode ser ∅, {q}, {q,r}, ...)
Diferença fundamental: No DFA, cada (estado, símbolo) leva a exatamente 1 estado. No NFA, pode levar a 0, 1, ou vários estados simultaneamente.
DFA — Determinístico
δ(q, a) = um estado. Sem escolha. Sempre sabe onde ir.
NFA — Não-Determinístico
δ(q, a) = conjunto de estados. "Adivinha" o caminho certo. Se algum caminho aceita, o NFA aceita.
Mesma Potência!
Teorema 2.12: L é aceita por algum DFA ⟺ L é aceita por algum NFA. Mesmas linguagens regulares.
2. Exemplo 2.6 — NFA para "Termina em 01"
Objetivo: Aceitar todos os strings de 0's e 1's que terminam em 01. Com um DFA precisaríamos de 3 estados cuidadosamente projetados. Com um NFA, a construção é mais intuitiva: o autômato "adivinha" quando o 01 final começou.
⚡ Interativo — veja o NFA explorando MÚLTIPLOS caminhos
Estados ativos: {q₀}
Entrada: ε · Não aceito (q₂ não ativo)
3. Construção de Subconjuntos: NFA → DFA (§2.3.5)
Para cada NFA N, podemos construir um DFA D tal que L(D) = L(N).
Ideia: Cada estado do DFA D é um subconjunto de estados do NFA N. O DFA "simula" todos os caminhos possíveis do NFA ao mesmo tempo.
CONSTRUÇÃO
Dado NFA N = (QN, Σ, δN, q₀, FN), construímos DFA D = (QD, Σ, δD, {q₀}, FD):
QD = 𝒫(QN) (subconjuntos de estados de N, no máximo 2n) δD(S, a) = ⋃q∈S δN(q, a) (união das transições de todos os estados em S) FD = { S ⊆ QN : S ∩ FN ≠ ∅ } (subconjuntos que contêm pelo menos um estado de aceitação de N)
Exemplo 2.10 — Convertendo o NFA "termina em 01" para DFA
⚡ Clique nos passos para ver a construção
1 Estado inicial do DFA: {q₀}. Calcular δD({q₀}, 0) e δD({q₀}, 1).
2Clique para revelar...
3Clique para revelar...
4Clique para revelar...
RESULTADOClique para revelar...
4. ε-NFA: Transições Vazias (§2.5)
Um ε-NFA estende o NFA permitindo transições com ε (string vazio). O autômato pode mudar de estado sem consumir nenhum símbolo de entrada.
δ : Q × (Σ ∪ {ε}) → 𝒫(Q)
Novo conceito: ECLOSE(q) = conjunto de todos os estados alcançáveis a partir de q usando apenas ε-transições (incluindo o próprio q).
ECLOSE(q)
Base: q ∈ ECLOSE(q). Indução: se p ∈ ECLOSE(q) e r ∈ δ(p, ε), então r ∈ ECLOSE(q). Seguir todas as ε-transições recursivamente.
ε-NFA → DFA
Igual à construção de subconjuntos, mas: estado inicial = ECLOSE(q₀), e cada transição δD(S, a) = ECLOSE(⋃q∈S δ(q, a)).
Mesma potência!
ε-NFA ⟺ NFA ⟺ DFA. Todos aceitam exatamente as linguagens regulares. ε-transições não adicionam poder, apenas conveniência.
Exemplo 2.16 — ε-NFA para números decimais
Objetivo: Aceitar strings da forma [sinal opcional][dígitos][ponto][dígitos] como +3.14, .5, 72., 100 etc. Um ε-NFA modela isso naturalmente: o sinal (+ ou −) é opcional via ε-transição do estado inicial.
Aplicação: Reconhecer as palavras "web" e "ebay" em um texto. Criamos uma cadeia de estados para cada palavra e conectamos via ε-transições a um estado inicial comum. Cada cadeia é um NFA simples para uma palavra específica, e o ε-NFA "escolhe" qual palavra tentar reconhecer.
5. Exemplo 2.13 — Explosão Exponencial
Pior caso: Um NFA com n+1 estados para "o n-ésimo símbolo a partir do fim é 1" pode exigir um DFA com 2n estados. Isso porque o DFA precisa "lembrar" os últimos n símbolos, e há 2n combinações possíveis. Na prática, a maioria dos estados é inalcançável, mas o pior caso teórico é exponencial.
COMPARAÇÃO DE TAMANHO (n = 3: "3º símbolo do fim é 1")NFA: 4 estados (q₀ → q₁ → q₂ → q₃, com q₀ tendo self-loop 0,1) DFA: até 2³ = 8 estados (cada estado lembra as últimas 3 entradas)
Para n = 10: NFA tem 11 estados, DFA pode ter até 1024 estados!