|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.Trad250309 History
Hide minor edits - Show changes to output
Changed line 24 from:
* hanno un segno '''+''' o '''-''', opzionale, all'inizio to:
* hanno un segno + o -, opzionale, all'inizio Changed lines 32-64 from:
to:
Visto com'è carino? Con un po' di magia, l'ε-NFA riconosce tutto:)
Formalmente, l'ε-NFA è una quintupla (!, Σ, δ. q'_0_', 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.
Added line 7:
!!Ancora sull'equivalenza tra DFA e NFA Changed line 20 from:
to:
Added lines 1-31:
(:title Traduttori - Appunti del 25 marzo 2009:)
[[Torna alla pagina di Traduttori -> Traduttori]]
%titolo%''':: Traduttori - Appunti del 25 marzo 2009 ::'''
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:
Attach:trad-e-nfa.png
----
[[Torna alla pagina di Traduttori -> Traduttori]]
|
|
