[C] Automi a stati finiti

[gila75]

Per esempio (grafico sotto):
come risolvo per una stringa "AABBAA" che è lecita?
Se non visito più volte i nodi da cui provengo (cosa proibita con DFS) non riesco.
Mi sa che mi sto incasinando di brutto!!!
oltretutto in rete, non trovo materiale di DFS+NFA e la cosa mi puzza un po', no?
ecco l'esempio:
lascia stare i pallini in rosa, calcola come fossero bianchi...ho fatto una foto mentre lo provavo. Vergine il grafo è bianco
Tutto si risolverebbe tra nodo S0 e S2, ma li devo visitare più volte...mannaggia!!!!
Mi sa che l'altro metodo è più semplice, ma non mi voglio arrendere
Credo a sto punto che vada effettuato un backtracking, ma senza il vincolo di non poter più rivisitare...ma non ci giurerei

[spider-net]

Ciao gila. Hai totalmente ragione, usando una DFS pura, in alcuni (molti) casi si preclude la possibilità di esplorare un'altro "cammino" che magari avrebbe portato ad uno stato di accettazione. Ma DFS non è proprio da buttare, infatti possiamo usare un'algoritmo simile, come ho fatto alcune pagine fa nel codice che ho postato. Quindi non è tutto lavoro buttato. Anzi DFS può essere usata in una categoria particolare di NFA per studiare la raggiungibilità.

[gila75]

L'importante è aver capito e non percorrere una strada sbagliata.
Certo che è servita la DFS, se non altro una palestra di programmazione e un concetto importante.
Ora per 5 giorni non farò nulla, parto per la Spagna per una mini gita.
Appena torno riordino le idee e provo\studio di nuovo.
Intanto ancora grazie per l'aiuto, sono concetti un po' difficili e avere una persona che ti segue aiuta molto.
Buona Pasqua @Spider e a tutti.

[spider-net]

Buona Pasqua anche a te!

[gila75]

ho poco tempo, ma mi è venuta un'idea sul metodo della computazione degli stati (abbandono il backtracking per ora)
Il problema con gli nfa è che non è possibile scrivere una matrice per un grafo orientato e pesato (come i DFA) perchè con lo stesso evento
si può andare in più stati contemporaneamente.
Il mio problema più grosso è questo.
Per esempio nel grafo sotto q0 accede a tre nodi con 2 eventi diversi.
Avevo pensato a strutture ecc. ma ho ripiegato con un altro metodo (da provare).
Mi scrivo la mia bella matrice di adiacenze per il grafo, poi una seconda matrice per le varie mobilità.
esempio il grafo sotto ha 2 eventi (0,1)
la matrice avrà righe pari ai nodi e colonne pari agli eventi. Marco a 1 se la mobilità è consentita.
Stabilisco a priori che
0=evento 0
1=evento 1.
quindi avrò:
q0 11 (mobile sia con 1 che con 0)
q1 10 ( mobile solo con 0)
q2 11 (mobile con 1 e 0)
q3 00 (non mobile)
q4 00 (non mobile)

Quindi quando mi entra un carattere letto da stringa es 0, ho l'evento 0. Leggo nella matrice in q0[0] ho 1, ok si muove con l'evento 0.
Ma dove si muove ? (il test era positivo), quindi vado alla matrice delle adiacenze e scopro che q0 con 0 va a q2 e q1.
Può essere un'idea valida?
Non so se incontrerò rogne nella stesura del programma, ma ci provo, sembrerebbe un'idea no?


Piccola divagazione: tempo fa come detto avevo usato la DFS per genereare un labirinto e il brute force per risolverlo...ma ragionando...
posso usare la DFS anche per risolverlo giusto?

[spider-net]

Potrebbe essere un'idea, devi solo decidere come determinare se la stringa viene accettata o meno. Nel senso che ad ogni transizione finisci in un insieme di stati a quel punto ti basta controllare che tale insieme contiene uno stato finale. In termini matematici che, dato S l'insieme degli stati raggiunti e F l'insieme degli stati finali, S ∩ F ≠ Ø.

Piccola divagazione: tempo fa come detto avevo usato la DFS per genereare un labirinto e il brute force per risolverlo...ma ragionando...
posso usare la DFS anche per risolverlo giusto?

Sì.

[gila75]

Potrebbe essere un'idea, devi solo decidere come determinare se la stringa viene accettata o meno.

Scorrerei l'intera stringa carattere per carattere.
Se il carattere non rientra negli eventi (o in gergo nell'alfabeto) esco subito, inutile proseguire.
Altrimenti vado fino alla fine, e se mi fermo in uno stato d'uscita è ok.
Facile a parole, magari implementarlo un po' meno.
So già che ci sarà una rogna, non so se risolvo, ma ci provo.
Dovrebbe occupare un po' di spazio in più due array di char, ma credo potrebbe risultare abbastanza veloce.

EDIT: no, non può funzionare

[spider-net]

Quale parte non funziona?

[gila75]

Se prendiamo il grafico sopra q0 va a q2,q3,q1.
Supponiamo entri 0, ok, ho la mobilità.
Vado nella matrice delle adiacenze e in q0 trovo
01110
ma non ho modo di stabilire che 0 va a q2 e q1 ma non q3
Cavolo che casino!!!

[spider-net]

Potresti usare una struttura che contiene due campi, uno per lo stato e uno per il simbolo. Così se nella matrice trovo 1, controllo il simbolo se è quello in input, ok.

[gila75]

piccolo esempio?
Ho guardato il tuo programma. Devo dire che le liste e le strutture non sono il mio forte.
Le uso poco e ogni volta tendo a dimenticare (le liste intendo)

[spider-net]

Puoi usare una struttura come ho fatto io. Oppure crei una nuova struttura del tipo:

Codice: Seleziona tutto

struct stato {
    int adiacente;   /* 0 - 1 */
    char simbolo;
};

E poi puoi usare questa struttura per creare una matrice di adiacenza di tipo struct stato.
E la usi come una matrice di adiacenza standard.

[gila75]

Forse @spider intendi una cosa così...ci ho provato

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#define N 5

struct mat_adj {
    int evento;
    int arco;
} adj_array[N][N];


void funzione           (struct mat_adj q[N][N]);
void azzera             (struct mat_adj q[N][N]);
void stampa_mat_adj     (struct mat_adj q[N][N]);



void azzera(struct mat_adj q[N][N])
{
    int row,col;
    for (row=0; row<N; row++)
    {
        for (col=0; col<N; col++)
         {
             q[row][col].arco=0;
             q[row][col].evento=0;
         }
           
    }
    puts("azzerato tutto");
}

void funzione(struct mat_adj q[N][N])
{
    int row,col;
    int ev,arc;
    puts ("-1 PER USCIRE");
    for (row=0; row<N; row++)
    {
        for (col=0; col<N; col++)
        {
            
            printf ("q[%d] collegato a ? (-1 for exit) ",row);
            scanf("%d",&arc);
            if (arc==-1)
                break;
            q[row][arc].arco=1;
            
            printf ("con che evento ? ");
            scanf("%d",&ev);
            q[row][arc].evento=ev;
            
        }
            printf ("COMPLETATA RIGA %d\n",row);
            puts("_______________________________________");
    }
}

void stampa_mat_adj(struct mat_adj q[N][N])
{
    int row,col;
    for (row=0; row<N; row++)
    {
        for (col=0; col<N; col++)
        {
            
            if (q[row][col].arco==1)
            {
                printf ("nodo q[%d] collegato a nodo q[%d] con evento [%d]\n",
                row,col,q[row][col].evento);
            }
            
        }
          
    }
}

int main(void)
{
    azzera  (adj_array);
    funzione(adj_array);
    stampa_mat_adj(adj_array);
    
  
return 0;
}

è un array bidimensionale di strutture
e l'output riferito al famoso grafico è questo:

Codice: Seleziona tutto

gila@ubuntu:~/Scrivania$ ./xx
azzerato tutto
-1 PER USCIRE
q[0] collegato a ? (-1 for exit) 1
con che evento ? 0
q[0] collegato a ? (-1 for exit) 2
con che evento ? 0
q[0] collegato a ? (-1 for exit) 3
con che evento ? 1
q[0] collegato a ? (-1 for exit) -1
COMPLETATA RIGA 0
_______________________________________
q[1] collegato a ? (-1 for exit) 3
con che evento ? 0
q[1] collegato a ? (-1 for exit) -1
COMPLETATA RIGA 1
_______________________________________
q[2] collegato a ? (-1 for exit) 4
con che evento ? 0
q[2] collegato a ? (-1 for exit) 3
con che evento ? 1
q[2] collegato a ? (-1 for exit) -1
COMPLETATA RIGA 2
_______________________________________
q[3] collegato a ? (-1 for exit) -1
COMPLETATA RIGA 3
_______________________________________
q[4] collegato a ? (-1 for exit) -1
COMPLETATA RIGA 4
_______________________________________
nodo q[0] collegato a nodo q[1] con evento [0]
nodo q[0] collegato a nodo q[2] con evento [0]
nodo q[0] collegato a nodo q[3] con evento [1]
nodo q[1] collegato a nodo q[3] con evento [0]
nodo q[2] collegato a nodo q[3] con evento [1]
nodo q[2] collegato a nodo q[4] con evento [0]
gila@ubuntu:~/Scrivania$ 

Poi per il resto ho già delle idee, per ora vorrei capire se intendevi così...sembrerebbe funzionare

[spider-net]

Esattamente gila, è la versione "matriciale" della lista che avevo scritto io.

[gila75]

Ottimo
Procedo allora...e mò vengono i dolori
Devo pensare come gestire 2 stati contemporanei, ci sto pensando e ora riguardo il tuo programma.

[spider-net]

A meno che usi algoritmi paralleli o distribuiti una vera computazione parallela non è possibile, puoi però, ad esempio usare una struttura dati (lista, stack, ...) per memorizzare i vari stati raggiungibili con un dato simbolo (vedi la lista di transizioni nel mio programma). Dovrai comunque esplorare le varie "opzioni" o percorsi uno alla volta.

[gila75]

Dovrai comunque esplorare le varie "opzioni" o percorsi uno alla volta.

e ma così facendo devo scorrere tutta la stringa e poi riavvolgerla e provare ancora, giusto?
Non mi piace molto.
Ci devo riflettere non è facile...come nulla del resto su questo argomento.

[spider-net]

Non proprio, prendi il mio programma, in particolare focalizziamo sulla procedura nfa().

Prediamo come grafo questo, riconosce tutte le stringhe in cui il terzultimo simbolo è 0:


Se eseguiamo il programma la lista delle transizioni sarà la seguente (con un po' di fantasia):

Codice: Seleziona tutto

s0: | '0', s0 | -> | '1', s0 | - > | '0', s1 |
s1: | '0', s2 | -> | '1', s2 |
s1: | '0', s3 | -> | '1', s3 |
s3: NULL

In cui ad esempio

Codice: Seleziona tutto

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

E' la lista di transizioni dello stato s0, il primo campo del rettangolino è il simbolo che porta al prossimo stato, cioè al secondo campo del rettangolino. Quindi da s0 con il simbolo '0' vado ad s0 stesso, con il simbolo '1' vado ad s0 e con '0' vado anche a s1.

Supponiamo che la stringa in input sia "000" e vediamo come si svolge la computazione della procedura nfa():
la variabile accettato parte da 0, entriamo nel ramo else del primo if, il secondo if è falso, quindi entriamo nel while (la condizione è vera). Il primo simbolo della stringa corrisponde al simbolo della (prima) transizione, quindi effettuo una chiamata ricorsiva a nfa passando la stringa "00" e lo stato s0 (seguo quindi la transizione riconosciuta). La stessa cosa avviene per la stringa "00" (mi sposto in s0 e richiamo nfa su "0" e s0) e per "0", mi sposto sempre su s0 e richiamo nfa() su "\n" e s0.
Ora il simbolo ('\n') non viene riconosciuto dalla prima transizione, quindi l'if interno al while fallisce e viene eseguito t = t->next passando quindi alla prossima transizione, che non verrà riconosciuta, come anche quella dopo, quindi ora t punterà a NULL, si esce dal while e l'ultima chiamata di nfa(), quella con "\n" e s0, ritornerà 0, che risalendo lo stack delle chiamate avremo che nfa("00", s0) sarà 0 (la nostra prima chiamata ricorsiva), quindi accettato sarà 0.
Questo vuol dire che abbiamo esaurito tutte le computazioni partendo come scelta iniziale la transizione che con il simbolo 0 porta a s0, ora verrà eseguito t = t->next che ci porta alla transizione | '1', s0 | che non verrà riconosciuta perché il simbolo è diverso (ora siamo all'interno della chiamata iniziale di nfa(), quindi primo zero), quindi si passa all'ultima transizione: | '0', q1 | che se continuiamo la computazione ci porterà ad uno stato finale.

Spero di aver reso l'idea e di aver chiarito qualche dubbio che avevi.

[gila75]

Porcaccia miseria domani mi alzo alle 5 e ora non riesco a riflettere.
Leggo tutto con molta cura più e più volte.
Mi sorge un dubbio: non è che con una matrice al posto delle liste è più difficile e mi sto incasinando?
Ho scelto la matrice solo per un discorso (come già detto) che le liste le ho studiate un po' di tempo fa e non ho mai preso molta
confidenza.
Però magari è solo una mia paranoia, forse matrice e liste comportano stesse difficoltà.
Grazie @Spider, domani leggo attentamente.
Ti prometto che arriverà un punto che metterò il risolto...ti sto tartassando
Ma forse per un argomento così non esiste il "risolto"... c'è il mondo da sapere

[spider-net]

Liste e matrici di adiacenza differiscono solo per memoria usata e velocità di iterazione e ricerca. Per il resto una vale l'altra. Memorizzando entrambe le stesse informazioni.
Io con i grafi mi trovo meglio con le liste, per il semplice fatto che per la stragrande maggioranza delle volte ho usato le liste.

Figurati, nessun disturbo. Se ti serve dimmi che ti rispiego o porto un'altro esempio commentato.