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:
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
Dopo l'istruzione t = t->next; ora t punta a
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.
