Kann ich Zustandsübergänge für einen DFA in Java unter Verwendung von java.util.Set implementieren

Question

Ich bin ein DFA-Implementierung so nah wie möglich an die formalen Definition als Lernübung (und Blogging Material)

ich planten einen java.util.Set zur Verwendung in dem ein Satz in der Definition beteiligt ist.

Die Definition beinhaltet eine Menge von Tupeln, die rechtlichen Zustandsübergänge zu definieren. (Staat, Symbol) -> nextstate

Ich habe eine Transition-Klasse mit Mitgliedern Zustand, Symbol und nextstate. Ich habe implementiert equals () und hashCode (), um anzuzeigen, dass zwei Übergänge gleich sind, wenn sie auf Zustand und Symbol entsprechen. Ich habe dann eine java.util.Set von Transition Instanzen haben.

In meinem Verarbeitungsalgorithmus, ich habe den aktuellen Zustand, wenn ich das nächste Symbol zu lesen. Ich erwartet hatte ein Transition-Objekt bauen diese beiden unter Verwendung von dem Set die passenden Übergang zu ziehen, die dann mir den nächsten Zustand sagen würde, und ich kann iterieren.

Aber - ich sehe keinen Weg, um ein Mitglied eines java.util.Set zur weiteren Verwendung zu extrahieren. Ich kann (Object o) entfernen, aber das nur boolean zurück.

Was mache ich falsch?

Answer 1

Set ist wahrscheinlich nicht das, was Sie für diese verwenden möchten. Meine Empfehlung wäre, eine Liste verwenden oder möglicherweise eine Karte >. Ich bin mir nicht sicher, welche ohne tatsächlich zu bauen es besser wäre, und einig Benchmarking zu tun.

Answer 2

Es klingt, als ob Ihr überwiegendes von equals () und hashCode () zweifelhaft ist, weil der ursprüngliche Übergang des einen in dem Satz entspricht nach equals () und doch die beiden sind nicht austauschbar (sonst würden Sie einfach die neue verwenden Übergang anstelle des Originals.)

Sie wollen wahrscheinlich eine Klasse, die nur eine Kombination von Staat und Symbol ohne andere Eigenschaften, und verwenden, die als Schlüssel in einer Karte ist. Alternativ könnten Sie eine Map<State, Map<Symbol, State>> verwenden

Answer 3

ich mit Matthew Brubaker einig, dass Set ist wahrscheinlich nicht das, was Sie brauchen. Vielleicht möchten Sie enums versuchen statt; finden Sie in der Java Glossar für ein Beispiel.

Answer 4

Können Sie dies nicht erreichen, ohne eine externe Sammlung von Zuständen oder sogar die Transistion Objekte? Wenn der Staat Klasse definiert wie:

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); }
}

Wenn Sie dann einen Verweis auf den Ausgangszustand haben, können Sie nur aus dem Zustand bewegen wie folgt angeben:

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

Answer 5

Ja, ich bin ein bisschen verwirrt darüber, warum überhaupt eine Sammlung noch brauchen würde.

Für eine einfache Zustandsmaschine Sie nur statische ganzen Zahlen und einer Case-Anweisung verwenden können, um Zustandsmaschine wie dies zu tun:

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;
      }
 }

Das ist eine Grundzustandsmaschine, die für jede Zeichenfolge mit ‚abc‘ aussehen wird. Sie könnten einfach erweitern zu, dass für ab * c aussehen oder was auch immer Sie wollen.

Was also, wenn Sie eine dynamische Zustandsmaschine wollen, zur Laufzeit gebaut? Nun, ich habe dies auch getan. Es ist nicht zu hart. Was ich tat, ist eine Zustandsklasse mit einer Liste von Übergängen erstellen. Jeder Übergang weist einen Zeiger auf den nächsten Zustand und die Kriterien zur Verknüpfung auf.

So würde zum Beispiel hat STATE1 einen Übergang mit den ‚a‘ Kriterien und einem Zeiger auf ein Objekt, das STATE2 darstellt. Der Code würde die Kriterien aussehen überprüfen (die ein Objekt sein könnten, die einen int als Parameter und gibt wahr oder falsch, wenn sie paßt) und wenn die Kriterien angepasst, wäre es um den Zustand Zeiger auf den Zustand wies auch durch den Übergang zu bewegen.

Der Code könnte so etwas wie ths aussehen

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

Answer 6

Wenn Sie nur eine Pattern-Matching-Engine implementieren mögen, könnte ein Staat, Design, Muster unnötig sein, da das Prasseln unwahrscheinlich ist, zu ändern. Wie Chad ausgeführt hat, eine switch mit der Übergangsfunktion zu kodieren, in solchen Fällen völlig akzeptabel ist.

Hier ist ein Beispiel für einen nichtdeterministische Muster passenden Automaten, die Sätze verwendet:

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;
}

Dieser Automat erkennt Eingangsworte der regulären Sprache durch das Muster "a(bb*|bbb*) beschrieben“, das heißt ein‚a‘, gefolgt von entweder ein Vielfaches von zwei oder mehreren von drei viele‚b‘s.