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

Question

Я реализую DFA как можно ближе к формальному определению в качестве учебного упражнения (и материала для блога).

Я планировал использовать java.util.Set, где в определении участвует набор.

Определение включает в себя набор кортежей для определения законных переходов между состояниями:(состояние,символ) -> nextState.

У меня есть класс Transition с состоянием членов, символом и nextState.Я реализовал методы равенства() и hashCode(), чтобы указать, что два перехода равны, если они совпадают по состоянию и символу.Затем у меня есть java.util.Set экземпляров перехода.

В моем алгоритме обработки у меня есть текущее состояние, когда я читаю следующий символ.Я предполагал построить объект Transition, используя эти два, чтобы извлечь соответствующий Transition из набора, который затем сообщит мне следующее состояние, и я смогу выполнить итерацию.

Но я не вижу способа извлечь член java.util.Set для дальнейшего использования.Я могу удалить (Объект o), но это просто вернет логическое значение.

Что я делаю не так?

Answer 1

Set, вероятно, не то, что вы хотите использовать для этого. Я рекомендую использовать List & Lt; Переход & Gt; или возможно Карта & Lt; Государство, Список л &; Переход GT &; & GT ;. Я не уверен, что было бы лучше, если бы на самом деле это не строили и не проводили сравнительный анализ.

Answer 2

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

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

Answer 3

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

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

Если вы просто хотите реализовать механизм сопоставления с образцом, шаблон проектирования состояний может оказаться ненужным, так как шаблон вряд ли изменится. Как указал Чад, использование 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 *) ", то есть an & # 8220; a & # 8221; за которым следует либо кратное двум, либо кратное трем многим & # 8220; b & # 8221; s.