[Algoritmi][C] implementazione automa stati finiti NFA

Linguaggi di programmazione: php, perl, python, C, bash e tutti gli altri.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

[Algoritmi][C] implementazione automa stati finiti NFA

Messaggio da gila75 »

Buona sera a tutti.
Vorrei chiedere a chi conoscesse gli automi a stati finiti non deterministici come di solito s'implementano.
Un automa a stati finiti deterministico, avevo imparato a gestirlo proprio qui sul forum grazie ad un utente (il grande Claudio F.)
Ma è semplice, s'implementa un' array bidimensionale che funge da grafo orientato e pesato.
In un NFA le cose si complicano.
Ogni nodo può con lo stesso evento andare in più nodi contemporaneamente.
Supponiamo nodo 0 entra evento 0.
Il nodo 0 con evento 0 si collega a: se stesso , nodo 1 e a nodo 2.
quindi la propagazione avviene in simultanea e va gestita.
La mia domanda è: tipicamente sapete la tecnica d'implementazione ? liste? strutture ? Metodi ricorsivi ? (vi prego ditemi di no !!! :D )
Io ho trovato una soluzione (che va testata per bene) che fa uso di un array 3d. Magari si usa proprio così e io non lo so.
Sembra carina e se qualcuno sa qualcosa e gli interessa discutere, posso postare materiale.
Grazie nel caso in anticipo
Ultima modifica di gila75 il domenica 7 novembre 2021, 20:46, modificato 1 volta in totale.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da gila75 »

NFA.odt
(40.03 KiB) Scaricato 62 volte
Per chi fosse interessato ho scritto la spiegazione di come ho fatto.
A breve posterò il programma. Prima voglio verificare eventuali bug .
Magari non è interessato nessuno, ma magari in futuro...
Avatar utente
vaeVictis
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 4703
Iscrizione: venerdì 27 luglio 2012, 17:58
Desktop: Gnome
Distribuzione: Ubuntu 20.04 64bit

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da vaeVictis »

La discussione, ameno per me, è interessante, ma al momento non ho avuto il tempo per intervenire adeguatamente.
Appena posso, butto un occhio al file che hai allegato.

Potresti nel frattempo linkarmi la discussione in cui parlavi con Claudio F degli automi deterministico a stati finiti?
Pirates arrrrrrrrrrr awesome!!!
«I fear not the man who has practiced 10000 kicks once,
but I fear the man who has practiced one kick 10000 times.»
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da gila75 »

Potresti nel frattempo linkarmi la discussione in cui parlavi con Claudio F degli automi deterministico a stati finiti?
Appena riesco la cerco
La discussione, ameno per me, è interessante, ma al momento non ho avuto il tempo per intervenire adeguatamente.
Appena posso, butto un occhio al file che hai allegato.
Io tante volte scrivo anche se nessuno interviene, magari torna utile ad un futuro utente.
Ho cercato d'implementare un'automa a stati finito non deterministico usando un array a 3d dimensioni.
Sfrutta più o meno la logica degli automi a stati finiti dove si usa un array bidimensionale come una matrice di adiacenze.
Negli NFA non puoi fare così. Allora mi sono "inventato" di usare la parte tridimensionale (vedilo come un cubo) per salvare altri dati.
Insomma credo possa essere funzionale senza scomodare le liste (quindi malloc, puntatori a puntatori) e la temuta (per me) ricorsione, che è vero
che ti toglie dai pasticci in poche righe, ma estremamente contro intuitiva e gravosa a livello di prestazioni\memoria.
Il programma funziona, devo solo fare più test per eventuali bug (che arrivano sempre quando pensi sia tutto ok :D ) e aggiungere un pezzo.

EDIT:
viewtopic.php?f=33&t=606507&hilit=automi+a+stati+finiti

EDIT2:
questa è una prima bozza funzionante, da ritoccare e renderla funzione in futuro.
Ripeto: grosso modo è una matrice di adiacenze, ma sfrutto la terza dimensione dell'array : array[x][y][z].
Sembra complicato ma non lo è.

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void)
{
	const short int array[4][3][4]=	{
	{{0,-1,-1,-1}, 	 	{1,3,-1,-1},    {1,3,-1,-1}},
	{{3,-1,-1,-1}, 	 	{-1,-1,-1,-1},  {-1,-1,-1,-1} },
	{{-1,-1,-1,-1},		{2,1,-1,-1},    {-1,-1,-1,-1} },
	{{3,1,-1,-1},             {1,-1,-1,-1},   {1,-1,-1,-1 }}
	};

	//"cbaaaac";
	char s[]="bcacaaacababacabaa";
	int stack[2][4]={ {0},{0} };
	int cont[2][1]={ {0},{0} };
	int i=0;
	int doppi[4]={-1,-1,-1,-1};
	int k=0;
	int event,j,x,w;
	int a=0;
	int b=1;
	int len=strlen(s);
	

	if (s[0]=='a')
		event=0;
	else if (s[0]=='b')
		event=1;
	else if (s[0]=='c')
		event=2;
	else
		{
			printf ("[%c] carattere non valido",s[0]);
			return 0;
		}
// precaricamento stack primo "giro"
	while (array[0][event][i]!=-1)
	{
		stack[a][cont[a][0]]=array[0][event][i];
		cont[a][0]++;
		i++;
	}
	i=0;
	
	
					
	for (j=1; j<len; j++) // scansiono la striga
	{
    	
		if  (s[j]=='a') 
			event = 0;
		else if 	(s[j]=='b')
			event = 1;
		else if 	(s[j]=='c')
			event = 2;
		else
		{
			printf ("[%c] carattere non valido",s[j]);
			return 0;
		}
		
		while (cont[a][0]>0)
		{
			while (array[ stack[a][k] ][event][i]!=-1)
			{
				
				if  (doppi [array [ stack[a][k] ][event][i]  ]==-1)
				{
					stack[b][cont[b][0]]=array[ stack[a][k] ][event][i];
					printf ("stack %d\n", stack[b][cont[b][0]] );//getchar();
					doppi [stack[b][cont[b][0]]]=1;
					++cont[b][0];
					i++;
				}
				else 
				{
					i++;
					break;
				}
			}
				
			k++;i=0; 
			cont[a][0]--;
			
					
		}
		puts("----------esco---------");//getchar();
		k=0;
		a=a^1;b=b^1;  // INVERTO GLI STACK
		if (cont[a][0]==0 ) 
		{
			printf (" uscita prematura in %c pos[%d]\n",s[j],j+1);
			return 0;
		}
		for (w=0; w<4; w++)
			doppi[w]=-1;
	}
		
	puts ("-----NODI RIMANENTI-----");
	for (x=0; x<cont[a][0]; x++)
		printf ("[%d] ", stack[a][x]);
	puts("\n--------------");
	return 0;
					    
}
 
output:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ ./xx
stack 1
----------esco---------
stack 3
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 3
stack 1
----------esco---------
stack 3
stack 1
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 1
----------esco---------
stack 3
----------esco---------
stack 3
stack 1
----------esco---------
-----NODI RIMANENTI-----
[3] [1] 
--------------
gila@gila-pc:~/Scrivania$ 





questo listato è stato fatto su questo automa:
Allegati
automa_last.png
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da gila75 »

Per correttezza dico che la gestione dei nodi doppi in alcuni casi presenta un bug. Spesso in situazioni del genere si presentano casi che non puoi prevedere. Ci sto lavorando per risolvere.
Lavorare con array al posto delle liste, potrebbe essere vantaggioso. Ma è facile confondersi con gl'indici.
In più su array grossi potrebbe presentarsi il problema delle matrici sparse. Uno spreco di memoria in poche parole. Spero non arrivi MAW...sicuro che mi fa a pezzi !!!
Avatar utente
Claudio_F
Entusiasta Emergente
Entusiasta Emergente
Messaggi: 1463
Iscrizione: lunedì 28 maggio 2012, 18:49
Desktop: Mate/Gnome
Distribuzione: Ubu22.04

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da Claudio_F »

Maledizione, un argomento interessante che mi sveglia dal letargo :D

Sono già passati sei anni? :o

Premetto che non ho mai pensato a come realizzare un NFA tramite tabelle di transizione, trovo molto più pratico usare magari diversi DFA (ambito specifico automazione), ma soprattutto espressi in forma algoritmica:

Codice: Seleziona tutto

Se sono in questo stato
    E avviene questo
        ALLORA faccio questo (e cambio stato se serve).
L'unico caso pratico in cui ho usato la tabella è per la lettura dell'encoder rotativo della sveglietta autocostruita sul comodino :D

Codice: Seleziona tutto

const uint8_t tabT[7][4] = {
    { 0, 4, 1, 0 },
    { 2, 1, 1, 0 },
    { 2, 3, 1, 2 },
    { 2, 3, 3, 0 },
    { 5, 4, 4, 0 },
    { 5, 4, 6, 5 },
    { 5, 6, 6, 0 }
};

void readEncoder(void)
{
    static uint8_t  f = 0;           // stato processo lettura fasi

    uint8_t enc = (digitalRead(ENCODER_B) << 1) | digitalRead(ENCODER_A);

    onUp = (3 == f  &&  3 == enc);   // transiz. 3-->0  uno scatto avanti
    onDn = (6 == f  &&  3 == enc);   // transiz. 6-->0  uno scatto indietro

    f = tabT[f][enc];                // nuovo stato
}
Ma veniamo all'NFA, che ha come caratteristica di base il fatto di poter avere più stati attivi contemporaneamente, e come caso limite anche tutti attivi.

Ho difficoltà a seguire il codice, ma lo imposterei partendo dalle seguenti considerazioni che forse sono state anche le tue:

- In un DFA lo stato dell'automa può essere rappresentato da un solo valore numerico, mentre in un NFA serve un array, i cui elementi rappresentano l'attività o inattività dei singoli stati.

- In un DFA dall'incrocio della tabella stato(riga)/evento(colonna) si ottiene il nuovo stato sotto forma di numero, mentre in un NFA dall'incrocio si deve ottenere un array di nuovi stati attivi. E quindi si, viene fuori una matrice 3D.

- Siccome in un NFA gli stati attivi possono anche essere... tutti... si deve valutare la tabella stato-evento per ogni stato attivo, e i diversi array di attivazioni ottenuti vanno messi in OR binario tra loro per ottenere il nuovo stato globale, da copiare solo alla fine nell'array di stato corrente. Possiamo definire questo ultimo passaggio come "aggiornamento sincrono".


Dopo di che si potrebbe ulteriormente generalizzare l'automa, consentendo eventi diversi in parallelo gestiti da stati differenti, basta usare anche un array di eventi facendo l'OR di tutti gli array di attivazioni ottenuti dagli incroci tra tutti gli stati attivi e tutti gli eventi presenti.

Con questo gestisci anche robot indipendenti che si devono coordinare autonomamente su spazi condivisi, MA... è assolutamente vero il problema delle matrici sparse. Ad esempio anche un DFA si può benissimo realizzare in questo modo, ma con 10 stati e 10 eventi se non sbaglio abbiamo una matrice 3D di 1000 elementi di cui valorizzati solo 100. Inoltre applicare quanto detto a un caso reale (cioè compilare a mano o in lavatrice la tabellona) è da spararsi... lo trovo sensato e interessante solo dal punto di vista accademico, didattico o come virtuosismo matematico/informatico :)
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da gila75 »

Che piacere risentirti Claudio!!
Ora non sono a casa, appena ho il pc ti rispondo ed espongo un po' i miei dubbi e cosa ancora devo risolvere.
Grazie intanto per l'interessamento


Eccomi al pc:
lo trovo sensato e interessante solo dal punto di vista accademico, didattico o come virtuosismo matematico/informatico :)
Certo, come detto molte volte, io mi diverto, non ci lavoro con la programmazione. Mi piace cercare di capire cosa gira... Giusto ? Sbagliato?
Chi lo sa, molto probabilmente sbagliato, ma come detto è solo un hobby.

Per quanto riguarda le matrici sparse: si lo so non è il massimo. Ho letto che ci sono svariati modi per ovviare. Solo con questo argomento ci sarebbe tanto materiale da studiare...per il momento passo.
é vero anche che con la memoria disponibile di un pc (rimane comunque una pratica errata) ci si può permettere un po' di sprecare.
Array di 20x20x20=8000 Supponiamo di short int 8000x16 bits=16 k bytes non molto.
Tralasciando la leggibilità o meno del programma che ovviamente è sempre difficile se non l'hai scritto tu la logica di base è questa:
riga (nodo)\colonna(evento) intersecano l'array che contiene le transizioni possibili.
Questo array lo scansiono fino a-1 che indica che non ci sono più transizioni memorizzando tutto nello stack.
Di stack ne uso 2 : uno viene letto e riversa il contenuto sul secondo (stack a stack b).
Al giro dopo inverto: leggo da b e riverso in a e uso lo XOR per invertire.
Ostica la gestione dei nodi doppi:
Possiamo accedere allo stesso nodo , ma inutile memorizzare due volte
Es: siamo in 0 e 1. Tutti e due arrivano a nodo 3 con evento 'c'.
inutile memorizzare 3,3
per questo uso l'array doppioni che marca ad un nodo già visitato.
Ma che succede? Io potrei marcare preventivamente un nodo già visitato, ma se quel nodo è presente nello stack e lo dovrò "svolgere"
essendo marcato sarà ignorato.
Un'idea sarebbe dire: marca preventivamente un nodo già visitato , ma se sarà presente nello stack no. Lo dovrò usare.
Ci sto lavorando
Inoltre applicare quanto detto a un caso reale (cioè compilare a mano o in lavatrice la tabellona) è da spararsi...
Certo ma in qualche modo anche nei programmi reali si deve pur dire alla macchina come è il nostro grafo.
Nei DFA avevo inserito un tool che dicevi tu (input da terminale) chi era collegato con chi e con che evento e lui ti compilava la
matrice di adiacenze. Una stupidata in fondo. Si potrebbe applicare anche qui.
Se hai voglia o tempo mi piacerebbe sapere se hai consigli
(cioè compilare a mano o in lavatrice la tabellona)
:D :D :D l'ho capita dopo un po'...il tuo solito umorismo sottile mi apre ;)

Edit

Segnalo quest bel link, dove si possono generare dfa o nfa in modo random e seguire le transizioni.
Momentaneamente non crea più il grafico, magari il sito è in manutenzione.
Io lo uso per testare il mio listato.
speriamo riparta:
https://ivanzuzak.info/noam/webapps/fsm_simulator/

Credo che abbia scovato qualche bug. L'automa postato sopra( generato da quel sito) secondo me ha un errore:
Al nodo s2 non c'è nessuno modo di accedere. E' come se non esistesse. E non è sensato.
gila75
Imperturbabile Insigne
Imperturbabile Insigne
Messaggi: 2739
Iscrizione: mercoledì 16 gennaio 2013, 17:28
Desktop: ubuntu-2d
Distribuzione: Ubuntu 12.04.2 LTS i686
Località: Airuno(Lecco)

Re: [Algoritmi] implementazione automa stati finiti NFA

Messaggio da gila75 »

Ma che succede? Io potrei marcare preventivamente un nodo già visitato, ma se quel nodo è presente nello stack e lo dovrò "svolgere"
essendo marcato sarà ignorato.
Un'idea sarebbe dire: marca preventivamente un nodo già visitato , ma se sarà presente nello stack no. Lo dovrò usare.
Ci sto lavorando
Le cose non stavano esattamente così. O meglio c'è del vero, ma bastava eliminare un break. Non mi dilungo perchè tanto sarebbe
complicato star qui a spiegare.
Ora dovrebbe (condizionale ) essere esente da bug. Sulla stringa "aba" prima avevo il bug, ora non più.
Sto aspettando che riparta il link che vi ho postato per fare più prove con più automi diversi per scovare nuovi eventuali bug.
Per la matrice sparsa per il momento mi accontento. Volendo si potrebbe usare una tabella di char per limitare la memoria.
Ovvio che con i char si può arrivare ad un massimo di nodi: 256 o 128, ora dovrei fare 2 calcoli.
Stavo anche implementando un tool per fare una tabella in automatico. Ma come l'avevo scritto complicava un po'...non mi piaceva.
Ci riproverò.
Sarebbe bello anche studiare (e magari implementare) come passare da DFA a NFA e viceversa...con calma.
Ecco la versione non buggata (spero):

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define XOR ^

int main(void)
{
	const short int array[4][3][5]=	
	{
	{ {0,-1,-1,-1,-1}, 	 {1,3,-1,-1,-1},     {1,3,-1,-1,-1}},
	{  {3,-1,-1,-1,-1},  {-1,-1,-1,-1,-1},   {-1,-1,-1,-1,-1} },
	{  {-1,-1,-1,-1,-1}, {2,1,-1,-1,-1},     {-1,-1,-1,-1,-1} },
	{ {3,1,-1,-1,-1},     {1,-1,-1,-1,-1},   {1,-1,-1,-1,-1}}
						  			};


	
	char s[]="aba";
	int stack[2][4]={ {0},{0} };
	int cont[2][1]={ {0},{0} };
	int i=0;
	int doppi[4]={-1,-1,-1,-1};
	int k=0;
	int event,j,x,w;
	int a=0;
	int b=1;
	int len=strlen(s);
	
	if (s[0]=='a')			event=0;
	else if (s[0]=='b')		event=1;   
	else if (s[0]=='c')		event=2;
	else
	{
		printf ("[%c] carattere non valido",s[0]);
		return 0;
	}

// precaricamento stack primo "giro"
	printf ("---[%c]---\n",s[0]);
	while (array[0][event][i]!=-1)
	{
		stack[a][cont[a][0]]=array[0][event][i];
		printf ("stack %d\n", stack[a][cont[a][0]] );//getchar();
		cont[a][0]++;
		i++;
	}
	i=0;
	
//***********************************************
// scansiono la stringa
//***********************************************
					
	for (j=1; j<len; j++) 
	{
    	
		if  		(s[j]=='a') event = 0;
		else if 	(s[j]=='b') event = 1;
		else if 	(s[j]=='c') event = 2;
		else
		{
			printf ("[%c] carattere non valido",s[j]);
			exit (0);
		}

		printf ("\n---[%c]----------------\n",s[j]);
		
		

		while (cont[a][0]>0) // finche stack maggiore di 0
		{
			while (array [stack[a][k]] [event] [i]!=-1) // finchè nodo ha collegamenti validi
			{
				if  (doppi [array [stack[a][k]] [event][i]  ]==-1) // se link non è doppio
				{
					stack[b][cont[b][0]]=array[ stack[a][k] ][event][i];
					printf ("stack %d pos Char [%c %d]\n", stack[b][cont[b][0]],s[j],j );
					doppi [stack[b][cont[b][0]]]=1;
					++cont[b][0];
					i++;
				}
				else 
					i++;
			}
				
			k++;i=0; 
			cont[a][0]--;
		}
		

		puts("*******esco**********");
		k=0;
		a=a XOR 1;b=b XOR 1;  // INVERTO GLI STACK
		if (cont[a][0]==0 ) 
		{
			printf (" uscita prematura in %c pos[%d]\n",s[j],j);
			return 0;
		}
		for (w=0; w<4; w++) // reset array doppioni
			doppi[w]=-1;
	}
		
	puts ("\n\n-----STATO FINALE-----");
	for (x=0; x<cont[a][0]; x++)
		printf ("[%d] ", stack[a][x]);
	puts("\n--------------");
	return 0;
					    
}
 
Edit

poi promesso che non vi scoccio più :D :D :D
Questo è il generatore "automatico" per la matrice di adiacenze. Credo sia comodo ed intuitivo.
l'ho fatto in un file a parte, ma facilmente integrabile nel programma, oppure come modulo esterno.
Non ho previsto controlli di input, non avevo voglia di farli... :shy:

Codice: Seleziona tutto

// gila75 nov_2021
// compila in automatico la matrice di adiacenze
// alfabeto si inserisce come stringa es: "abcd"
// in nodi si immettono con la virogola es: 1,2,0,5 ecc...
// se un nodo x con un evento y non si collega a nulla
// si preme semplicemente INVIO
//ATTENZIONE: non sono previsti controlli sugli input!!



#include <stdlib.h>
#include <stdio.h>
#include <string.h> 
#include <ctype.h>
#define NODI 4
#define EV 3
#define EV3D NODI+1

void init_array (int array[NODI][EV][EV3D]);
int ins_eventi (char eventi[]);
void input (char str[]);
void compila_tab (int array[NODI][EV][EV3D],char eventi[],int len_eventi);
int scansiona_str(char buff[],int nodi_arrivo[]);
void stampa (int array[NODI][EV][EV3D]);
//**********************************************************

void stampa(int array[NODI][EV][EV3D])
{
	int x,y,z;
	for (x=0; x<NODI; x++)
	{
		for (y=0; y<EV; y++)
		{
			for (z=0; z<EV3D; z++)
				printf("%d ", array[x][y][z]);
			puts("");
			
		}
		puts("");
	}
}
//**********************************************************

int scansiona_str(char buff[],int nodi_arrivo[])
{
	char *token;
	const char s[2] = ",";
	int i=0;
	token = strtok(buff, s);

	while( token != NULL ) 
	{
		nodi_arrivo[i]=atoi(token);i++;
		token = strtok(NULL, s);
	}
	return i;
}


//**********************************************************
void input (char str[])
{
    int len_str;
    len_str=strlen(str);
    str[len_str-1]='\0';
	//printf ("len %d\b", strlen(str));
}


//**********************************************************
void compila_tab (int array[NODI][EV][EV3D],char eventi[],int len_eventi)
{
	int i,j,x,res;
	int w=0;
	int nodi_arrivo[NODI];
	char buff[30];
	puts("");
	puts("*************************************************************************");
	printf(" INSERISCI NODI DI ARRIVO CON VIRGOLA:0,3,1..ecc\n");
	printf(" PER UN NODO x CON EVENTO y CHE NON SI COLLEGA A NULLA PREMI INVIO\n");
	puts("*************************************************************************");
	puts("");
	
	for (i=0; i<NODI; i++)
	{
		for (j=0; j<len_eventi; j++)
		{		
			printf ("INSERISCI DA NODO [%d] CON EVENTO [%c] A CHE NODO GIUNGO: ",i,eventi[j]);
			fgets(buff,30,stdin);
			input(buff);
			if ( (strlen(buff)!=0))
			{
				
				res=scansiona_str(buff,nodi_arrivo);
				for (x=0; x<res; x++)
				{
					array[i][j] [w]=nodi_arrivo[x];
					w++;
				}
			}
			w=0;
		}
	}
	
}
//**********************************************************
	


//**********************************************************
int ins_eventi (char eventi[])
{
	int len;
	printf ("inserisci eventi come una stringa es:abcd--> ");
	fgets(eventi,30,stdin);
	input(eventi);
	len=strlen(eventi);
	return len;
}
	

//**********************************************************
void init_array (int array[NODI][EV][EV3D])
{
	int x,y,z;
	for (x=0; x<NODI; x++)
	{
		for (y=0; y<EV; y++)
		{
			for (z=0; z<EV3D; z++)
				array[x][y][z]=-1;
		}
	}

	for (x=0; x<NODI; x++)
	{
		for (y=0; y<EV; y++)
		{
			for (z=0; z<EV3D; z++)
				printf("%d ", array[x][y][z]);
			puts("");
			
		}
		puts("");
	}
	
}
//**********************************************************
int main(void)
{
	int array[NODI][EV][EV3D];
	char eventi[30];
	int len_eventi;
	init_array(array);
	len_eventi=ins_eventi(eventi);
	compila_tab(array,eventi,len_eventi);
	stampa(array);
	return 0;
}
	
OUTPUT:

Codice: Seleziona tutto

gila@gila-pc:~/Scrivania$ ./xx
inserisci eventi come una stringa es:abcd--> abc

*************************************************************************
 INSERISCI NODI DI ARRIVO CON VIRGOLA:0,3,1..ecc
 PER UN NODO x CON EVENTO y CHE NON SI COLLEGA A NULLA PREMI INVIO
*************************************************************************

INSERISCI DA NODO [0] CON EVENTO [a] A CHE NODO GIUNGO: 0
INSERISCI DA NODO [0] CON EVENTO [b] A CHE NODO GIUNGO: 1,3
INSERISCI DA NODO [0] CON EVENTO [c] A CHE NODO GIUNGO: 1,3
INSERISCI DA NODO [1] CON EVENTO [a] A CHE NODO GIUNGO: 3
INSERISCI DA NODO [1] CON EVENTO [b] A CHE NODO GIUNGO: 
INSERISCI DA NODO [1] CON EVENTO [c] A CHE NODO GIUNGO: 
INSERISCI DA NODO [2] CON EVENTO [a] A CHE NODO GIUNGO: 
INSERISCI DA NODO [2] CON EVENTO [b] A CHE NODO GIUNGO: 2,1
INSERISCI DA NODO [2] CON EVENTO [c] A CHE NODO GIUNGO: 
INSERISCI DA NODO [3] CON EVENTO [a] A CHE NODO GIUNGO: 3,1
INSERISCI DA NODO [3] CON EVENTO [b] A CHE NODO GIUNGO: 1
INSERISCI DA NODO [3] CON EVENTO [c] A CHE NODO GIUNGO: 1

0 -1 -1 -1 -1 
1 3 -1 -1 -1 
1 3 -1 -1 -1 

3 -1 -1 -1 -1 
-1 -1 -1 -1 -1 
-1 -1 -1 -1 -1 

-1 -1 -1 -1 -1 
2 1 -1 -1 -1 
-1 -1 -1 -1 -1 

3 1 -1 -1 -1 
1 -1 -1 -1 -1 
1 -1 -1 -1 -1 

gila@gila-pc:~/Scrivania$ 
Non voglio più annoiarvi...ho scritto fin troppo. Spero che risulti utile a qualcuno questo mio "piccolo studio" su gli NFA
A dire il vero ci sarebbe il mondo ancora da sapere sui grafi...ma pazienza.
P.S. in python con tanto d'interfaccia grafica verrebbe fuori una cosa carina...avanti Claudio e Nuzzo ;)
Scrivi risposta

Ritorna a “Programmazione”

Chi c’è in linea

Visualizzano questa sezione: 0 utenti iscritti e 10 ospiti