Torna alla pagina di Traduttori
:: Traduttori - Appunti del 25 marzo 2009 ::
Ancora sull'equivalenza tra DFA e NFA
Nella lezione precedente, abbiamo visto come si costruisce un DFA a partire da un NFA, e dimostrato che sono equivalenti, cioè che riconoscono le stesse stringhe.
Tuttavia, l'equivalenza deve andare in entrambi i sensi, quelli della doppia implicazione. Un DFA è equivalente ad un NFA se e solo se riconosce tutte e sole le stringhe riconosciute dal NFA.
La parte del se l'abbiamo dimostrata nella lezione precedente. Ora occorre il solo se, ovvero dimostrare che a partire dal DFA posso arrivare ad un NFA equivalente, tramite il nostro sistema.
La soluzione è abbastanza semplice: devo convertire la δD in δN, e per fare ciò dico che
se δD(q, a) = p, allora δN_(q, a) = {p}
In pratica faccio il giochetto dei sottinsiemi all'incontrario: la δD porta da uno stato ad un altro, mentre la δN da uno stato ad un insieme di stati. Se facciamo in modo che quest'insieme di stati contenga un solo stato, in particolare quello a cui porta la δD, allora il gioco è fatto.
L'equivalenza delle δ^ viene a gratis, perché le δ^ sono costruite proprio a partire dalle δ normali.
ε-NFA
Un ε-NFA è un automa non deterministico un po' particolare: esso possiede anche delle ε-transizioni, ovvero delle transizioni che scattano in presenza della stringa vuota ε. Lasciamo perdere le implicazioni filosofiche di questo automa, e vediamo un po' com'è fatto subito con un esempio.
Vogliamo un automa che riconosca i numeri decimali, cioè quelli che:
- hanno un segno + o -, opzionale, all'inizio
- hanno una stringa che rappresenta la parte intera, opzionale (se non c'è vuol dire che è 0)
- hanno un punto
- hanno una stringa che rappresenta la parte decimale, opzionale anche questa
Vedete quante "opzioni" ci sono? Provate a pensare ad un bel DFA che riconosca questo tipo di stringhe, e vedrete che non è banalissimo. Invece, con il trucchetto metafisico delle ε-transizioni, ecco come risolvo il problema:
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.
Torna alla pagina di Traduttori
