我可以使用java.util.Set中

Question

我實現DFA接近實現了DFA態躍遷Java作爲我可以正式定義爲一個學習鍛鍊（和博客材料）

我計劃使用定義中涉及集合的java.util.Set。

該定義涉及到一組元組來定義合法的狀態轉換：（state，symbol） - > nextState。

我有一個Transition成員狀態，符號和nextState類。我已經實現了equals（）和hashCode（）來表示如果它們在狀態和符號上匹配，那麼兩個Transitions是相等的。然後我有一個java.util.Set Transition實例。

在我的處理算法中，當我讀取下一個符號時，我有當前狀態。我期望使用這兩個構建一個Transition對象來從Set中取出匹配的Transition，然後告訴我下一個狀態，並且我可以迭代。

但是 - 我沒有看到任何提取java.util.Set成員的方式以供進一步使用。我可以刪除（Object o），但只是返回布爾值。

我在做什麼錯？

Answer 1

設置可能不是你想要用於這個。我的建議是使用列表< Transition>，或可能使用Map < State，列表< Transition >>。我不確定沒有真正建立它並做一些基準測試，哪個更好。

Answer 2

這聽起來好像你的equals（）和hashCode（）的覆蓋是可疑的，因爲原始轉換匹配equals（）中的集合中的一個，但兩者不可互換（否則你只需使用新的過渡代替原來的）。

你可能想要一個類，它只是狀態和符號的組合，沒有其他屬性，並將它用作Map中的一個鍵。或者你可以使用Map<State, Map<Symbol, State>>

Answer 3

我同意馬修布魯貝克認爲Set可能不是你所需要的。您可能想嘗試使用enums;例如，請參閱Java Glossary。

Answer 4

如果沒有外部狀態的集合，甚至是Transistion對象，你難道不能完成這個嗎？如果State類的定義如下：

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

然後，如果你有到初始狀態的參考，你可以從狀態移動到狀態是這樣的：

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

Answer 5

是的，我是那種對爲什麼甚至需要一個集合感到困惑。

對於一個簡單的狀態機，你可以只使用靜態整數和一個case語句做你的狀態機這樣的：

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

這是一個基本的狀態機，將查找包含「ABC」的任意字符串。你可以很容易地擴展它，尋找ab * c或任何你想要的。

那麼，如果你想要一個運行時建立的動態狀態機呢？好吧，我也是這樣做的。這並不難。我所做的是創建一個帶有轉換列表的狀態類。每個轉換都有一個指向下一個狀態的指針以及鏈接的標準。

因此，例如，STATE1將具有標準「a」和指向表示STATE2的某個對象的指針的轉換。代碼看起來會檢查條件（這可能是一個將int作爲參數的對象，如果匹配則返回true或false），並且如果條件匹配，則會將狀態指針移動到過渡指向的狀態。

的代碼可能看起來像部份

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

Answer 6

如果你只是想實現一個模式匹配引擎，狀態設計模式可能會因爲圖案是不可能改變的是不必要的。正如Chad指出的那樣，在這種情況下，使用switch來編碼轉換函數是完全可以接受的。

下面是一個使用設置的非確定性模式匹配自動機的示例：

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

此自動機識別由圖案"a(bb*|bbb*)描述的正則語言的輸入字」，即，‘一’，接着爲無論多兩個或三個「b」的倍數