Forum Ubuntu-it

Sto rileggendo per bene, ma fatico un po'...

Intanto mi è venuta un'idea.
Potrei usare un'array d'appoggio lungo al massimo quanto tutti i nodi per segnare dove sono.
I campi segnati a 1 indicano la posizione dove siamo.
Usiamo il vecchio grafico .
Inizialmente parto da q0 quindi nell'array d'appoggio in 0 ho 1.
Leggo dove va q0 tramite la matrice: se mi entra un carattere 0 vado in q1 e q2.
Mi sono mosso da q0, quindi nell'array d'appoggio la posizione 0 (q0) diventa 0 mentre q1 e q2 diventano 1.
Stesso discorso se non mi posso muovere, lo stato attuale va messo a 0.
Ricomincio a scorrere l'array d'appoggio e vedo che la pos 1(q1) e 2(q2) sono a 1.
Quindi riscorro la matrice e vedo (in base al carattere) dove portano e riaggiorno l'array d'appoggio.
Potrei trovarmi nella situazione che l'array d'appoggio é tutto a 0, quindi l'NFA non porta da nessuna parte.
Userei un test (for): se tutto a zero, prima della fine scansione stringa, è rifiutato di sicuro: esci.
Se invece finisco, ciclo l'array d'appoggio. Se almeno uno dei campi corrispondenti alle uscite è a 1,
la stringa è accettata.
Per ora quello che ho pensato è questo.
Non so se può funzionare, potrebbero esserci degli inghippi sui cambi di stato che qui sulla carta non riesco a prevedere.
Però devo capire bene quello che hai scritto. Sicuramente sarà una soluzione più collaudata e snella la tua.
Le mie sono soluzioni da autodidatta che lasciano un po' il tempo che trovano

Ciao a tutti, avrei una domanda sui DFA ed essendoci un post già aperto ho pensatp non fosse il caso aprirne un altro. Spero che per l'autore del post non sia un problema.

Dato un linguaggio regolare L, un DFA M che riconosce L è minimo se M è un DFA con il minimo numero di stati. Affinchè ciò accada M non deve avere ne stati irraggiungibili ne stati equivalenti. Allora il DFA minimo sarà unico a meno dei nomi. Ora il mio dilemma è qual è la differenza tra il DFA minimo e quello canonico? Sono la stessa cosa?

Riporto anche la definizione di DFA canonico:
Detto A essere un DFA minimo. Se ogni DFA A' con lo stesso numero di stati è isomorfico con A, A è detto il DFA canonico

Spero che per l'autore del post non sia un problema.

Figurati! Anzi più gente partecipa più cose s'imparano...ma la gente scarseggia

Io sto impazzendo sull'implementazione dell'NFA e forse ho fatto un madornale errore che mi costringe a fare passi indietro...

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4868568#p4868568][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Sto rileggendo per bene, ma fatico un po'...

Cosa non ti è chiaro?

Intanto mi è venuta un'idea.
[...]
Per ora quello che ho pensato è questo.
Non so se può funzionare, potrebbero esserci degli inghippi sui cambi di stato che qui sulla carta non riesco a prevedere.

Potrebbe funzionare. Mi viene in mente un dubbio però, prendi in considerazione il grafo che ho postato il primo di aprile.
All'inizio il vettore di appoggio sarà Q = 1, 0, 0, 0 la matrice di adiacenza è

Codice: Seleziona tutto

	      s0  s1  s2  s3
     s0  1   1   0   0
     s1  0   0   1   0
     s2  0   0   0   1
     s3  0   0   0   0

Quindi leggo la prima riga della matrice trovo s0 s1 ad uno con simbolo '0', mi sposto quindi su s0: Q = 1, 0, 0, 0 e poi su s1: Q = 0, 1, 0, 0. Ma ora ho azzerato s0, ma non posso perché su s0 "ci sono" ancora. Sempre se ho capito bene cosa vuoi fare.

Infatti @Spider hai capito al volo.
Ho una marea di problemi da risolvere.
1) credo di aver impostato male gli eventi per l'nfa.
Per esempio (sotto)
pensavo di gestire l'evento 0,1 come evento (0)
if c=='0' || c=='1'
e l'evento 1 come 1.
Ma così facendo a q non ci andrò mai. Non posso usare l'OR
questo mi porta a capire che devo rivedere come compongo la matrice.

L'atra cosa si, è un bel grattacapo. Ci sono casi (ho fatto prove con i tuoi link) che per esempio:
s2 accede a s3 con 'b'
s3 si accende e s2 si spegne
Passo a s3: s3 si dovrebbe spegnere perchè non esce con eventi 'b'. Ma deve rimanere acceso perchè s2 l'aveva accesa!!!!

Bhà...si potrebbe pensare a qualcosa, ma la mia poca esperienza mi dice che quando rattoppi non è la strada giusta.
Il codice deve essere semplice ed elegante. Le correzioni ad hoc prima o poi...ti fregano
Cerco di rivedere la mia matrice di adiacenza con strutture.
Credo sia li il problema...quello maggiore intendo.

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869160#p4869160][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
Spero che per l'autore del post non sia un problema.
Figurati! Anzi più gente partecipa più cose s'imparano...ma la gente scarseggia
Io sto impazzendo sull'implementazione dell'NFA e forse ho fatto un madornale errore che mi costringe a fare passi indietro...

Ok grazie. Io ho avuto a che fare dal punto di vista implementativo solo con DFA ma in C++. Ma se vuoi implementare un NFA non dovrebbe essere difficilissimo. Se il numero degli stati è noto a compile-time e non cambia a run-time ,allora per la funzione di transizione puoi usare un array bidimensionale (le colonne sono tante quante i simboli dell'alfabeto) che contiene in ogni cella una lista (la lista dei nodi che è in numero variabile).
Se invece il numero di stati può crescere a runtime puoi usare una lista anche per gli stati. Ogni struct di uno stato dovrà contenere oltre al puntatore al prossimo stato anche un array (grande quanto l'alfabeto) in cui ogni elemento è a sua volta una lista che contiene l'elenco (gli indici) dei nodi di arrivo. Si possono pensare anche altre implementazioni ed è ovvio che la migliore soluzione dipende dal problema in questione.

cuccagna [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869153#p4869153][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Dato un linguaggio regolare L, un DFA M che riconosce L è minimo se M è un DFA con il minimo numero di stati. Affinchè ciò accada M non deve avere ne stati irraggiungibili ne stati equivalenti. Allora il DFA minimo sarà unico a meno dei nomi. Ora il mio dilemma è qual è la differenza tra il DFA minimo e quello canonico? Sono la stessa cosa?

Assolutamente sì, e lo conferma il teorema di Myhill-Nerode. Le due definizioni, solo in apparenza distinte, sono state introdotte in momenti storici diversi, e per motivi storici si trovano ancora indipendentemente in letteratura, ma si riferiscono al medesimo ente matematico, la cui univocità è peraltro sancita (seppure in modo leggermente diverso) dal medesimo enunciato della definizione. La classe di equivalenza alla quale fa apparentemente riferimento la definizione di DFA canonico è in realtà "collassata" in un solo DFA, quello minimo: a meno delle etichette, ovviamente.
In genere i migliori testi omettono l'una o l'altra definizione, allo scopo di evitare confusione, o ne spiegano chiaramente l'assoluta equivalenza: purtroppo non è così per testi più recenti o dispense molto sintetiche.

M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869250#p4869250][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
cuccagna [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869153#p4869153][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Dato un linguaggio regolare L, un DFA M che riconosce L è minimo se M è un DFA con il minimo numero di stati. Affinchè ciò accada M non deve avere ne stati irraggiungibili ne stati equivalenti. Allora il DFA minimo sarà unico a meno dei nomi. Ora il mio dilemma è qual è la differenza tra il DFA minimo e quello canonico? Sono la stessa cosa?
Assolutamente sì, e lo conferma il teorema di Myhill-Nerode. Le due definizioni, solo in apparenza distinte, sono state introdotte in momenti storici diversi , e per motivi storici si trovano ancora diffusamente in letteratura, ma si riferiscono al medesimo ente matematico, la cui univocità è peraltro sancita (seppure in modo leggermente diverso) dal medesimo enunciato della definizione. La classe di equivalenza alla quale fa apparentemente riferimento la definizione di DFA canonico è in realtà "collassata" in un solo DFA, quello minimo: a meno delle etichette, ovviamente.

La presenza di due definizioni e di due diverse nomenclature mi ha fatto sospettare che denotassero due concetti diversi sotto qualche aspetto che mi sfuggiva. Tuttavia l'idea che fossero figli gemelli della stessa madre era forte dato l'interscambiale uso che se ne fa in letteratura. Inoltre come fatto notare nella definizione di dfa canonico si fa riferimento al dfa minimo cioè ad un solo DFA (a meno dei nomi degli stati). Avevo anche pensato alle motivazioni storiche ma non sapevo come e dove trovare conferma, la sua nella fattispecie e in generale per questioni inerenti la computer science e non solo suona come la sentenza della Cassazione.

M_A_W_ 1968 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869250#p4869250][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
cuccagna [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869153#p4869153][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Dato un linguaggio regolare L, un DFA M che riconosce L è minimo se M è un DFA con il minimo numero di stati. Affinchè ciò accada M non deve avere ne stati irraggiungibili ne stati equivalenti. Allora il DFA minimo sarà unico a meno dei nomi. Ora il mio dilemma è qual è la differenza tra il DFA minimo e quello canonico? Sono la stessa cosa?
Assolutamente sì, e lo conferma il teorema di Myhill-Nerode. Le due definizioni, solo in apparenza distinte, sono state introdotte in momenti storici diversi, e per motivi storici si trovano ancora indipendentemente in letteratura, ma si riferiscono al medesimo ente matematico, la cui univocità è peraltro sancita (seppure in modo leggermente diverso) dal medesimo enunciato della definizione. La classe di equivalenza alla quale fa apparentemente riferimento la definizione di DFA canonico è in realtà "collassata" in un solo DFA, quello minimo: a meno delle etichette, ovviamente.
In genere i migliori testi omettono l'una o l'altra definizione, allo scopo di evitare confusione, o ne spiegano chiaramente l'assoluta equivalenza: purtroppo non è così per testi più recenti o dispense molto sintetiche.

Ha colto nel segno, la dispensa è una tesi di dottorato. Altri manuali omettono di sottolinearne l'equivalenza semplicemente ignorando una delle due nomenclature. C'è anche chi, in dispense molto sintetiche, ed articoli scientifici, non propriamente riguardanti FSA ed annessi, usa il concetto di dfa minimo/canonico intercambiabilmente come conoscenza di background preliminare. E anche se adesso il motivo mi è chiaro ciò può generare confusione.

cuccagna [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869258#p4869258][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Avevo anche pensato alle motivazioni storiche ma non sapevo come e dove trovare conferma, la sua nella fattispecie e in generale per questioni inerenti la computer science e non solo suona come la sentenza della Cassazione.

Il compito istituzionale di noi logici, a prescindere da quanto siamo propensi a baloccarci con le applicazioni (dall'elettronica digitale all'informatica teorica, con tutto quel che vi corre in mezzo), è sorvegliare sul modo in cui vengono fatte le cose in Matematica e in tutte le scienze formali: definizioni, nomenclatura, scelta degli assiomi, metodologie dimostrative, collegamenti tra le discipline. Dunque è professionalmente necessario avere le idee chiare a priori su una buona quantità di oggetti matematici, eventualmente anche cassando o modificando definizioni obsolete o confusionarie, per quanto possibile.

Ma come sempre i matematici (applicativi e non) si dividono in due categorie: quelli che hanno letto e capito Halmos, e quelli che pensano di non averne bisogno. Così ci ritroviamo in mano i DFA "canonici" sovrapposti a quelli minimi, oppure una mezza dozzina di diverse definizioni operative di "vettore d'inversione" in combinatorica (che ovviamente quasi ogni autore sembra dare per scontata, come se ve ne fosse una sola), per non dire delle definizioni inutilmente sovraspecificate come quella di ring of sets che viene normalmente gabellata nei corsi in Italia (funzionale unicamente alla teoria della misura, e nel più ampio quadro di una distorsione didattica della quale si lamentano almeno tre generazioni di docenti) rispetto a quella fondamentale in matematica discreta, e così via... ma qui stiamo già divagando, temo.

Se il numero degli stati è noto a compile-time e non cambia a run-time ,allora per la funzione di transizione puoi usare un array bidimensionale (le colonne sono tante quante i simboli dell'alfabeto) che contiene in ogni cella una lista (la lista dei nodi che è in numero variabile).

Infatti, io ho usato un array di strutture con colonne pari al numero di stati.
Riga 0 colonna 0 (esempio) mi indica dove può andare lo stato 0. Se il campo della struttura è a 1 significa che ci posso accedere.
Nell'esempio indicherebbe un "cappio" che si chiude con s0.
l'errore che dicevo, è che avevo previsto un campo solo per l'evento. Quindi s0 può accedere a se stesso o un altro stato ma con solo un evento.
Se per assurdo su s0 si richiudono più eventi, sono fregato.
Ho riparato modificando il campo della struttura adibita agli eventi con un array.
è tutto da testare, ma l'errore era questo.
Pensavo di gestire più eventi sullo stesso nodo con OR es: stato 0 accetta a || b || c come in un DFA, ma con gli NFA non è possibile.
Se a s1 accedo con 'a' non lo raggiungerò mai perchè' mi si ferma in s0, visto che avevo previsto evento 0= a||b||c ...

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4869475#p4869475][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:
Se il numero degli stati è noto a compile-time e non cambia a run-time ,allora per la funzione di transizione puoi usare un array bidimensionale (le colonne sono tante quante i simboli dell'alfabeto) che contiene in ogni cella una lista (la lista dei nodi che è in numero variabile).
Infatti, io ho usato un array di strutture con colonne pari al numero di stati.
Riga 0 colonna 0 (esempio) mi indica dove può andare lo stato 0. Se il campo della struttura è a 1 significa che ci posso accedere.
Nell'esempio indicherebbe un "cappio" che si chiude con s0.
l'errore che dicevo, è che avevo previsto un campo solo per l'evento. Quindi s0 può accedere a se stesso o un altro stato ma con solo un evento.
Se per assurdo su s0 si richiudono più eventi, sono fregato.
Ho riparato modificando il campo della struttura adibita agli eventi con un array.
è tutto da testare, ma l'errore era questo.
Pensavo di gestire più eventi sullo stesso nodo con OR es: stato 0 accetta a || b || c come in un DFA, ma con gli NFA non è possibile.
Se a s1 accedo con 'a' non lo raggiungerò mai perchè' mi si ferma in s0, visto che avevo previsto evento 0= a||b||c ...

Ho capito il tuo problema:
Ti consiglio di cambiare strategia. Fai un array bidimensionale. Nelle righe metti l'indice degli stati es. s0, s1, s2, s3 come stai facendo tu. Nelle colonne metti gli eventi possibili (se sono a,b,c gli eventi il numero di colonne è 4 perché devi considerare la epsilon-transizione per gli NFA). Per ogni cella metti una struttura dati, una lista ad esempio che contiene l'indice degli stati che è possibile raggiungere tramite quell evento. Ad esempio se da s1 tramite l'evento a è possibile raggiungere s2 ed s3, chiamando A il tuo array bidimensionale A[s1][a] = {s2,s3} .
Lo stato iniziale puoi sceglierlo di salvarlo nella prima riga (s0). Inoltre potresti aggiungere un'altra colonna all'array bidimensionale per indicare se lo stato è accettante.

Grazie @Cuccagna, ma mi sono un po' arenato...complice il fatto di avere poco tempo.
Ho risolto il problema degli eventi, ora dovrei implementare. Solo che sono un po' di cicli for innestati, e mi sto incasinando.
Se non dovessi postare nulla, grazie a tutti, e particolarmente a @Spider-net che mi ha davvero aiutato parecchio.
Io ci provo ancora, ma dubito...

Ci sto ancora provando, ma è un po' difficile e il tempo scarseggia.
Mannaggia a sti NFA

@Spider o chiunque se stai ancora leggendo, ed hai tempo, mi spiegheresti un po' nel dettaglio (anche con link) il metodo ricorsivo per l'nfa?
Stavo implementando il metodo degli stati "contemporanei", ma comporta casini assurdi..o almeno il gioco non vale la candela.
Ci sono troppi casi da gestire per esempio : uno stato può uscire con un evento e quindi azzerarsi, ma al tempo stesso lo stato precedente lo riaccende...
Avevo anche pensato di traformare l'nfa in un dfa e poi risolvere.
Però non so bene la tecnica, l'avrei dovuta studiare (cosa che per altro farò).
Nel caso grazie

Ciao Gila, per metodo ricorsivo intendi quello che ho implementato io?

spider-net [url=http://forum.ubuntu-it.org/viewtopic.php?p=4875677#p4875677][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Ciao Gila, per metodo ricorsivo intendi quello che ho implementato io?

Ciao spider. Si, intendo quello.
Come ho detto stavo tentando il metodo a più stati "contemporanei", ma trovo difficoltà. Non è così semplice.
Per esempio, col tuo automa, (quello del terzultimo 0 ) va, con altri no.
Vorrei ritornare su quello ricorsivo\backtracking, ma non mi è molto chiaro.
Senza impegno, se ti va sono qui

Partiamo dalle tre strutture dati.

stato: ogni stato ha un indice, può essere finale o meno ed ha una lista di transizioni;
listaStati: lista concatenata di stati, niente di speciale;
transizioni: come detto prima, ogni stato possiede una lista di transizioni. Dato un nodo x, ogni elemento di questa lista rappresenta una transizione (un arco uscente) dal nodo, o stato x al nodo y con il simbolo s.

In particolare se prendiamo come esempio il seguente NFA, le strutture dati sono le seguenti:

Immagine

Codice: Seleziona tutto

lista stati: | 0 |stato|     -->     | 1 |stato|     -->     | 2 |stato|     -->     | 3 |stato|    -->    | 4 |stato|
                    |                       |                       |                       |                     |
                    V                       V                       V                       V                     V
        | 0 | 'n' | trans |      | 1 | 'n' | trans |       | 2 | 'n' | trans |       | 3 | 'n' | trans |    | 4 | 's' | trans |

Dove 0,1, ..., n rappresenta l'indice dello stato. 's' o 'n' indicano rispettivamente se lo stato è finale o no. "stato" è il puntatore allo stato e "trans" è il puntatore alla lista di transizioni.

Ad esempio la lista di transizioni dello stato 0 è:

Codice: Seleziona tutto

| '0' |stato|     -->     | '0' |stato|     -->     | '1' |stato|
         |                         |                         | 
         V                         V                         V 
   | 1 | 'n' | trans |      | 2 | 'n' | trans |       | 3 | 'n' | trans |

Oppure la possiamo immaginare più semplicemente così:

Codice: Seleziona tutto

lista stati:         |qo, 'n'| -> |q1, 'n'| -> |q2, 'n'| -> |q3, 'n'| -> |q4, 's'|

transizioni di q0:   | '0', q1| -> | '0', q2| -> | '1', q3|
transizioni di q1:   | '0', q3|
transizioni di q2:   | '1', q3| -> | '0', q4|
transizioni di q3:   NULL
transizioni di q4:   NULL

Se ti viene più facile, pensa alla lista delle transizioni come la lista di adiacenza di un grafo, solo che si ha un campo in più che indica il simbolo con il quale si raggiunge il nodo.

Consideriamo la lista di stati e le liste di transizioni sopra (quelle semplici).
Vediamo ora la procedura nfa() ad esempio la chiamata nfa("00", q0): lo stato q0 è diverso da NULL, quindi si passa al ramo else, guardiamo se lo stato attuale, quindi q0 è finale e se abbiamo processato tutta la stringa in input, allora la stringa è accettata. Ma ora non è così, consideriamo la lista delle transizioni dello stato attuale, q0, la scorriamo (ciclo while), il primo simbolo della stringa corrisponde alla prima transizioni di q0, quindi facciamo una chiamata ricorsiva su nfa("0", q1).
Come ti sarai accorto se proseguiamo la stringa non sarà accettata, ma non fa niente perché poi torneremo indietro esplorando anche la transizione corretta.

Da q1 esploriamo la lista di transizioni di q1, e con il simbolo '0' andiamo in q3, quindi richiamiamo nfa("", q3). Siamo in q3, la stringa è vuota ma q3 non è finale, il while non viene eseguito perché la lista delle transizioni di q3 è vuota, restituiamo 0 (stringa non accettata). Risaliamo tutto lo stack delle ricorsioni e arriviamo alla prima chiamata ricorsiva fatta, cioè accettato = nfa("0", q1) che darà quindi risultato 0. Ci troviamo ora nel while della prima chiamata (non ricorsiva) a nfa, nfa("00", q0), ma subito dopo l'if. Questo è il punto cruciale, eseguiamo l'istruzione t = t->next;
Questa istruzione ci permette di esplorare un'altro percorso di transizioni che potrebbe portarci all'accettazione della stringa.

La lista di transizioni t, nella chiamata originale ad nfa() puntava a

Codice: Seleziona tutto

 | '0', q1| -> | '0', q2| -> | '1', q3|

Dopo l'istruzione t = t->next; ora t punta a

Codice: Seleziona tutto

 | '0', q2| -> | '1', q3|

Scartando quindi la scelta che ci ha portato alla non accettazione della stringa.
Ora ricorda che accettato vale 0, quindi il while viene eseguito un'altra volta, esploriamo la nuova lista delle transizioni di q0 e con il simbolo '0' andiamo in q2, facciamo quindi una chiamata ricorsiva ad nfa("0", q2).
Ci troviamo ora in q2, q2 non è finale, prendiamo la sua lista di transizioni, entriamo nel while, ma il simbolo della prima transizione non coincide con il simbolo della stringa da controllare, quindi l'if risulta falso, eseguiamo t = t->next; e passiamo quindi al prossimo elemento della lista di transizioni di q2. Il simbolo della transizione coincide con quello della stringa (entrambi '0'), richiamiamo quindi nfa("", q3). Dato che q3 è finale e la stringa è vuota, ritorniamo 1, uscendo quindi dal while della chiamata nfa("0", q2) e ritornando a sua volta 1, risalendo lo stack delle chiamate ricorsive ancora una volta, torniamo all'interno del while della chiamata originale nfa("00", q0). accettato vale 1, quindi si esce dal while e tutta la procedura nfa() torna 1, che sarà il risultato finale. Stringa accettata, STOP.

Il punto chiave sta tutto nell'usare una lista di transizioni e di usare t = t->next; così da scartare le scelte che ci hanno portato a non accettazione.

Se ad esempio non ci fosse uno stato di accettazione, l'algoritmo termina quando si esaurisce tutta la lista dello stato iniziale.

C'è qualcos'altro in particolare che non ti è chiaro?

Se non sei ancora convinto prendi qualche esempio di NFA, non troppo complessi e prova a simularlo a mano o a mente.

Grazie spider, domani non lavoro e provo a studiarci su. Non sono sicuro di poter adattare il ragionamento a come ho pensato io la costruzione
dell'NFA (io ho usato una matrice di adiacenze) o perlomeno devo ragionare e riadattare il tutto.
Qualche domanda veloce: non è meno prestante la ricorsione rispetto al metodo degli stati "contemporanei"?
Poi : gli nfa sono molto più semplici da pensare per un essere umano (molti meno stati per fare la stessa cosa) dei DFA.
Ma non sono più lenti? Cioè se io mo scrivo il mio nfa carta e penna e poi lo trasformo in DFA (sempre a programma intendo), non è molto più veloce il dfa?
Anche a livello d'implementazione un dfa, una volta fatta la matrice, è un gioco da ragazzi.
Certo ho il costo della trasformazione, ma viene fatta una sola volta. Anche un po' di memoria in più usata..
Intanto grazie mille....speriamo di riuscirci

gila75 [url=http://forum.ubuntu-it.org/viewtopic.php?p=4876754#p4876754][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Qualche domanda veloce: non è meno prestante la ricorsione rispetto al metodo degli stati "contemporanei"?

Poi : gli nfa sono molto più semplici da pensare per un essere umano (molti meno stati per fare la stessa cosa) dei DFA.
Ma non sono più lenti? Cioè se io mo scrivo il mio nfa carta e penna e poi lo trasformo in DFA (sempre a programma intendo), non è molto più veloce il dfa?

In termini di compattezza gli nfa sono in genere più efficienti. Pensa al DFA per riconoscere se il terzultimo carattere di una stringa è uno zero, il DFA minimo ha 8 stati, meglio di così non puoi fare, il suo nfa lo fai con 4 stati. Come avevo detto in un'altro post dato un NFA di n stati, il DFA corrispondente può avere fino a 2^n stati. Non prenderlo come un dogma, non in tutti i linguaggi il DFA ha un numero di stati esponenziale. 2^n è un limite massimo (upperbound).

In termini di tempo computazionale invece, ti risponderei con un "dipende". Dipende dall'implementazione in primis. Usando algoritmi paralleli l'NFA è più efficiente, usando però algoritmi non paralleli, il matching di una stringa tramite DFA è lineare sulla dimensione della stringa, invece per fare il matching di una stringa in un NFA, come abbiamo già detto ci sono due metodi: backtracking o tenere traccia degli stati attivi (quello che stavi provando a fare tu). Entrambi sono più costosi, in particolare l'ultimo metodo, per ogni transizione impiegherà al massimo tempo pari a n, con n dimensione dell'NFA.

Forum Ubuntu-it

[C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti