Implementare automi non deterministici

di il
4 risposte

Implementare automi non deterministici

Salve a tutti,
dovrei implementare un automa non deterministico che data una stringa di input mi dica se tale stringa giunge in uno stato accettante e di conseguenza viene accettata.
Fin qui sembrava tutto abbastanza realizzabile, se nonché ad un certo punto mi è stato detto di creare l'albero corrispondente in modo che da poter gestire tutti i possibili stati in cui un automa può trovarsi. Il mio dubbio e come costruisco questo albero, ed una volta costruito come faccio a visitarlo? dovrei per caso usare dei pattern?
Vi ringrazio in anticipo per il tempo dedicatomi, potrebbe essermi utile qualunque informazione, anche solo teorica.

Saluti

4 Risposte

  • Re: Implementare automi non deterministici

    giorgetta ha scritto:


    dovrei implementare un automa non deterministico che data una stringa di input mi dica se tale stringa giunge in uno stato accettante e di conseguenza viene accettata.
    Puoi fare un esempio pratico (anche minimale) di stringa e di cosa devi verificare?
  • Re: Implementare automi non deterministici

    Grazie andbin per la risposta,
    ecco un esempio,

    dato l'automa e la stringa w = ab, dovrei, in un primo momento creare l'albero corrispondente e successivamente scandire tale albero per verificare almeno uno dei rami mi porta a soluzione.
    Spero di essere stata abbastanza chiara, se dovessi aver bisogno di ulteriori elementi fammi sapere.
    Grazie
  • Re: Implementare automi non deterministici

    Ciao
    Immagino che l'automa sia stato costruito tramite classi e riferimenti agli oggetti successivi.
    Pertanto, se l'automa fosse stato deterministico ti sarebbe bastato un riferimento allo stato corrente per sapere in quale stato sei, e la scansione sarebbe stata semplice. Il risultato sarebbe stato una lista degli stati attraversati dal riferimento allo stato corrente.

    L'automa pero' e' non deterministico. Non hai quindi un solo stato corrente ma ha un insieme di stati correnti! La cosa e' semplice: utilizzi un array (anzi, un ArrayList) di riferimenti invece che una semplice variabile scalare. Ne risulta che quindi la scansione originera' l'albero che appunto vuoi ottenere.
    Ad ogni passo (i.e. ad ogni nuova lettura di un carattere di ingresso), potrai quindi far cambiare l'automa di stato o creare/rimuovere un nuovo stato.
  • Re: Implementare automi non deterministici

    Ciao sottovento,
    grazie per la tua risposta, per la costruzione dell'automa ho creato tre classi: Stato, Transizione ed Automa. La classe Stato ha come proprietà il numero indicante lo stato ed un arraylist per gestire le epsilon transizioni nonché una mappa per la gestione delle transizioni ordinarie. La particolarità di tali automi risiede nell'avere tra i possibili stati anche quelli di tipo contatore, il cui scopo è contare quante occorrenze di un determinato simbolo, che vanno da un numero minimo ad un numero massimo, ci sono. Una prima implementazione prevedeva l'uso si Set per la gestione delle transizioni, che per la parte delle transizioni ordinarie funzionava correttamente, ma adesso con la costruzione dell'albero mi trovo confusa. Alla fine ho creato una nuova classe Nodo che mi permette di creare, a seguito di una transizione, un nuovo nodo all'interno dell'albero, quindi quando leggo un carattere creo il nuovo nodo con il riferimento al padre; ma il tutto non funziona correttamente poiché quando si incontrano stati di tipo contatore dovrei scorrere l'albero dalla radice fino al nuovo nodo che devo inserire nell'albero e capire se lungo il percorso c'è un nodo uguale, se si devo incrementare di 1 il valore di una variabile dello stato contatore.
    Non so se sono stata chiara, ad ogni modo adesso non riesco a capire come scandire l'albero in contemporanea alla sua creazione.
    Potreste darmi qualche suggerimento?
    Grazie a tutti
Devi accedere o registrarti per scrivere nel forum
4 risposte