[C] Automi a stati finiti

[M_A_W_ 1968]

Materiale sugli automi a stati finiti? Intendo libri,non dispensine ridicole. Se ne avete da consigliare fatemi sapere e vi sarò mooolto grato

Comincia da questo, e poi leggi l'articolo su QP (già linkato recentemente), il sito referenzia anche un manuale di estrema importanza per FSM e dintorni con applicazioni in C embedded. Il tutto senza dimenticare di dare un'occhiata anche a Libero.

[ubuntumate]

Materiale sugli automi a stati finiti? Intendo libri,non dispensine ridicole. Se ne avete da consigliare fatemi sapere e vi sarò mooolto grato

Comincia da questo, e poi leggi l'articolo su QP (già linkato recentemente), il sito referenzia anche un manuale di estrema importanza per FSM e dintorni con applicazioni in C embedded. Il tutto senza dimenticare di dare un'occhiata anche a Libero.

Ottimo come sempre @MAW, mi do da fare.

[gila75]

penso di aver risolto anche io.
La mia soluzione forse è più macchinosa della tua @Claudio.
questi sono gli output:

Codice: Seleziona tutto

input esperssione 12
ris= 1
input esperssione 12.3
ris= 1
input esperssione 12.301
ris= 1
input esperssione 12.000
ris= 0
input esperssione 12.00102
ris= 1
input esperssione 0.3
ris= 1
input esperssione 0.330
ris= 0
input esperssione 0.3301
ris= 1
input esperssione 0012
ris= 0
input esperssione 0
ris= 1
input esperssione 00
ris= 0
input esperssione 00.12
ris= 0
input esperssione 12.3330
ris= 0
input esperssione 0.
ris= 0
input esperssione 0.002
ris= 1
input esperssione 00.2
ris= 0
input esperssione 00.21
ris= 0
input esperssione 00.20
ris= 0
input esperssione 0.20
ris= 0
input esperssione 0.2
ris= 1

e in fondo c' è il grafico.
cosa ne pensi?
hai voglia di dargli un'occhiata? O anche altri.

per comporre la tabella ho usato il programma che avevo scritto.
Pensavo fosse inutile, invece è comodissimo:

Codice: Seleziona tutto

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

//-------------------------------------------------------------

void compila(char table[R][C]);
int isvalue(char s[] ,char table[R][C]);
void input (char str[]);


void input (char str[])
{
    int len_str;
    len_str=strlen(str);
    str[len_str-1]='\0';
    
}



void compila(char table[R][C])
{
    int nodi,row,col,event_err,i,nodo,evento,num_eventi;
    char buff[10];

    printf ("immetti numero nodi (0 to x) ");
    fgets(buff,10,stdin);
    input(buff);
    nodi=atoi(buff);
    nodi++;
    puts("");

    printf ("immetti numero eventi (err escluso) " );
    fgets(buff,10,stdin);
    input(buff);
    num_eventi=atoi(buff);
    num_eventi++;
    event_err=nodi;
    
     //------------------------------------------------------
    // inizializza tutta la tavola a errore
    for (row=0; row<=nodi; row++)
    {
        for (col=0; col<num_eventi; col++)
        {
            table[row][col]=event_err;
            printf ("%d ",table[row][col]);
        }
        puts("");
    }
  //------------------------------------------------------
    
    

    for (i=0; i<nodi; i++)
    {
            
        for(;;)
        {
            printf ("collega nodo [%d] a nodo ? (-1 for exit)",i);
            fgets(buff,10,stdin);
            input(buff);
            nodo=atoi(buff);

            if (nodo==-1 )
                break;
            
            printf ("collega nodo [%d] a nodo--->[%d] tramite evento ?", i,nodo);
            fgets(buff,10,stdin);
            input(buff);
            evento=atoi(buff);  
            table[i][evento]=nodo;
                         
        }
        
       printf ("fatti tutti i collegamenti di nodo [%d]\n",i );
       puts("--------------------------------------------------");
    }

    for (row=0; row<=nodi; row++)
    {
        for (col=0; col<num_eventi; col++)
        {
           
            printf ("%d ", table[row][col]);
        }
        puts("");
    }  
}


int isvalue(char* s,char table[R][C])
{
    
    int event;
    int stat = 0;
    while(*s)
    {
        char c = *s++;
        if      (c=='0')            event = 0;
        else if (c=='.' )           event = 1;
        else if (c>='1' && c<='9')  event = 2;


       
       
        else   event = 3;
        stat = table[stat][event];  

        
    }
    return stat==1 || stat==4 || stat==7 || stat==2 || stat==10 || stat==8;
}



//--------------------------------------------------------------------
int  main(void)
{
    char st[128];
    char table[R][C];
    
    compila(table);
    while(1)
    {   printf("input esperssione ");
        fgets(st,128,stdin);
        input(st);
        printf("ris= %d\n", isvalue(st,table));
    }
    return 0;
}

EDIT: i nodi 6 e 7 sono identici a 9 e 10, forse si potrebbero eliminare.
Va bhè, aspetto e vedo se qualcuno di voi gli da un occhio
EDIT_2: si credo proprio che da 5 potrei passare a 9 tramite l'evento 0

[Claudio_F]

Si credo che dal 5 si possa andare al 9 senza passare dal via.

Piuttosto non è gestito il caso ".15"

Comunque la differenza più grossa col mio codice è che il tuo automa riconosce quali stringhe numeriche sono accettabili e quali hanno trailing/leading zero di troppo, mentre il mio crea nuove stringhe depurate e normalizzate (soprattutto i casi attorno al punto .0 3. 0.0), è appunto un automa che "esegue operazioni" ad ogni transizione (non più implementabile in modo semplice con la sola tabella delle transizioni).

[gila75]

Piuttosto non è gestito il caso ".15"

Vero

Comunque la differenza più grossa col mio codice è che il tuo automa riconosce quali stringhe numeriche sono accettabili e quali hanno trailing/leading zero di troppo, mentre il mio crea nuove stringhe depurate e normalizzate (soprattutto i casi attorno al punto .0 3. 0.0), è appunto un automa che "esegue operazioni" ad ogni transizione (non più implementabile in modo semplice con la sola tabella delle transizioni)

Si hai ragione, infatti devo ancora guardare bene il tuo programma.
Più che altro è che facevo fatica a immaginare il grafico. mi sto inventando esempi per prendere la mano.
Grazie Claudio

[gila75]

Stavo anche cercando d'implementare un automa (solo come esercizio) che riconosca valida una stringa solo se la 'a' non è seguita da 'b'.
Al tempo stesso 'a',' 'b' singole sono valide e anche da 'c' a 'z', sia singole che appaiate :
a=1
b=1
ba=1
ab=0
bab=0
czarbbca=1
Voi come scrivereste il grafico?
Io ho risolto, ma ho tanto l'impressione di aver complicato.
Al di la che qui l'automa complica, credo che con degli if e un for si risolva ma....è per esercitarmi.
Appeno ho tempo posto il grafico.
Stavo poi leggendo gli automi non deterministici, ma non ho ben capito: si possono avere più scelte, ma può anche non
produrre risultati. Per ora non colgo ancora vantaggi\svantaggi. Proseguo la lettura.

Grafico e relativo programma:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
//--------------------------------------------------------------------
int isvalue(char* s)
{
    char ttable[8][4] = {{1,3,6,7},
                         {1,7,2,7},
                         {1,3,2,7}, 
                         {4,3,5,7}, 
                         {4,7,3,7}, 
                         {3,3,5,7}, 
                         {1,3,6,7}, 
                         {7,7,7,7}}; 
    int event;
    int stat = 0;
    while(*s)
    {
        char c = *s++;
        if      (c=='a')           event = 0;
        else if (c=='b')           event = 1;
        else if (c>='c' && c<='z') event = 2;
       
        else                       event = 3;
        stat = ttable[stat][event];   
    }
    return stat==1 || stat==2 || stat==3 || stat==4 || stat==5 || stat==6;
}
//--------------------------------------------------------------------
void main(void)
{
    char st[128] = "bab";
    printf("%d\n", isvalue(st));
}

Mi sono accorto che ci sono molti casi da gestire, ma al tempo stesso credo sia un grafico esagerato per una stupidata simile.
Ci sono anche qui nodi che potrebbero essere eliminati....mi accorgo sempre dopo!!!!!
Però (domanda) : usando più nodi e percorsi che fanno la stessa cosa (quindi spreco di memoria) non si ha più leggibilità del grafico
rispetto a meno nodi, ma intrecci infiniti di percorsi?

[gila75]

Si semplifica tutto invece eliminando i nodi superflui...ho detto una bojata

[Claudio_F]

Stavo anche cercando d'implementare un automa (solo come esercizio) che riconosca valida una stringa solo se la 'a' non è seguita da 'b'.
Al tempo stesso 'a',' 'b' singole sono valide e anche da 'c' a 'z', sia singole che appaiate :
a=1
b=1
ba=1
ab=0
bab=0
czarbbca=1
Voi come scrivereste il grafico?

forum.ubuntu-it.org/viewtopic.php?f=33&t=606507#p4843252

[ubuntumate]

@gila75: se ti interessa,puoi usare Dia per disegnare il grafico degli automi (e non solo)

[gila75]

Stavo anche cercando d'implementare un automa (solo come esercizio) che riconosca valida una stringa solo se la 'a' non è seguita da 'b'.
Al tempo stesso 'a',' 'b' singole sono valide e anche da 'c' a 'z', sia singole che appaiate :
a=1
b=1
ba=1
ab=0
bab=0
czarbbca=1
Voi come scrivereste il grafico?

forum.ubuntu-it.org/viewtopic.php?f=33&t=606507#p4843252

Mi pareva non funzionasse, ma forse ho sbagliato io...ricontrollo
però da 'a', puoi accedere a 'b' e non va bene, forse li mi ero confuso.

@gila75: se ti interessa,puoi usare Dia per disegnare il grafico degli automi (e non solo)

Comodo è vero, lo sto provando
Grazie

[Claudio_F]

però da 'a', puoi accedere a 'b' e non va bene, forse li mi ero confuso.

Perché non va bene? Per dire che non deve esserci 'ab' dobbiamo controllare se appare la sequenza 'ab', in quel caso si va in uno stato "scarto" (il 2):

Codice: Seleziona tutto

int noab(char* s) {
    char ttable[3][3] = { {1, 0, 0},
                          {0, 2, 0},
                          {2, 2, 2}  };
    int stat = 0;
    while(*s) {
        stat = ttable[stat][(*s == 'a') ? 0 : (*s == 'b') ? 1 : 2];
        s++;
    }
    return stat != 2;
}

[gila75]

Certo Claudio...devi avere un po' di pazienza... sono cose nuove per me.
Dal grafico accedevi a 'b' dopo di 'a' e li mi ero confuso.
Ma dal programma dici: ritorno 1 in caso diverso da 2.
Forse ci sono.
Ok il tuo è il metodo più elegante...ma alle prime armi, il secondo diagramma che ho postato, fa così schifo?

EDIT: è una vera furbata la tua.. non credo ci avrei mai pensato. Io testo tutti i casi senza ab...tu te ne freghi(giustamente): se c'è 'ab' errore
se entra altro che non si a-z errore, il resto tutto buono.
Porca miseria...che eleganza!!!

[gila75]

Ho introdotto il caso .3 come dicevi Claudio.
Stavo cercando di scrivere anche io il programma che elimina gli zeri non significativi.
Sono riuscito a eliminare il caso 12.0000 che viene stampato 12
0. viene scritto 0
00 diventa 0
Purtroppo il caso 012 mi risulta il più difficile, per non parlare di 0012.000
Temo di aver scritto il grafico in modo errato:
se scrivo 012 vado esempio al nodo 5, ma è un ramo morto:
0 sono in nodo 1 (che è lecito, sarebbe anche un'uscita)
1 vado nel nodo 5 (da qui potrei capire che se sono in 5 ho zeri non significativi a sx)
Ma essendo il nodo 5 un ramo che si chiude in se stesso, gli altri caratteri (il 2 nel nostro caso) sono considerati errori.
Forse il nodo 5 non dovrebbe richiudersi in se stesso.
Non so se sono stato chiaro, devo provare di nuovo.

[gila75]

Ho provato in tutti i modi a scrivere un mio automa per gestire i vari casi, ma alla fine ho dovuto seguire il tuo @Claudio.
Forse io sbagliavo perchè volevo gestire ogni singolo caso in modo diverso:
Tu per esempio 12.30 lo gestisci come 0012.30.
Io invece volevo fare 2 casi diversi e mi sono incasinato.
Ho riscritto una mia versione studiando il tuo codice. Non ho usato una struttura (m'incasino un po' con quelle) e nemmeno un buffer.
Magari (molto facile) è peggiorativa rispetto alla tua.
Col programma che compila la tabella in automatico, mi sono costruito la tavola e poi ho gestito i vari casi.
Mi farebbe piacere se gli dai un 'occhio quando hai voglia.
Ho scritto anche un programmino per estrapolare dalla tabella il grafico, cioè l'inverso del compilatore automatico.
Credo sia comodo anche quello.
Ecco qui il programma degli zeri non significativi. Speriamo non sia buggato

Codice: Seleziona tutto

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


void isvalue(char* st);
void input (char str[]);
void zeri_prima(char *st);
void zeri_dopo (char *st);

void zeri_prima(char *st)
{
    int i=0;
    int len=strlen(st);

    while(1)
    {
        if(st[i]!='0')
            break;
        i++;
    }

    memmove(&st[0],&st[i],(len+1-i)*sizeof(char));

    if(st[0]=='.')
    {
        memmove(&st[1],&st[0],(len+1)*sizeof(char));
        st[0]='0';
    }
  
}

void zeri_dopo (char *st)
{
    int i=0;
    int len=strlen(st);
    while(1)
    {
        if(st[len-i-1]!='0')
            break;
        i++;
    }
    st[len-i]='\0';
    if (st[len-i-1]=='.')
        st[len-i-1]='\0';
}


void input (char str[])
{
    int len_str;
    len_str=strlen(str);
    str[len_str-1]='\0';    
}



void isvalue(char* s)
{

    static char table[R][C]={{1,5,2,6}, 
                             {1,3,2,6},
                             {2,3,2,6},
                             {3,6,4,6}, 
                             {3,6,4,6}, 
                             {3,6,4,6}, 
                             {6,6,6,6}}; 

    int event;
    int pos=0;
    int stat = 0;
    char *back_up=s;
    while(*s)
    {
        char c = *s++;
        if      (c=='0')            event = 0;
        else if (c=='.')            event = 1;
        else if (c>='1' && c<='9')  event = 2;
        else                        event = 3;
        stat = table[stat][event];  
        

        if ( stat==6)
        {
            printf ("error in '%c' posizione[%d]\n",c,pos+1);
            return;
        }

        pos++;
    }

    printf ("stato %d\n",stat);

    if (stat==1)
    {
        strcpy(back_up,"0");
        s=back_up;
        printf ("%s\n",s);
        return;
    }
      
    if (stat==2)
    {
       zeri_prima(back_up);
       s=back_up;
       printf ("%s\n",s);
       return;
    }

    if (stat==3)
    {
       zeri_prima(back_up);
       s=back_up;
       zeri_dopo(s);
       printf ("%s\n", s); 
       return;
    }

    if (stat==4)
    {
        zeri_prima(back_up);
        s=back_up;
        printf ("%s\n", s);
        return;
    }

    if (stat==5)
    {
        puts("error '.' privo di significato");
        return;
    }
}
//--------------------------------------------------------------------

int main(void) {
  char st[128];
  while(1)
    {   printf("input espressione ");
        fgets(st,128,stdin);
        input(st);
        isvalue(st);
    }

return 0;
}

edit

Questo invece è il programma che da tabella (l'array bidimensionale) ci guida a capire il grafico.
Sarebbe bello fare un vero e proprio grafico, magari con gtk, ma io non ne sono capace, non conosco librerie grafiche.
Penso però sia utile anche questo.
Il programma seguente si riferisce al grafico allegato:

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#define R 7
#define C 4
//--------------------------------------------------------------------
 void event_nodi(int *n_eventi,int *n_nodi);
 void stampa (char table[R][C]);

void event_nodi(int *n_eventi,int *n_nodi)
{
      *n_eventi=C-1;
      *n_nodi=R-2;
} 

void stampa (char table[R][C])
{
    int i,j;

    for (i=0; i<R-1; i++)
    {
        for (j=0; j<C; j++)
        {
            if(table[i][j]!=R-1)
                printf ("nodo [%d] collegato a nodo [%d] con ev[%d]\n",
                      i,table[i][j],j);
        }
    }
}



//--------------------------------------------------------------------
int main(void)
{
    char table[R][C] = {{1,5,2,6}, 
                             {1,3,2,6},
                             {2,3,2,6},
                             {3,6,4,6}, 
                             {3,6,4,6}, 
                             {3,6,4,6}, 
                             {6,6,6,6}}; 

    int n_eventi,n_nodi;

    event_nodi(&n_eventi,&n_nodi);
    printf ("nodi totali %d ERRORE:nodo %d\n",n_nodi,n_nodi+1);
    printf ("numero eventi %d\n",n_eventi);
    stampa (table);
  
    return 0;
}   

output:

Codice: Seleziona tutto

gila@ubuntu:~/Scrivania$ ./xx
nodi totali 5 ERRORE:nodo 6
numero eventi 3
nodo [0] collegato a nodo [1] con ev[0]
nodo [0] collegato a nodo [5] con ev[1]
nodo [0] collegato a nodo [2] con ev[2]
nodo [1] collegato a nodo [1] con ev[0]
nodo [1] collegato a nodo [3] con ev[1]
nodo [1] collegato a nodo [2] con ev[2]
nodo [2] collegato a nodo [2] con ev[0]
nodo [2] collegato a nodo [3] con ev[1]
nodo [2] collegato a nodo [2] con ev[2]
nodo [3] collegato a nodo [3] con ev[0]
nodo [3] collegato a nodo [4] con ev[2]
nodo [4] collegato a nodo [3] con ev[0]
nodo [4] collegato a nodo [4] con ev[2]
nodo [5] collegato a nodo [3] con ev[0]
nodo [5] collegato a nodo [4] con ev[2]
gila@ubuntu:~/Scrivania$ 

EDIT_2 : per alcuni casi è buggata!!! Mannaggia!!! Cercherò di correggere
EDIT_3: no, nessun bug funziona

[gila75]

Ho cliccato riporta su per sbaglio...scusatemi

[gila75]

Hai provato @Claudio (o altri) la mia versione ?
Vorrei capire se la struttura (come hai fatto tu) e il buffer sono necessari.
Io non ho usato un buffer supplementare, ma forse il codice si è appesantito.
Mi piacerebbe approfondire, visto che le strutture mi risultano ancora un po' ostiche.
Per ora non ho rilevato bug. Ho aggiunto anche la stampa che indica il primo carattere non valido e la relativa posizione nella stringa.

[gila75]

Ma in pratica il grafico di un'automa è quello che viene definito un grafo orientato?

[spider-net]

Ma in pratica il grafico di un'automa è quello che viene definito un grafo orientato?

Sì.

Comincia da questo, e poi leggi l'articolo su QP (già linkato recentemente), il sito referenzia anche un manuale di estrema importanza per FSM e dintorni con applicazioni in C embedded. Il tutto senza dimenticare di dare un'occhiata anche a Libero.

Vorrei anche aggiungere Introduction to Automata Theory, Languages, and Computation dei mostri sacri Hopcroft e Ullman.

[gila75]

Grazie @spider.
Sto iniziando a studiare alberi e grafi e mi è venuta la domanda.
Ho svariati pdf sugli automi...ma in inglese, e i in più il tempo per lo studio è quello che è...

[M_A_W_ 1968]

Vorrei anche aggiungere Introduction to Automata Theory, Languages, and Computation dei mostri sacri Hopcroft e Ullman.

Ovviamente si sottintende la terza edizione, o al limite la seconda, ambedue con l'aggiunta agli autori del terzo moschettiere Motwani.

L'edizione originale degli anni Settanta, e il suo predecessore del 1969 "Formal Languages and Their Relation to Automata" degli stessi autori, oggi risultano probabilmente illeggibili al laureato quadratico medio italiano ed a quasi tutti i practitioners.

La bibliografia sulla enorme famiglia degli automi a stati finiti (che finisce per includere non solo Mealy e Moore ma una varietà enorme di alternative, incluse le reti di Petri e perfino i BDD) è comunque sterminata e le esposizioni alternano numerosi e diversi punti di vista, da quello process-algebraic a quello (comunissimo) dell'elettronica digitale e degli HDL, fino agli aspetti più propriamente computer-theoretic.

Chi fosse interessato ad approfondimenti non ha che da chiedere, al solito.