Могу ли я реализовать переходы состояний для DFA на Java с помощью java.util.Set

Set, вероятно, не то, что вы хотите использовать для этого. Я бы рекомендовал использовать List <Transition> или, возможно, Map <State, List <Transition >>. Я не уверен, что было бы лучше, не создавая его и не делая некоторых тестов.

Похоже, ваше переопределение equals () и hashCode () сомнительно, потому что исходный переход совпадает с переходом в наборе в соответствии с equals (), и все же эти два не взаимозаменяемы (иначе вы просто использовали бы новый переход вместо оригинала.)

Вероятно, вам понадобится класс, представляющий собой просто комбинацию состояния и символа без других атрибутов, и использовать его в качестве ключа на карте. В качестве альтернативы вы можете использовать Map<State, Map<Symbol, State>>

Я согласен с Мэтью Брубейкером в том, что Set, вероятно, не то, что вам нужно. Вместо этого вы можете попробовать enums; см. Глоссарий Java для примера.

Разве вы не можете этого добиться, не имея некоторого внешнего набора состояний или даже объектов 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...

Да, я немного не понимаю, зачем вообще нужна коллекция.

Для простого конечного автомата вы можете просто использовать статические целые числа и оператор 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, если он совпадает), и если критерии совпадают, он переместит указатель состояния в состояние, на которое также указывает переход.

Код может выглядеть примерно так: ths

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

Если вы просто хотите реализовать механизм сопоставления с шаблоном, шаблон State Design Pattern может быть ненужным, поскольку шаблон вряд ли изменится. Как указал Чад, использование 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 ".