Visto com'è carino? Con un po' di magia, l'ε-NFA riconosce tutto:)
Formalmente, l'ε-NFA è una quintupla (!, Σ, δ. q0, f), che sono le stesse cose di un NFA e pertanto non le redifinisco, ma con questa variante:
δ: Q x Σ U {ε} -> ℙ(Q)
dove ℙ(Q) è l'insieme dei sottinsiemi di Q. Rispetto all'NFA normale, quindi, abbiamo che anche ε fa parte dei simboli riconosciuti.
ε-chiusura
La ε-chiusura di uno stato comprende l'insieme di tutti gli stati che si possono raggiungere a partire da quello stato, applicando una ε-mossa.
Oltre a questa definizione intuitiva, ne diamo anche una induttiva.
Base induttiva: q ∈ ε-chiusura(q)
il che vuol dire che uno stato q fa parte della ε-chiusura di se stesso.
Induzione: se p ∈ ε-chiusura(q), e r ∈ δ(p, ε), allora r ∈ ε-chiusura(q)
In altre parole: se p fa parte dell'ε-chiusura di q, ed r a sua volta è membro della ε-chiusura di p, allora r è anche membrdo della ε-chiusura di q'.
Abbiamo detto in forma matematica che l'ε-chiusura di uno stato comprende tutti gli stati che si possono raggiungere ε-muovendoci da quello stato.
δ^ degli ε-NFA
Negli ε-NFA, la δ^ è definita così, sempre induttivamente:
Caso base: δ^(q, ε) = ε-chiusura(q)
Se ricordate, negli NFA normali avevamo definito δ^(q, ε) = q. Qui invece, visto che la ε ha un ruolo più "attivo", ridefiniamo la δ^ con la ε-chiusura.
Passo induttivo: δ^(q, xa) = U, p ∈ δ(δ^(q,x),a), ε-chiusura(p)
Il passo induttivo ci informa che, rispetto all'NFA normale, includiamo negli stati raggiungibili tramite la δ^ anche tutti quelli appartenenti alla ε-chiusura di tutti gli stati attraversati dalla mia funzione.
Definizioni induttive a parte, quello che si vuole dire è che l'ε-NFA è uguale ad un NFA, con in più il fatto che la ε diventa un simbolo di primo livello.
Da ε-NFA a DFA
Il procedimento per andare da ε-NFA a DFA è simile a quello che si usa per andare da NFA a DFA (vedi il teorema di Rabin Scott), ma con la differenza che occorre anche includere, nei sottinsiemi raggiunti, anche tutti gli stati ε-raggiungibili.
