Implementare automa a stati finiti DFA

[cerza]

Ciao,
devo implementare un automa a stati finiti in java, non so bene come fare, qualcuno può suggerirmi del codice o appunti? il dubbio è capire come poter implementare l'effettiva transizione per effettuare il passaggio, dato un carattere di input, da uno stato iniziale ad uno stato finale.
Grazie a quanti vorranno darmi una mano.

[Nikopol]

Il modo più semplice che mi viene in mente è rappresentarlo come un insieme di transizioni e un insieme di stati finali.
Gli stati finali li puoi implementare come un HastSet di interi.
Le transizioni, nella forma (q, ch) -> q' dove q, q' sono stati (interi) e ch è il carattere/simbolo che caratterizza la transizione, puoi implementarli con:
- una classe M che rappresenta lo stato di partenza e il simbolo, ovvero (q, ch);
- un HashMap <M, Integer> che associa a ogni M lo stato di arrivo q'.

[cerza]

Grazie Nikopol per la risposta,
quindi dovrei avere una classe che mi rappresenta lo Stato, una per le Transizioni, ma l'effettiva transizione dovrei farla eseguire in un'ulteriore classe automa, giusto? ma il dubbio è legato all'effettiva transizione, come faccio a fargli fare la transizione? dovrei avere una lista di stati ai quali si giungerebbe leggendo un determinato input, dovrei quindi conoscere già in partenza tali stati?
Grazie e buona giornata

[Nikopol]

Una classe M (Move, Mossa o come vuoi) per rappresentare la coppia (statoDiPartenza, carattere). Ogni coppia è unica in un automa e in questo modo potrai usarla come chiave di un HashMap.
Una classe Automa con:
attributi:
- un HashSet di interi che rappresenta gli stati finali
- un HashMap <M, Integer> che rappresenta una transizione (statoDiPartenza, carattere) -> statoDiArrivo
- un variabile intera che rappresenta il numero di stati
metodi(scrivo i nomi in italiano anche se potrebbero risultare un po' strani):
- creaNuovoStato() //incrementa di 1 il numero di stati
- aggiungiTransizione(int q, char ch, int p) //crea una nuova M con (p, ch) e la inserisce nell' HashMap usando la coppia come chiave e p come valore
- aggiungiStatoFinale(int q) //aggiunge q all'insieme degli stati finali
- èUnoStatoValido(int q) // controlla se q è nel range [0, numeroStati)
- èUnoStatoFinale(int q) // controlla se q fa parte dell'insieme degli stati finali

ma il dubbio è legato all'effettiva transizione, come faccio a fargli fare la transizione?

- eseguiTransizione(int q, char ch)// crea una nuova M con (q, ch) e restituisce il valore (stato di arrivo) associato a (q, ch) nell'HashMap delle transizioni. Se (q, ch) non è presente nelle transizioni allora restiruisci -1, lanci un eccezioni o comunque qualcosa che segnali che quella transizione non fa parte dell'automa.

dovrei avere una lista di stati ai quali si giungerebbe leggendo un determinato input

In un DFA la funzione di transizione è una vera e propria funzione, ovvero per ogni coppia (statoDiPartenza, simbolo) esiste uno e un solo stato di arrivo. Se invece esistono più stati di arrivo la "funzione" di transizione `e una relazione e questo significa che non si tratta più di un DFA ma bensì di un NFA.

Se però per input intendi la stringa che il DFA dovrebbe decidere e per transizione intendi l'insieme delle transizioni che devi eseguire per deciderla, allora ti basta fare qualcosa del genere:

public boolean decidi(String s) {
    char ch;
    int statoCorrente = 0;
    int i = 0;
    while (i < s.length() && èUnoStatoValido(statoCorrente)) {
        ch = s.charAt(i++);
        statoCorrente = eseguiTransizione(statoCorrente, ch);
    }
    return èUnoStatoFinale(statoCorrente);
}

[cerza]

Grazie Nilkopol, la tua risposta è stata decisiva!
Grazie ancora

[Nikopol]

Figurati