NFA e transições vazias

NFA e aceitação

Num NFA, $\delta(q,a)$ é um conjunto de destinos, possivelmente vazio. O NFA aceita quando existe um percurso que consome toda a palavra e termina num final.

• Simula com conjuntos de estados possíveis: desde o conjunto atual $S$ e a letra $a$, o conjunto seguinte é $S'=\bigcup_{q\in S}\delta(q,a)$.
• Para o sufixo $01$: $p$ repete $0,1$ e pode saltar $p\xrightarrow{0}q\xrightarrow{1}r$ ($r$ final, sem saídas). Em $001$: $\{p\},\{p,q\},\{p,q\},\{p,r\}$. Em $0010$: conjunto final $\{p,q\}$, rejeita.

Fecho-ε

Uma transição ε muda de estado sem consumir entrada. Para um conjunto $S$, o fecho $E(S)$ reúne os estados alcançáveis desde $S$ com zero ou mais transições ε.

1. Começa com o conjunto $S$ e segue só saídas ε, visitando cada estado novo uma vez.
2. A simulação começa em $E(\{q_0\})$. Para cada letra $a$ desde o conjunto atual $S$, calcula $S'=E(\bigcup_{q\in S}\delta(q,a))$.
3. No fim da palavra, aceita quando $S\cap F\ne\emptyset$. Os conjuntos guardados já estão fechados.

Na máquina de $a^*b^*$, o fecho inicial é $E(\{p\})=\{p,q\}$, por isso $\varepsilon$ é aceite. Depois de ler um $b$, ler um $a$ leva ao conjunto vazio.

Determinização

1. Começa com uma lista de trabalho desde o conjunto inicial, com fecho-ε quando a máquina tem transições ε.
2. Para cada subconjunto e cada letra, calcula a união dos destinos e depois o fecho.
3. Um subconjunto é final quando contém um estado final do NFA. O conjunto vazio, quando alcançável, funciona como poço.
4. Um NFA com $n$ estados tem no máximo $2^n$ subconjuntos; só os alcançáveis desde o início interessam.

Eliminar ε sem determinizar: $\delta'(q,a)=E(\bigcup_{p\in E(\{q\})}\delta(p,a))$, com $q$ final quando $E(\{q\})\cap F\ne\emptyset$.

Complemento

Trocar finais num NFA não complementa: uma palavra pode ter um ramo final e outro não final. Determiniza, completa, troca finais no DFA.

Os DFA, NFA e ε-NFA descrevem a mesma classe das linguagens regulares. O não determinismo reduz a descrição, não aumenta o poder.

Tabela completa da determinização.