NFA e transições vazias

No DFA do sufixo $ab$, cada letra determina o próximo estado. Um NFA pode manter o ciclo que lê o prefixo e, ao mesmo tempo, começar um ramo que tenta verificar o sufixo; uma escolha errada bloqueia esse ramo, mas basta um ramo consumir a palavra toda e terminar num final.

Aceitação é existência de um percurso

Um NFA tem os mesmos cinco componentes de um DFA, mas

$$\delta:Q\times\Sigma\to\mathcal P(Q).$$

O destino é um conjunto: pode conter zero, um ou vários estados. $\mathcal P(Q)$ é o conjunto de todos os subconjuntos de $Q$. Um ramo sem transição morre, sem impedir que outro ramo aceite.

Um NFA aceita $w$ se existe pelo menos um percurso de $q_0$ até um estado final que lê exatamente $w$. Não exige que todos os percursos aceitem, e não pode aceitar deixando símbolos por ler.

Para o sufixo $01$, com conjuntos de estados fáceis de seguir, usa esta tabela:

Estado	$0$	$1$
$p$ inicial	$\{p,q\}$	$\{p\}$
$q$	$\emptyset$	$\{r\}$
$r$ final	$\emptyset$	$\emptyset$

O ciclo em $p$ lê o prefixo. A transição $p\xrightarrow{0}q$ escolhe o início do sufixo. Como $r$ não tem saídas, essa escolha só aceita se o $1$ for a última letra.

Para simular sem adivinhar, mantém o conjunto de estados possíveis. Se $S$ é o conjunto atual, depois de ler $a$ tens $\bigcup_{q\in S}\delta(q,a)$. Para $001$:

$$\{p\}\xrightarrow{0}\{p,q\} \xrightarrow{0}\{p,q\} \xrightarrow{1}\{p,r\}.$$

Como o conjunto final contém $r$, a palavra é aceite. Com mais um $0$, chegas a $\{p,q\}$ e a palavra $0010$ é rejeitada.

Experimenta $001$ e $0010$. O laboratório mantém todos os ramos: chegar a $r$ antes do fim não basta. Abre o editor para acrescentar um destino ou alterar os estados finais.

Construir um NFA por adivinhação

Para reconhecer palavras binárias cujo antepenúltimo símbolo é $1$, adivinha onde começa esse sufixo de comprimento 3. Usa quatro estados em linha: $p$ repete $0,1$; num $1$ pode saltar para $q$; depois $q \xrightarrow{0,1} r \xrightarrow{0,1} s$, com $s$ final e sem saídas.

Para $1101$, o ramo que salta no segundo $1$ lê depois $01$ e aceita em $s$, e o ramo que salta no primeiro $1$ lê depois $101$ e bloqueia por falta de transição, sem que isso impeça a aceitação. Também $1100$ é aceite, pois o segundo $1$ é o antepenúltimo símbolo e o ramo que o escolhe lê os dois $0$ até $s$.

Já $1000$ é rejeitada: o salto no único $1$ chega a $s$ depois de ler dois $0$, mas resta um terceiro $0$ e $s$ não tem saídas. A palavra vazia e as palavras com menos de três símbolos são rejeitadas pelo mesmo motivo, porque nenhum ramo chega a $s$.

Este é o padrão de adivinhação: um ciclo consome o prefixo, uma transição escolhe a posição relevante, e uma cauda curta verifica o sufixo. A determinização transforma essa adivinhação em conjuntos de estados possíveis.

De NFA para DFA: construção de subconjuntos

O DFA equivalente guarda um conjunto inteiro como um único estado. O estado inicial é $\{q_0\}$ e a transição é:

$$\delta_D(S,a)=\bigcup_{q\in S}\delta_N(q,a).$$

Um subconjunto é final se intersecta $F$. A tabela do exemplo fica:

Estado do DFA	$0$	$1$	Final?
$A=\{p\}$ inicial	$B$	$A$	Não
$B=\{p,q\}$	$B$	$C$	Não
$C=\{p,r\}$	$B$	$A$	Sim

Constrói a tabela por rondas, mantendo uma lista de trabalho:

1. Começa com o subconjunto inicial $\{q_0\}$.
2. Para cada subconjunto na lista e cada letra, calcula a união dos destinos e o seu fecho, se houver transições vazias.
3. Acrescenta à lista os subconjuntos novos e repete até não surgir nenhum.
4. Marca como final cada subconjunto que intersecta $F$.

Só precisas dos subconjuntos alcançáveis, não de desenhar todos os $2^{|Q|}$ candidatos. O conjunto vazio, se aparecer, é um estado poço como os outros: a união de destinos a partir dele continua vazia. O limite geral é $2^{|Q|}$ estados, e não $2|Q|$. Neste exemplo só surgem três.

Transições ε e fecho-ε

Num ε-NFA, permite $\delta:Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal P(Q)$. Uma transição $\varepsilon$ muda de estado sem consumir entrada.

O fecho-$\varepsilon$ $E(S)$ contém todos os estados alcançáveis de algum estado de $S$ com zero ou mais transições vazias. Inclui sempre $S$. Para o calcular, começa com $S$ e segue saídas vazias até não encontrar estados novos. Um ciclo vazio não impede o algoritmo de terminar, porque há finitos estados e cada estado entra uma vez no conjunto.

Considera a máquina para $a^*b^*$:

$E(\{p\})=\{p,q\}$ e $E(\{q\})=\{q\}$. A palavra vazia é aceite porque o fecho do início contém um final. A transição vazia não obriga a mudar para $q$; o ramo em $p$ continua disponível para ler mais $a$.

Compara a entrada vazia, $aab$ e $abba$. Cada linha mostra os destinos que consomem a letra e o fecho-ε desses destinos. No editor, o símbolo ε está disponível sem pertencer ao alfabeto.

Determinizar com fechos

Agora, o estado inicial do DFA é $E(\{q_0\})$, e cada passo é:

$$\delta_D(S,a)=E\left(\bigcup_{q\in S}\delta(q,a)\right).$$

Os conjuntos guardados já estão fechados. Se começares por um conjunto arbitrário não fechado, aplica o fecho antes de consumir a letra também.

Para a máquina anterior:

Estado	$a$	$b$	Final?
$A=\{p,q\}$ inicial	$A$	$B$	Sim
$B=\{q\}$	$C$	$B$	Sim
$C=\emptyset$	$C$	$C$	Não

O $a$ em $B$ leva ao poço porque, depois de começar os $b$, não pode haver outro $a$. Simular $abba$ percorre $A,A,B,B,C$ e rejeita. $aab$ termina em $B$ e aceita.

Para eliminar apenas as transições vazias, mantendo um NFA, podes definir

$$\delta'(q,a)=E\left(\bigcup_{p\in E(\{q\})}\delta(p,a)\right)$$

e marcar $q$ como final quando $E(\{q\})\cap F\ne\emptyset$. Isto também preserva a aceitação da palavra vazia.

Complementar depois de determinizar

Trocar finais e não finais num NFA não produz, em geral, o complemento. A aceitação exige algum ramo final; a rejeição exige que nenhum ramo seja final. Trocar estados não troca esses quantificadores.

O procedimento correto é construir o DFA completo equivalente e trocar os finais nesse DFA. No exemplo $a^*b^*$, apenas $C$ fica final. Assim, $abba$ passa a ser aceite, enquanto $aab$ e $\varepsilon$ passam a ser rejeitadas.

DFA, NFA e ε-NFA reconhecem a mesma classe, as linguagens regulares. O não determinismo pode reduzir o tamanho da descrição, mas não aumenta o poder deste modelo. Para aumentar a descrição sem mudar o poder, a conversão por Thompson segue a direção inversa.