Can I implement State Transitions for a DFA in Java using java.util.Set

Question

I'm implementing a DFA as close as I can to the formal definition as a learning exercise (and blogging material)

I planned on using a java.util.Set where a set is involved in the definition.

The definition involves a set of tuples to define the legal state transitions: (state,symbol) -> nextState.

I have a Transition class with members state, symbol and nextState. I have implemented equals() and hashCode() to indicate that two Transitions are equal if they match on state and symbol. I then have a java.util.Set of Transition instances.

In my processing algorithm, I have the current state when I read the next symbol. I anticipated building a Transition object using these two to pull out the matching Transition from the Set, which would then tell me the next state, and I can iterate.

But - I don't see any way of extracting a member of a java.util.Set for further use. I can remove(Object o), but that just return boolean.

What am I doing wrong?

Answer 1

Set is probably not what you want to use for this. My recommendation would be to use a List< Transition>, or possibly a Map< State,List< Transition>>. I'm not sure which would be better without actually building it and doing some benchmarking.

Answer 2

It sounds as though your overriding of equals() and hashCode() is dubious, because the original transition matches the one in the set according to equals() and yet the two are not interchangeable (otherwise you would just use the new transition in place of the original.)

You probably want a class that is just a combination of state and symbol with no other attributes, and use that as a key in a Map. Alternatively you could use a Map<State, Map<Symbol, State>>

Answer 3

I agree with Matthew Brubaker that Set is probably not what you need. You might want to try enums instead; see the Java Glossary for an example.

Answer 4

Can't you accomplish this without having some external collection of states, or even the Transistion objects? If the State class is defined like:

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

Then, if you have a reference to the initial state, you can just move from state to state like this:

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

Answer 5

Yeah I'm kind of confused about why would even need a collection at all.

For a simple state machine you can just use static integers and a case statement to do your state machine like this:

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

That's a basic state machine that will look for any string containing 'abc'. You could easily extend that too look for ab*c or whatever you want.

So what if you want a dynamic state machine, built at runtime? Well, I've done this too. It's not too hard. What I did is create a state class with a list of transitions. Each transition has a pointer to the next state, and the criteria to link on.

So for example, STATE1 would have a transition with the criteria 'a' and a pointer to some object that represents STATE2. The code would look check the criteria (which could be an object that takes an int as a parameter and returns true or false if it matches) and if the criteria matched, it would move the state pointer to the state pointed too by the transition.

The code could look something like ths

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

Answer 6

If you just want to implement a pattern matching engine, a State Design Pattern might be unnecessary since the patter is unlikely to change. As Chad has pointed out, using a switch to encode the transition function is completely acceptable in such cases.

Here's an example of a nondeterministic pattern matching automaton that uses sets:

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

This automaton recognizes input words of the regular language described by the pattern "a(bb*|bbb*)", i.e. an “a” followed by either a multiple of two or a multiple of three many “b”s.