Могу ли я реализовать переходы состояний для DFA в Java, используя java.util.Set - PullRequest
Новая
       28

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

3 голосов
/ 15 января 2009

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

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

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

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

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

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

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

Ответы [ 6 ]

2 голосов
/ 15 января 2009

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

1 голос
/ 15 января 2009

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

1 голос
/ 15 января 2009

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

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

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

</p> <pre><code>public void move(int input){ for(transition t : currentState.transitions){ if(t.getCriteria().matches(input)){ currentState = t.getNextState(); break; } } }

1 голос
/ 15 января 2009

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

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

1 голос
/ 15 января 2009

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

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

...