Posso implementare Transizioni di stato per un DFA in Java usando java.util.Set

Question

Sto implementando un DFA il più vicino possibile alla definizione formale come esercizio di apprendimento (e materiale di blog)

Ho pianificato di utilizzare un java.util.Set in cui un set è coinvolto nella definizione.

La definizione implica una serie di tuple per definire le transizioni di stato legali: (stato, simbolo) - > NextState.

Ho una classe Transition con stato membri, simbolo e nextState. Ho implementato equals () e hashCode () per indicare che due Transizioni sono uguali se corrispondono su stato e simbolo. Ho quindi un java.util.Set di istanze di transizione.

Nel mio algoritmo di elaborazione, ho lo stato corrente quando leggo il simbolo successivo. Ho anticipato di costruire un oggetto Transizione usando questi due per estrarre la Transizione corrispondente dal Set, che mi avrebbe quindi indicato lo stato successivo e posso iterare.

Ma - Non vedo alcun modo di estrarre un membro di un java.util.Set per un ulteriore utilizzo. Posso rimuovere (Object o), ma questo restituisce solo un valore booleano.

Cosa sto sbagliando?

Answer 1

Set probabilmente non è quello che vuoi usare per questo. La mia raccomandazione sarebbe di usare un Elenco & Lt; Transizione & Gt ;, o possibilmente una mappa & Lt; Stato, Lista lt &; Transizione gt &; & Gt ;. Non sono sicuro quale sarebbe meglio senza effettivamente costruirlo e fare qualche benchmarking.

Answer 2

Sembra che la tua sostituzione di equals () e hashCode () sia dubbia, perché la transizione originale corrisponde a quella nell'insieme secondo equals () e tuttavia i due non sono intercambiabili (altrimenti useresti semplicemente il nuovo transizione al posto dell'originale.)

Probabilmente vuoi una classe che è solo una combinazione di stato e simbolo senza altri attributi e usala come chiave in una Mappa. In alternativa puoi usare un Map<State, Map<Symbol, State>>

Answer 3

Sono d'accordo con Matthew Brubaker che Set probabilmente non è ciò di cui hai bisogno. Invece potresti provare enums; vedere il Glossario Java per un esempio.

Answer 4

Non puoi farlo senza avere una raccolta esterna di stati, o persino gli oggetti Transistion? Se la classe di stato è definita come:

public class State
{
    private Map<Symbol, State> transitions = new HashMap<Symbol, State>();

    public State() { /* populate transitions somehow */ }

    public State nextState(Symbol symbol) { return transitions.get(symbol); }
}

Quindi, se hai un riferimento allo stato iniziale, puoi semplicemente spostarti da uno stato all'altro in questo modo:

State initial = getInitialStateSomehow();
State second = initial.nextState(SYMBOL_1);
State third = initial.nextState(SYMBOL_2);  // etc...

Answer 5

Sì, sono un po 'confuso sul perché avrebbe persino bisogno di una collezione.

Per una semplice macchina a stati puoi semplicemente usare numeri interi statici e un'istruzione case per fare la tua macchina a stati in questo modo:

int STATE1 = 1; 
int STATE2 = 2;
int STATE3 = 3;
int STATE4 = 4;

int currentstate = STATE1 ;
int input = nextInput();


while(currentstate != STATE4 ){
   switch(input){
      case STATE1: 
          if(input == 'a') currentstate = STATE2; 
          break;
      case STATE2: 
          if(input == 'b') currentstate = STATE3;
          else currentstate = STATE1;
          break;
      case STATE3: 
          if(input == 'c')  currentstate = STATE4;
          else currentstate = STATE1;
      }
 }

Questa è una macchina a stati di base che cercherà qualsiasi stringa contenente "abc". Potresti facilmente estendere anche quello per cercare un * c o qualunque cosa tu voglia.

E se volessi una macchina a stati dinamici, costruita in fase di esecuzione? Bene, l'ho fatto anche io. Non è troppo difficile. Quello che ho fatto è stato creare una classe di stato con un elenco di transizioni. Ogni transizione ha un puntatore allo stato successivo e i criteri su cui collegarsi.

Ad esempio, STATE1 avrebbe una transizione con i criteri 'a' e un puntatore a qualche oggetto che rappresenta STATE2. Il codice sembrerebbe controllare i criteri (che potrebbe essere un oggetto che accetta un int come parametro e restituisce vero o falso se corrisponde) e se i criteri corrispondessero, sposta il puntatore di stato sullo stato indicato anche dalla transizione.

Il codice potrebbe assomigliare a questo

public void move(int input){
   for(transition t : currentState.transitions){
      if(t.getCriteria().matches(input)){
         currentState = t.getNextState();
         break;
      }
   }
}

Answer 6

Se si desidera solo implementare un motore di abbinamento dei modelli, un modello di progettazione dello stato potrebbe non essere necessario poiché è improbabile che il picchiettio cambi. Come ha sottolineato Chad, l'utilizzo di un switch per codificare la funzione di transizione è del tutto accettabile in questi casi.

Ecco un esempio di un automa di corrispondenza pattern non deterministico che utilizza set:

public boolean validate() {
    Set<Integer> currentStates = new HashSet<Integer>();
    final Set<Integer> acceptingStates = new HashSet<Integer>();

    currentStates.add(0); // Initial state.
    acceptingStates.add(1);
    acceptingStates.add(3);
    acceptingStates.add(6);

    for (int i = 0; i < getInput().length(); i++) {
        char c = getInput().charAt(i);
        Set<Integer> newStates = new HashSet<Integer>();

        for (int state : currentStates) {
            switch (state) {
                case 0:
                    if (c == 'a')
                        newStates.add(1);
                    break;
                case 1:
                    if (c == 'b') {
                        newStates.add(2);
                        newStates.add(4);
                    }
                    break;
                case 2:
                    if (c == 'b')
                        newStates.add(3);
                    break;
                case 3:
                    if (c == 'b')
                        newStates.add(2);
                    break;
                case 4:
                    if (c == 'b')
                        newStates.add(5);
                    break;
                case 5:
                    if (c == 'b')
                        newStates.add(6);
                    break;
                case 6:
                    if (c == 'b')
                        newStates.add(4);
                    break;
            }
        }

        if (newStates.size() == 0)
            return false;
        currentStates = newStates;

        System.out.printf("Character read: %c\n", c);
        System.out.printf("Current states: ");
        printStates(currentStates);
    }

    for (int state : acceptingStates)
        if (currentStates.contains(state))
            return true;
    return false;
}

Questo automa riconosce le parole di input del linguaggio normale descritto dal modello " a (bb * | bbb *) " ;, cioè un & # 8220; a & # 8221; seguito da un multiplo di due o un multiplo di tre molti & # 8220; b & # 8221; s.