automi a stati finiti

[Killian]

avrei la necessità (in Java) di creare un modello di automa a stati finiti, solo che ho un problema: quale è il modo migliore per rappresentarli?

Premetto che per ora mi serviranno metodi per sapere lo stato iniziale, lo stato corrente e l'elenco degli stati raggiungibili con lo stato corrente "in una mossa".

Non chiedo delle righe di codice, solo sapere come poterli miplementare e se ci sono librerie utili allo scopo.

Grazie.

PS: ho fatto una ricerca sul forum con le parole chiave "automi" "stati" "finiti" ma non ho trovato niente di utile.

[end.is.forever]

Non penso che esistano librerie apposta, io a prima vista realizzerei una classe stato che mantiene in una hasmap indicizzata per l'oggetto di input che porta ad una certa transizione, con valori gli stati a cui ogni transizione porta.

L'automa molto semplicemente avrebbe un campo statico che contiene lo stato iniziale, e gli eventuali metodi a cui passare gli input che richiamano lo stato attuale per sapere uscita e stato futuro.

[^TiGeRShArK^]

nel JADE dei telecom italia labs c'è la possibiltà di creare agenti intelligenti ke abbiano un comportamento di tipo automa a stati finiti...
non so se ti serve....

[Killian]

Originariamente inviato da ^TiGeRShArK^
nel JADE dei telecom italia labs c'è la possibiltà di creare agenti intelligenti ke abbiano un comportamento di tipo automa a stati finiti...
non so se ti serve....

no, non è quello che cerco.


Diciamo che a parte librerie predefinite preferirei non usare altro.

Per ora punto ad una struttura che contenga le transizioni e per ogni transizione una stringa per riconoscerla, lo stato da cui parte e lo stato a cui porta.

[lombardp]

Originariamente inviato da Killian
avrei la necessità (in Java) di creare un modello di automa a stati finiti, solo che ho un problema: quale è il modo migliore per rappresentarli?

Premetto che per ora mi serviranno metodi per sapere lo stato iniziale, lo stato corrente e l'elenco degli stati raggiungibili con lo stato corrente "in una mossa".

Non chiedo delle righe di codice, solo sapere come poterli miplementare e se ci sono librerie utili allo scopo.


Quando la scala di integrazione era bassa, in hardware automi a stati finiti di una certa complessità era realizzati con memorie PROM. In cui l'indirizzo era la combinazione dello stato corrente e degli ingressi all'automa, il dato in uscita alla PROM era lo stato futuro e le uscite dell'automa.

Quindi, tornando al tuo caso: per implementare l'automa ti basta di fatto una tabella opportunamente organizzata. Per esempio se numeri gli stati, lo stato corrente ti indicherà la riga di questa tabella, riga nella quale avrai memorizzato lo stato futuro ed eventuali al tre uscite. Se la variazione dello stato dipende anche da variabili esterne (ingressi), occorre "combinare" lo stato corrente e questi ingressi in modo da identificare una ed una sola riga della tabella. (Combinare si intende numericamente o con IF)

Così è come lo farei io se dovessi divertirmi a realizzarlo...

[Killian]

Originariamente inviato da lombardp
Quindi, tornando al tuo caso: per implementare l'automa ti basta di fatto una tabella opportunamente organizzata. Per esempio se numeri gli stati, lo stato corrente ti indicherà la riga di questa tabella, riga nella quale avrai memorizzato lo stato futuro ed eventuali al tre uscite. Se la variazione dello stato dipende anche da variabili esterne (ingressi), occorre "combinare" lo stato corrente e questi ingressi in modo da identificare una ed una sola riga della tabella. (Combinare si intende numericamente o con IF)

Così è come lo farei io se dovessi divertirmi a realizzarlo...

ho deciso invece di numerare le transizioni, in pratica creo una struttura con 4 attributi, un numero che identifica una transizione in modo univoco, 2 campi per identificare rispettivamente lo stato di partenza e quello di arrivo della transizione e un valore booleano per sapere se lo stato è marcato, poi una variabile a parte che identifica l'ultima transizione effettuata, utile per sapere in che stato mi trovo. Per convenzione la transizione 0 identificherà lo stato iniziale e non avrà alcuno stato 'sorgente'.

Dopotutto a me basta implementare pochi e semplici metodi, un metodo che mi permette di sapere se un certo stato (passato per parametro) è immediatamente raggiungibile con una sola transizione dallo stato corrente, un metodo che mi permette di sapere lo stato iniziale (praticamente un caso particolare del metodo precedente) e un metodo che mi restituisca l'elenco degli stati raggiungibili dalla posizione corrente con una sola transizione.

Probabilmente nella struttura gli stati li rappresenterò con delle stringhe, perchè comunque se li rappresentassi con numeri dovrei tenere in memoria una tabella che mi permetta di associare ad ogni stato un nome non numerico.


Se avete altre opinioni su come rappresentare lo stato sarò felice di ascoltarvi, ma senza scrivere linee di codice, voglio farmelo da solo.

Per i metodi non mi servono aiuti, so già come implementarli se utilizzerò la struttura che ho descritto sopra.

[atidem]

Ti consiglio questa (http://unimod.sourceforge.net/fsm-framework.html) lettura.

[Omni]

io ti consiglio qeusta lettura invece. http://www.dis.uniroma1.it/~terpa/sw/public_html