[C] Automi a stati finiti

[gila75]

Penso di aver capito il backtracking...vediamo.
Ho la stringa "00".
parto da q0 e inizio col primo carattere della stringa: "0"
q0 con "0" mi porta a q1 e q2.
Nella lista o matrice trovo prima q1, quindi lo seguo: sono in q1.
Passo al secondo carattere: "...0"
q1 con "...0" porta a q3 riconosco che la stringa è finita (es '\0'), ma q3 non è un'uscita.
Allora retrocedo con lo stack: sono in q1. q1 però non ha altri archi uscenti con "...0" (se non q3 chè già stato visitato)
Retrocedo ancora, sono in q0: q0 ha un altro arco uscente (q2) e anche l'evento è giusto...quindi ora sono in q2.
Avanzo anche con la stringa ecc...
In poche parole ad ogni passo buono avanzo anche con la stringa e ad ogni back retrocedo sempre con la stringa di un char. Giusto?
Se è così non mi resta che implementarlo. Non so se con la matrice devo riadattare un po', ci provo.
Mi confermi il ragionamento ?

[spider-net]

Confermo gila.

[gila75]

Ok, grazie.
Tempo permettendo provo a implementare con un'array di strutture.
Ormai sono partito così...perlomeno ci provo

[gila75]

Un'ultima domanda spider...
Con l'ultimo grafo (quello che accetta 00) penso di aver capito.
ti sposti di un carattere alla volta e azzeri l'evento. In modo tale che ripercorrendo a ritroso lo stack non posso ripercorrere la stessa strada.
Giusto?
Ma nel caso degli automi con il cappio (evento che si richiude sullo stato) il mio ragionamento non funziona.
L'automa del terz'ultimo zero se io inserisco 0000 non funziona il mio ragionamento.

Se va avanti così sarò costretto a mollare, è un casino !!!!

[spider-net]

Un'ultima domanda spider...
Con l'ultimo grafo (quello che accetta 00) penso di aver capito.
ti sposti di un carattere alla volta e azzeri l'evento. In modo tale che ripercorrendo a ritroso lo stack non posso ripercorrere la stessa strada.
Giusto?

Sì.

Ma nel caso degli automi con il cappio (evento che si richiude sullo stato) il mio ragionamento non funziona.
L'automa del terz'ultimo zero se io inserisco 0000 non funziona il mio ragionamento.

Se va avanti così sarò costretto a mollare, è un casino !!!!

Infatti non puoi azzerare s0. L'approccio non è corretto.

Ad esempio nel caso in cui la stringa sia "0000", la mia implementazione si comporta nel seguente modo:
la lista di transizioni di s0 è:

Codice: Seleziona tutto

s0: | '0', s0 | -> | '1', s0 | - > | '0', s1 |

ed effettua le seguenti chiamate a nfa():

Codice: Seleziona tutto

nfa("0000", s0) -> nfa("000", s0) -> nfa("00", s0) -> nfa("0", s0) -> nfa("", s0)

In particolare dato che nell'ultima chiamata, il simbolo '\0' non verrà riconosciuto da nessuna transizione, terminerà con risultato 0 (non accettato), quindi si torna alla chiamata precedente, la quale sceglierà la seconda transizione con il simbolo '0' (quella che porta a s1) che non portando ad uno stato di accettazione, terminerà con risultato 0. Quindi si passa alla chiamata precedente, che anch'essa sceglierà la seconda transizione con '0', terminerà con risultato 0, perché arriverà ad s2 che non è finale. Si giunge quindi alla chiamata nfa("000", s0) che sceglierà la seconda transizione con '0', andando quindi in s1, poi s2 e infine s3, quindi termina in uno stato finale e la stringa viene accettata.

[gila75]

Grazie.
Ho capito che il primo automa (00) funziona per caso con il mio ragionamento.
La tua spiegazione su quelli col "cappio" non l'ho ancora capita bene. Sto rileggendo tutti i tuoi post, ma per ora ancora nebbia.
Mi sto (forse) intestardendo in argomenti troppo difficili da studiare da solo.
è che sono davvero interessanti.
Rileggo ancora e cerco di capire

[spider-net]

La tua spiegazione su quelli col "cappio" non l'ho ancora capita bene. Sto rileggendo tutti i tuoi post, ma per ora ancora nebbia.

Può anche essere che non sia il massimo a spiegare le cose

Comunque nell'automa che riconosce il terzultimo zero, c'è un cappio (o come lo si chiama di solito "self loop") nel primo stato, questo vuol dire che per come è stata scritta la lista di transizioni di s0 (con la coppia '0', s0 come prima transizione) verrà sempre scelta la prima transizione, finché la stringa non viene "consumata" tutta, a quel punto si torna alla chiamata precedente (quella in cui la stringa è composta da un solo 0 e mi trovo in s0) e si sceglie la seconda transizione di s0, che non mi porterà ad uno stato finale, quindi si torna ancora indietro (quando la stringa era "00" e lo stato corrente era s0) scegliendo la seconda transizione di s0, anch'essa non terminerà di uno stato finale e infine si torna indietro a quando la stringa era "000" sempre sullo stato s0 che terminerà in s3, quindi la stringa verrà accettata.

[gila75]

Può anche essere che non sia il massimo a spiegare le cose

No, no, non intendevo quello, era inteso che sono confuso io.
Credevo semplicemente di avanzare nello stato successivo in base all'evento.
Avanzo e azzero l'evento e aumento lo stack.
Non trovo, retrocedo con la stringa e con lo stack.
Ma col "cappio" non funziona. E qui mi arrovvello.
Spero a sto punto che il problema non sia come ho pensato l'array di strutture e gli eventi perchè se no è tutto da rifare.
Ma non credo, quello dovrebbe essere ok.
Pestando il naso, mi accorgo come alberi, grafi e relativi algoritmi\argomenti non siano così facili.
Ma anche se ho la tendenza a impantanarmi in fatiche assurde (come una volta mi ha detto M_A_W) non voglio mollare, è un'argomento
troppo interessante.
Ci riprovo spider, grazie.

[gila75]

ho questo automa (fondo pagina)
la mia stringa è 111
quindi ho l'evento 1 che si chiude su q0 è lo stack sarebbe:
[1] "1"
[2]"11"
[3]"111"

Sarebbe l'evoluzione della stringa a ogni evento con buon esito: q0 si chiude su q0 con 0 quindi avanzo con la stringa.
ok ora l'ho "consumata" tutta.
Il secondo evento di q0 (0)non corrisponde al carattere, quindi q0 non può fare nulla.
Ho esaurito la stringa, ma non sono in uno stato d'uscita e non ho esaurito gli eventi di q0 (che vanno altrove), quindi devo tentare altro.
Allora faccio un pop sullo stack e sarò in
[2]"11"
seguendo l'evento 1 che da q0 va a q1 sono appunto in q1 e ho aumentato la stringa: "111".
Stringa esaurita e stato ok: accettata.
Stesso discorso per l'automa del terz'ultimo zero, anche se un po' più complesso (devo verificare bene carta e penna )
Il mio errore concettuale (se adesso è giusto il mio ragionamento) è che io tenevo traccia nello stack degli stati.
Mentre qui tengo traccia dell'evoluzione della stringa.
Comunque se fosse così, ho misere probabilità di riuscire a implementare...ci sono un trilione di cose da gestire.
Ma una cosa alla volta. Per ora mi preme la teoria

[spider-net]

Stesso discorso per l'automa del terz'ultimo zero, anche se un po' più complesso (devo verificare bene carta e penna )
Il mio errore concettuale (se adesso è giusto il mio ragionamento) è che io tenevo traccia nello stack degli stati.
Mentre qui tengo traccia dell'evoluzione della stringa.
Comunque se fosse così, ho misere probabilità di riuscire a implementare...ci sono un trilione di cose da gestire.
Ma una cosa alla volta. Per ora mi preme la teoria

Il ragionamento è corretto, tu hai scelto di farlo al contrario, cioè ad ogni transizione corretta aumenti la stringa di '1', io la decremento (nel senso che rimuovo un simbolo). Però il ragionamento è giusto comunque.