Forum Ubuntu-it

La discussione della notazione polacca inversa ( QUI) è sfociata
negli automi a stati finiti.
Ritengo opportuno proseguire qui.
Posto un esempio significativo di @Claudio_f

Codice: Seleziona tutto

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

e relativo grafico

Ora:il grafico è chiaro, ma vorrei capire anche carta e penna come si genera questo:

Codice: Seleziona tutto

char ttable[9][5] = { {3, 2, 1, 8, 8},
                          {3, 2, 8, 8, 8},
                          {4, 8, 8, 8, 8},
                          {3, 4, 8, 5, 8},
                          {4, 8, 8, 5, 8},
                          {7, 8, 6, 8, 8},
                          {7, 8, 8, 8, 8},
                          {7, 8, 8, 8, 8},
                          {8, 8, 8, 8, 8} };

la prima riga( 3, 2, 1, 8, 8 ) è intuitiva, ma poi mica tanto.

a me sembra solo una tabella di cammini validi, ad ogni lettera controlla in che posizione del grafo si trova e quando esce dal ciclo ritorna 1 solo se si è fermati in un posto giusto.

Piu che altro ho risposto solo x iscrizione.

L'automa in questione, appartenente ad una categoria più ampia di FSM, ed avente la sola funzione di riconoscitore, è implementabile tramite una semplice tabella delle transizioni perché:

1) Non compie operazioni negli stati o nelle transizioni (la sola cosa che fa è cambiare stato in risposta ad un evento).
2) L'uscita è data direttamente dallo stato (macchina di Moore)

La tabella delle transizioni comunque non è facilmente leggibile (cioè senza il diagramma non ci si capisce nulla).

La prima cosa da fare è stata associare un simbolo/evento ad un numero da usare come indice di colonna:

Codice: Seleziona tutto

cifre         -> 0
punto         -> 1
segno         -> 2
esponenziale  -> 3
altri simboli -> 4

La seconda scrivere un array per ogni stato seguendo il diagramma:
Nello stato iniziale 0 devo transitare al 3 se arriva un numero (evento 0), al 2 se arriva un punto (evento 1), all' 1 se arriva un segno (evento 2), e all'8 (errore) in tutti gli altri casi. In pratica lo stato iniziale "riconosce" che l'inizio corretto di un "valore" può essere solo un segno, una cifra o un punto.
Al giro successivo il nuovo stato fa la stessa cosa. Supponiamo di aver rilevato un segno, siamo quindi nello stato 1, dobbiamo di nuovo decidere quale sarà il prossimo stato per ogni evento, se arriva un numero (evento 0) passiamo in 3, se arriva un punto (evento 1) passiamo in 2, qualsiasi altra cosa è un errore. Lo stato 1 "riconosce" che dopo il segno iniziale può esserci solo una cifra o un punto. Stesso discorso per tutti gli altri stati. Lo stato di errore 8 transita sempre a se stesso per qualsiasi evento, una volta che è stato rilevato un errore qualsiasi altro simbolo non è più importante.

Una stringa è riconosciuta valida se l'automa di ferma negli stati 3 4 o 7, che "leggono" rispettivamente le cifre prima del punto (come in -15), dopo il punto (come in 3.14 o .16) e quelle della parte esponenziale (come in 2E-127), se si ferma in qualche posizione intermedia significa che il valore non è scritto completamente (come 12E o +.), se invece è in errore significa che:
1) è arrivato un simbolo non permesso (16f4 +8.9L4)
2) è arrivato un simbolo permesso ma non nel momento giusto (ad esempio 12.4. ++6 ..)

Una forma più leggibile di automa (che potrebbe anche effettuare operazioni) è invece implementabile tramite uno switch, dove i vari case gestiscono gli stati all'interno dei quali si possono riconoscere gli "eventi" tramite if. Ad esempio l'automa in questione si poteva scrivere nella seguente forma estesa e funzionava nello stesso modo:

Codice: Seleziona tutto

    int stat = 0;
    while(*s) {
        char c = *s++;
        switch (stat) {
            case 0:  // attesa primo carattere
                if (c>='0' && c<='9')      stat = 3;
                else if (c=='.')           stat = 2;
                else if (c=='+' || c=='-') stat = 1;
                else                       stat = 8;
                break;    

            case 1:  // trovato segno iniziale
                if (c>='0' && c<='9')      stat = 3;
                else if (c=='.')           stat = 2;
                else                       stat = 8;
                break;    


          ecc ecc ecc


            case 8:  // errore
                break;
        }
    }

Realizzare un automa con liste collegate? Si, è possibile, più che altro sarebbero nodi interconnessi l'uno all'altro con diversi puntatori ciascuno, basta che vi sia sempre la possibilità di stati e transizioni, e di un percorso sensato tra gli stati realizzato seguendo i puntatori. Probabilmente però si avrebbe solo un aggravio sintattico e nessun beneficio.

In linguaggi ad oggetti come Python un automa si può implementare anche tramite state pattern, in assembly tramite computed goto, ma il principio rimane sempre quello della logica scomposta in tanti piccoli pezzetti (stati) che rappresentano la conoscenza dell'automa in un certo momento, degli eventi che causano le transizioni, e della chiamata ciclica, che nel caso in questione è banalmente il while che itera sulla stringa, ma in un sistema di controllo potrebbe essere il mainloop del programma (in questo ultimo caso si possono eseguire innumerevoli automi contemporaneamente in multitasking cooperativo, soluzione che ho dovuto applicare in tutti i programmi per micro di una qualche utilità pratica (come l'orologio DCF77 fondo pagina).

Molto chiaro @Claudio, grazie.
Una domanda: tu nel grafico hai associato il 3 al numero, 1 a +|- ecc... ma è arbitrario giusto?
Sei stato tu che hai pensato così.
L'importante è l'abbinamento numero grafico--->evento.
Nel senso il 3 corrisponde all'evento 0 quindi fintanto esiste la possibiltà (un numero) il 3 nella'array va in posizione 0,
cioè nella posizione dell'evento corrispondente, giusto?
Il punto per esempio è l'evento 1 corrispondente al 2, e infatti lo trovo in posizione 1

Codice: Seleziona tutto

char ttable[9][5] = { {3, 2, 1, 8, 8},
                          {3, 2, 8, 8, 8},
                          {4, 8, 8, 8, 8},
                          {3, 4, 8, 5, 8},
                          {4, 8, 8, 5, 8},
                          {7, 8, 6, 8, 8},
                          {7, 8, 8, 8, 8},
                          {7, 8, 8, 8, 8},
                          {8, 8, 8, 8, 8} };

è corretto il ragionamento?
Si potrebbe allora fare qualsiasi tipo di automa, dal più semplice al più complesso:
stringa che abbia una sottostringa abc, che finisca per vocale, ma che abbia sempre la prima lettera maiuscola ecc..ecc..
No?
Maledetto tempo tiranno!!!!
Se mi confermi ciò che ho detto, appena ho tempo mi metto carta e penna e provo.

Le associazioni sono del tutto arbitrarie. Nello stato 4 (quinta riga) specifico che l'evento 3 (quarta colonna) causa una transizione allo stato 5. Questo crea la transizione da RD2 a EXP in presenza di una 'e' o di una 'E' . Se invece è presente un numero (evento 0, prima colonna) lo stato seguente è sempre il 4 (arco in alto che si richiude sullo stesso stato).

Gli automi si possono sicuramente ingrandire, ma all'aumentare della complessità del problema il numero degli stati può diventare molto grande (ogni tecnica va applicata solo quando permette reali semplificazioni).

Claudio_F [url=http://forum.ubuntu-it.org/viewtopic.php?p=4842277#p4842277][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Gli automi si possono sicuramente ingrandire, ma all'aumentare della complessità del problema il numero degli stati può diventare molto grande (ogni tecnica va applicata solo quando permette reali semplificazioni).

Si tratta della famigerata esplosione combinatoria, che limita il numero degli stati trattabili manualmente e computazionalmente in qualunque genere di "macchina" logica (Mealy, Moore, ma anche reti di Petri e altri automi utilizzati sia per il software che per l'hardware).

Usando metodi simbolici indiretti piuttosto avanzati e strutture algebriche derivate dai famosi BDD (Binary Decision Diagrams) ai quali recentemente anche il venerabile Knuth ha finalmente dedicato un fascicolo del TAoCP, siamo da anni in grado di gestire in verifica esaustiva sistemi con un numero complessivo di stati superiore a 1E21, con picchi di 1E24 e oltre: ovvero un impressionante 1.000.000.000.000.000.000.000.000, un milione di miliardi di miliardi di stati.
Ecco a cosa servono, anche, i metodi formali... ed ecco uno dei pochi numeri naturali d'impiego pratico che risulti superiore al debito pubblico della serva Italia, di dolore ostello, nave sanza nocchiere in gran tempesta, non donna di province, ma bordello, come diceva padre Dante.

sto cercando d'implementare un'automa che se trova ab consecutive nella stringa mi restituisca 0
aba=0
xbc=1

Ma sto incontrando difficoltà. Ho capito un po' di cose ma mi sa che disegno male il grafico

Forse pretendo un po' troppo...dovrei studiare per bene gli alberi, grafi ecc...

Qualcosa come:

Immagine

provo a implementare...aspetta eh!! non mettere la soluzione, voglio capire bene.
Lo schema nell'array l'ho capito (almeno credo) ma mi confondo!!!!
Grazie intanto

Sto cercando d'implementare un esempio più semplice ma ancora non ho chiare delle cose.
Sospetto di disegnare male il grafico.
Per esempio @Claudio: nel tuo primo esempio hai tre possibilità:
numero evento 0 (rd1)
+|- sig
. point

se tutto è ok si arriva a rd3 (numero) altrimenti si prosegue per esempio se arriva un punto si può andare solo in rd4.
Io pensavo ci si potesse ricollegare a rd3 da point 2 con l'evento numero.
Evidentemente mi mancano le basi dei grafi.
Appena prendo la mano con inkscape disegno i grafici anche io, l'ho scaricato, ma non l'ho mai usato.
Adesso sto cercando di fare una cosa più semplice:
entra una stringa (a-z) nella stringa ci possono essere . | * ma non consecutivi e sempre seguiti da una lettera.
Non mi funziona in alcuni casi

ma più che altro mi piacerebbe chiarire la cosa sopra:
[quote][/quote]

gila75 ha scritto:se tutto è ok si arriva a rd3 (numero) altrimenti si prosegue per esempio se arriva un punto si può andare solo in rd4. Io pensavo ci si potesse ricollegare a rd3 da point 2 con l'evento numero.

Non è chiaro, diciamo che si intuisce ma o usi sempre i numeri degli stati o sempre i nomi, così non so esattamente a quali stati ti riferisci. Il grafo percorre pari pari le situazioni che si possono presentare davanti. Un valore è valido se ci si ferma in uno qualsiasi degli stati finali (doppio cerchio).

entra una stringa (a-z) nella stringa ci possono essere . | * ma non consecutivi e sempre seguiti da una lettera.

Dovrebbe bastare:

Immagine

La logica è molto discorsiva: se mi arriva una lettera ok sto in zero, se mi arriva qualcosa che non è ne lettera ne simbolo valido vado in 2 (errore), se arriva un simbolo valido vado in 1 (trovato simbolo) dopo di che mi aspetto una lettera (e torno in zero) altrimenti è sicuramente un errore.

Grazie Claudio
Ti posto il mio programma che non va in alcuni casi:

Codice: Seleziona tutto

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

Appena riesco ti posto il grafico...magari riesci a risalire.
Credo di avere le idee confuse a livello di teoria.

Gila se ti interessa ho degli appunti condivisi su google drive che trattano queste cose mi dovresti mandare il tuo indirizzo gmail se c'è l'hai così ti condivido il link. Ora non ho tempo di fare l'upload del PDF. Mi puoi contattare in pvt

Ecco il disegno
fatto alla buona

Cosa cavolo sbaglio???

EDIT riflettendo fa la cosa giusta:
abc =1
ab.c=1
ab.c*1=0
è sbagliato il grafico

ce l'ho fatta Claudio:

Codice: Seleziona tutto

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

ho implementato il tuo diagramma.
Quello che intendevo dire è che nel primo esempio, quello della notazione polacca se la scrittura è corretta ti congiungi a
RD1 che è un'uscita.
però se sei a POINT2 vai a rd4 che è un'altra uscita.
Credevo che si potesse da POINT2 andare a RD1 che è identico a RD4 ci accedo con lo stesso evento e sono entrambi uscite.
Forse mi sfuggono regole base dei grafi...e qui sarebbe un'altro discorso.
Spero di essermi spiegato, perchè tutt'ora è la cosa che ho capito di meno

EDIT: mi sono permesso di fare piccole modifiche @Claudio:
così dovrebbe uscire senza analizzare tutta la stringa al costo di un if

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
//--------------------------------------------------------------------
int isvalue(char* s)
{
    char ttable[3][3] = { {0, 1, 2}, 
                          {0, 2, 2},
                          {2, 2, 2}};
                         
                          
                               
                           
    int event;
    int stat = 0;
    int err=0;
    while(*s!='\0')
    {
        
        if      ( *s>='a' && *s<='z')           event = 0;
        else if (*s=='.' || *s=='*')            event = 1;
        else                                    event = 2;
        stat = ttable[stat][event];   
       
        if (stat==2)
        {   
            printf ("errore in pos s[%d] %c\n",err,*s);
            return 0;
        }
        s++;
        err=err+1;
    }       
    
    return stat==0;
}
//--------------------------------------------------------------------
int  main(void)
{
    char st[128] = "cas*a9l";
    printf("%d\n", isvalue(st));
    
    return 0;
}

c'è un piccolo bug nella rilevazione dell'errore...provvederò
EDIT: corretto il bug

gila75 ha scritto: Quello che intendevo dire è che nel primo esempio, quello della notazione polacca se la scrittura è corretta ti congiungi a
RD1 che è un'uscita.
però se sei a POINT2 vai a rd4 che è un'altra uscita.
Credevo che si potesse da POINT2 andare a RD1 che è identico a RD4 ci accedo con lo stesso evento e sono entrambi uscite.

Appunto, non c'è RD4

probabilmente volevi dire: "se la scrittura è corretta ti congiungi a RD1 (stato 3) che è un'uscita. però se sei a POINT (stato 2) vai a RD2 (stato 4) che è un'altra uscita. Credevo che si potesse da POINT (stato 2) andare a RD1 (stato 3) che è identico a RD2 (stato 4) ci accedo con lo stesso evento e sono entrambi uscite."

Riporto dalla prima risposta:
"Una stringa è riconosciuta valida se l'automa di ferma negli stati 3 4 o 7, che "leggono" rispettivamente le cifre prima del punto (come in -15), dopo il punto (come in 3.14 o .16) e quelle della parte esponenziale (come in 2E-127)"

Il fatto è che ci sono molte scritture corrette, ma il punto deve apparire una volta sola. POINT (stato 2) significa "trovato un punto iniziale" senza cifre prima, mentre RD1 (stato 3) significa "trovate cifre iniziali e un eventuale punto verrà dopo", ma le cifre dopo il punto vanno "lette" in uno stato diverso che significa "trovate cifre dopo il punto, non potranno esserci altri punti", e questa è la funzione di RD2 (stato 4).

Stesso discorso per RD3 (stato 7), che significa: "trovate cifre dopo simbolo esponenziale, non possono esserci altri simboli oltre a cifre".

Ricordo che in questo diagramma lo stato di errore non è rappresentato e vi si può arrivare da qualsiasi stato se arriva un simbolo non permesso, oppure se arriva un simbolo permesso ma non nel momento giusto (ad esempio un segno è ammesso solo all'inizio della stringa oppure immediatamente dopo il simbolo esponenziale).

però se sei a POINT2 vai a rd4 che è un'altra uscita.
Credevo che si potesse da POINT2 andare a RD1 che è identico a RD4 ci accedo con lo stesso evento e sono entrambi uscite.

intendevo rd2!!!!

ma le cifre dopo il punto vanno "lette" in uno stato diverso che significa "trovate cifre dopo il punto, non potranno esserci altri punti", e questa è la funzione di RD2 (stato 4).

Ecco, grazie. Questo intendevo

Ma gli automi a stati finiti sono "parte" dei grafi degli alberi, di cosa?
Quale è la teoria?
@Claudio: sarebbe bello implementare un compilatore automatico che riempie da solo l'array.
A mano, è molto facile confondersi.
Magari provo, prima però devo fare altri esempi per capire bene.
Si potrebbe fare un input chiedendo il numero es rd1,rd0 ecc... evento e numero collegato...qualcosa del genere.
No? è una brutta idea?

Credo che grafi/alberi abbiano più a che fare con le strutture dati o comunque rappresentazioni.
Gli automi di questo thread sono un sottoinsieme delle macchine a stati (AFS, FSM), che possono essere realizzate tanto via software che in hardware (in particolare sono da cercare macchine di Mealy e Moore, in generale qualsiasi rete logica sincrona le cui uscite e il nuovo stato dipendono dagli ingressi e dallo stato precedente è una macchina a stati... una CPU è una grossa macchina a stati fatta per interpretare/eseguire istruzioni in codice macchina).

Claudio_F [url=http://forum.ubuntu-it.org/viewtopic.php?p=4844551#p4844551][img]http://forum.ubuntu-it.org/images/icons/icona-cita.gif[/img][/url] ha scritto:Credo che grafi/alberi abbiano più a che fare con le strutture dati o comunque rappresentazioni.
Gli automi di questo thread sono un sottoinsieme delle macchine a stati (AFS, FSM), che possono essere realizzate tanto via software che in hardware (in particolare sono da cercare macchine di Mealy e Moore, in generale qualsiasi rete logica sincrona le cui uscite e il nuovo stato dipendono dagli ingressi e dallo stato precedente è una macchina a stati... una CPU è una grossa macchina a stati fatta per interpretare/eseguire istruzioni in codice macchina).

In realtà esistono strutture dati avanzate ad albero che astraggono ulteriormente le macchine a stati: I BDD (Binary Decision Diagrams) e le loro decine di varianti: ordinate, sincrone, parallele, colorate etc.
Usando tali strutture dati si progettano e verificano indifferentemente chip ASIC con elevatissimo numero di gates e software di controllo in tempo reale: i migliori CAD EDA ne fanno ampissimo uso, palese e interno.

Tuttavia, si tratta di un argomento non banale da affrontare, mentre gli automi di base sono molto ben trattati in centinaia di testi anche altamente semplificati, vista la loro necessarietà sia dal punto di vista software che delle reti logiche.

Forum Ubuntu-it

[C] Automi a stati finiti

[C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti

Re: [C] Automi a stati finiti