[C] Automi a stati finiti

[spider-net]

nella matrice, in posizione 0 per ogni riga, ho marcato 0, cioè non visitabile.
Lo 0 nel mio caso è la radice dell'albero o il padre, quindi si parte per forza di cose da li, e di conseguenza si esce solo, senza
mai poterlo visitare, giusto?

In realtà il nodo di partenza lo possiamo considerare anche come già visitato.
Comunque una DFS dovrebbe essere in grado di terminare correttamente a prescindere dal nodo di partenza che è stato scelto. Molto spesso accade che tale nodo sia il primo che compare nella lista di adiacenza o nella matrice, ma non è detto che debba essere per forza lui.

EDIT:

Ho postato anche la matrice come evolve se lanci il programma.
Se una riga è tutta zero (come la casella nera) non mi muovo e faccio un pop.
Ad un certo punto alla fine della matrice, continuo a fare pop (matrice tutta a zero), ma arrivo a esaurire lo stack...quindi ho finito.
Evoluzione della matrice:

Ottimo ben fatto

[gila75]

Capisco....si, il mio è stato un esercizio. A dire il vero criticabile magari da molti, sembra che voglio reinventare la ruota.
Ma io non ci lavoro col C, mi voglio anche divertire.
Poi logico, studio come le cose van fatte

[spider-net]

Guarda, alle volte reinventare la ruota aiuta a capire come funziona, poi io sono dell'idea che questi, sono ottimi esercizi per "allenarsi" e per capire, quindi tanto di cappello.

[gila75]

Grazie @spider ;
Ora ritorno dovrei riadattare tutto per i famosi automi non deterministci...prima o poi

[gila75]

Questo è un piccolo tool, molto simile a quello del grafico per gli automi, per genererare in automatico una matrice di adiacenze partendo
dal grafico (che ci siamo fatti carta e penna precedentemente).
è rozzo un po',usa scanf() e la dimensione del vettore la si deve compilare, ma come tool mordi e fuggi, piuttosto che compilare un array bidimensionale
magari di 30X30 va più che bene:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define R 8
#define C 8

void azzera             (char matrix [R][C]);
void componi            (char matrix [R][C]);
void azzera_nodo_radice (char matrix [R][C]);
void stampa_mat_adiac   (char matrix [R][C]);



void azzera (char matrix [R][C])
{
    int r,c;
    for (r=0; r<R; r++)
    {
        for (c=0; c<C; c++)
        {
            matrix[r][c]='0';
        }
    }
}     

void componi (char matrix [R][C])
{
    int r,c;
    int nodo;
    for (r=0; r<R; r++)
    {
        for (c=0; c<C; c++)
        { 
            printf ("collega nodo [%d] a nodo ?",r);
            scanf("%d",  &nodo);
                if (nodo==-1)
                    break;  
            matrix[r][nodo]='1';  
            printf ("nodo [%d] collegato a nodo [%d]\n", r,nodo);  
        }
        puts("-----------------------------------------------------");
    }  
}


void azzera_nodo_radice (char matrix [R][C])
{
    int r,c;
    for (r=0; r<R; r++)
    {
        for (c=0; c<C; c++)
        {
            if (c==0)
                matrix[r][c]='0';
        }
    }
}


void stampa_mat_adiac   (char matrix [R][C])
{
     int r,c;
    for (r=0; r<R; r++)
    {
        for (c=0; c<C; c++)
        {
            printf ("%c ", matrix[r][c]);
        }
        puts("");
    }
}

int main(void) 
{
    char matrix[R][C];
    puts ("-1 PER COMPLETARE RIGA");
    azzera(matrix);
    componi(matrix);
    azzera_nodo_radice(matrix);
    stampa_mat_adiac(matrix); 
    return 0;      

}  


   

Output:

Codice: Seleziona tutto

collega nodo [0] a nodo ?7
nodo [0] collegato a nodo [7]
collega nodo [0] a nodo ?-1
-----------------------------------------------------
collega nodo [1] a nodo ?5
nodo [1] collegato a nodo [5]
collega nodo [1] a nodo ?3
nodo [1] collegato a nodo [3]
collega nodo [1] a nodo ?7
nodo [1] collegato a nodo [7]
collega nodo [1] a nodo ?-1
-----------------------------------------------------
collega nodo [2] a nodo ?4
nodo [2] collegato a nodo [4]
collega nodo [2] a nodo ?6
nodo [2] collegato a nodo [6]
collega nodo [2] a nodo ?-1
-----------------------------------------------------
collega nodo [3] a nodo ?1
nodo [3] collegato a nodo [1]
collega nodo [3] a nodo ?7
nodo [3] collegato a nodo [7]
collega nodo [3] a nodo ?4
nodo [3] collegato a nodo [4]
collega nodo [3] a nodo ?-1
-----------------------------------------------------
collega nodo [4] a nodo ?3
nodo [4] collegato a nodo [3]
collega nodo [4] a nodo ?2
nodo [4] collegato a nodo [2]
collega nodo [4] a nodo ?-1
-----------------------------------------------------
collega nodo [5] a nodo ?1
nodo [5] collegato a nodo [1]
collega nodo [5] a nodo ?-1
-----------------------------------------------------
collega nodo [6] a nodo ?2
nodo [6] collegato a nodo [2]
collega nodo [6] a nodo ?-1
-----------------------------------------------------
collega nodo [7] a nodo ?0
nodo [7] collegato a nodo [0]
collega nodo [7] a nodo ?3
nodo [7] collegato a nodo [3]
collega nodo [7] a nodo ?1
nodo [7] collegato a nodo [1]
collega nodo [7] a nodo ?-1
-----------------------------------------------------
0 0 0 0 0 0 0 1 
0 0 0 1 0 1 0 1 
0 0 0 0 1 0 1 0 
0 1 0 0 1 0 0 1 
0 0 1 1 0 0 0 0 
0 1 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 1 0 1 0 0 0 0 
gila@ubuntu:~/Scrivania$ 

riferito a questo:

[spider-net]

Grande gila!

[gila75]

grazie @spider, ma è proprio un prototipo..sarebbe da migliorare. In alcuni casi credo non possa andare bene.Es: 2 nodi marcati non 0 e 1 ma
10 e 6, andrebbe a pallino. Io ho supposto che si parta da 0 come nodo padre.
Comunque, se hai voglia e tempo, posti un esempio di DFS con liste di adiacenza e ricorsione?
Poi, avevo pensato per un NFA (in fondo da li eravamo partiti):
Il mio problema è come fare a dire: il nodo 0 va a nodo 1 con gli eventi 0,1.
in un automa a stati finiti, si fa la tabella delle transizioni. Credo di aver capito che si tratta di grafo orientato e pesato.
Negli nfa non posso farlo, avendo più scelte.
Ma a sto punto, se io faccio un array di strutture?
La prima struttura [0] contiene gli eventi di nodo [0] es: 0,1 la seconda [1]=0 ecc...
è una cagata?

[spider-net]

grazie @spider, ma è proprio un prototipo..sarebbe da migliorare. In alcuni casi credo non possa andare bene.Es: 2 nodi marcati non 0 e 1 ma
10 e 6, andrebbe a pallino. Io ho supposto che si parta da 0 come nodo padre.
Comunque, se hai voglia e tempo, posti un esempio di DFS con liste di adiacenza e ricorsione?

Appena ho tempo libero lo scrivo.

Poi, avevo pensato per un NFA (in fondo da li eravamo partiti):
Il mio problema è come fare a dire: il nodo 0 va a nodo 1 con gli eventi 0,1.
in un automa a stati finiti, si fa la tabella delle transizioni. Credo di aver capito che si tratta di grafo orientato e pesato.
Negli nfa non posso farlo, avendo più scelte.
Ma a sto punto, se io faccio un array di strutture?
La prima struttura [0] contiene gli eventi di nodo [0] es: 0,1 la seconda [1]=0 ecc...
è una cagata?

E come codificheresti la struttura? Con tanti campi quanti il numero di stati raggiungibili dal nodo i?
L'unico problema è che non sai quante transizioni può avere un nodo. A meno che mi porti un'esempio un po' più chiaro su come codificheresti la struttura, resto dell'idea che una lista di transizioni sia l'idea più semplice.

[gila75]

E come codificheresti la struttura? Con tanti campi quanti il numero di stati raggiungibili dal nodo i?
L'unico problema è che non sai quante transizioni può avere un nodo.

Si, l'idea (sui due piedi, dovrei provare) era quella. Il nodo zero si può muovere con evento 0,1 esempio.
Nella struttura 0 ho due campi 0,1.
quando arrivo al nodo 0, leggo la struttura corrispettiva, che ha 0 e 1, quindi mi muovo.
Nodo 3 evento 0.
nella struttura 3 leggo che movimenti ha il nodo 3 e così via.
Può essere ?
Ripeto, l'ho pensata tra una faccenda e l'atra, devo riprendere in mano bene il concetto. Solo un'idea.
Dovrei studiare le liste di adiacenza e i pro e i contro rispetto alle matrici.

[spider-net]

Però in un NFA è permesso che dal nodo 0, con il simbolo '0' vada nello stato 1, 2, 3, 6, 0, 12 (ad esempio) e magari con il simbolo '1' non vado da nessuna parte. Quindi per il simbolo 0 ti serve un vettore di stati? Ma quanto lungo? Non puoi saperlo a priori.

[gila75]

Però in un NFA è permesso che dal nodo 0, con il simbolo '0' vada nello stato 1, 2, 3, 6, 0, 12 (ad esempio) e magari con il simbolo '1' non vado da nessuna parte. Quindi per il simbolo 0 ti serve un vettore di stati? Ma quanto lungo? Non puoi saperlo a priori.

Vero.
Devo schiarirmi le idee. Intanto mi guardo le liste di adiacenza. E rivedo il programma che hai postato.

[gila75]

la dfs l'ho capita, è stata fatta, ma con gli NFA sono ancora
Per esempio: qual'è la stringa accetta dall'automa sotto?
00 mi porta in q3, ma non è l'uscita
00 mi porta anche in q4 e sarebbe accettata.
Ma 0000 ? Sarebbe accettata?
Non avendo i cappi che si chiudono sui nodi, faccio fatica a ragionare.
00 forse mi porterebbe a q3, ma non è l'uscita, allora col backtracking della dsf torno al nodo zero
ed esploro in direzione di q4 è così?
In definitiva accetta un numero qualsiasi di zeri?

[spider-net]

00 forse mi porterebbe a q3, ma non è l'uscita, allora col backtracking della dsf torno al nodo zero
ed esploro in direzione di q4 è così?

Sì, se la vuoi pensare come in un grafo.

Il linguaggio accettato è solo la stringa "00" perché dallo stato finale non esci con nessun simbolo.

Se vuoi strumenti automatici per costruire e testare automi:
http://automatonsimulator.com/
http://ivanzuzak.info/noam/webapps/fsm_simulator/

[gila75]

Ottimi link...grazie, davvero molto utili (per ora ho approfondito solo il primo).
Mi esercito, cerco di capire bene, poi provo a scrivere un NFA con DSF.
Poi al limite discutiamo, se ti va

[spider-net]

Certo.

[gila75]

Una domanda: esercitandomi col secondo link mi viene un dubbio.
Siamo sicuri che la DFS possa soddisfare la ricerca col backtracking?
Forse mi sto confondendo, ma mi pare che a volte si debba per forza rivisitare nodi già esplorati, cosa che la dfs non permette.
Non ci scommetto di aver visto giusto, ma mi pare di si.
Domanda a sto punto: non è che mi sono perso con la dfs (che tra l'altro averla implementata, male non mi fa), ma che non centra?

[spider-net]

Con il termine backtracking si intende un algoritmo generale per trovare, dato un problema, una soluzione. DFS è una forma specifica di backtracking applicabile ai grafi.

Porta un'esempio in cui secondo te DFS non funziona.

[gila75]

Porta un'esempio in cui secondo te DFS non funziona.

Adesso devo prepararmi per andare al lavoro purtroppo e non riesco.
Se generi degli nfa col secondo link, e provi a ragionare con la dfs, mi pare che a volte devi ripassare su un nodo già visitato (ripeto mi pare
L'esempio che facevamo, quello col nodo 3 e 4 "tronchi" è molto facile, ma se si complica la cosa, con la dfs mi risulta un casino.
Gli stessi "cappi" mi danno da pensare su come gestirli.
Va bhè, sapevo già a priori che non sono argomenti che in 2 giorni te la sbrighi....

[spider-net]

Quando hai tempo porta un'esempio che ragioniamo.

[gila75]

ok