ansaurus

Question

Modelling a Finite Deterministic Automaton via this data *Edit with new code*

Answer 1

+3 A:

I'd say that the most natural representation is to model each state as a Map with alphabet symbols as keys and resulting states (i.e. Map instances) as values. A class to represent an automaton would have a reference for the initial state, one for the current state, a Set of states and a Set of final states. Oh, and a Set for the alphabet.

The above should give you good performance for all relevant operations. Add some methods for convenience and encapsulation and you're done.

Edit:

You need a State class to be able to use generics correctly:

public class State extends HashMap<Character, State>{ }

public class Automaton{ 
    private Set<State> allStates;
    private Set<State> finalStates;
    private State initialState;
    private State currentState;
    private Set<Character> alphabet;

    public boolean doTransition(Character input)){
        if(!alphabet.contains(input){ 
            throw new IllegalArgumentException();
        }
        if(finalStates.contains(currentState)){ 
            throw new IllegalStateException(); 
        }

        currentState = currentState.get(input);

        if(currentState == null){ 
            throw new IllegalStateException(); 
        }

        return finalStates.contains(currentState);
    }

    // more methods go here
}

For the 3 state automaton you used as example:

State s0 = new State();
State s1 = new State();
State s2 = new State();
s0.put('a', s1);
s0.put('b', s0);
s1.put('a', s2);
s1.put('b', s0);
s2.put('a', s2);
s2.put('b', s0);

This should happen through initialization methods of the Automaton class, of course.

Michael Borgwardt 2009-12-08 23:20:37

I think this is a good idea, but I'm not familiar with Maps in Java, can you give a little code snippet for a 3 state automaton?

omgzor 2009-12-08 23:27:38

That seems great. Given the String abaa, how would I go through the states?

omgzor 2009-12-08 23:55:01

I've added a method to do transitions, you should be able to do the rest on your own.

Michael Borgwardt 2009-12-09 07:32:54

I've written new code. Please look at the problem at getting out of state 0.

omgzor 2009-12-09 15:39:53

Also, is it necessary for me to override hashCode and equals in State? Why? How should I?

omgzor 2009-12-09 18:24:36

The superclass AbstractMap already implements hashCode and equals in a useful manner. Having them is necessary if you want to use instances of the class as keys in a HashMap or elements in a HashSet (equals is used for may other purposes as well).

Michael Borgwardt 2009-12-10 08:50:14

Answer 2

+1 A:

That is a fun project.

You might want to think about the interface around your FSM first. How do you program it? How do you feed it?

Something like:

fsm.setStates("ab");
fsm.setInitialState(0);
fsm.addTransition(1,0);
fsm.addTransition(2,0);
fsm.addTransition(2,0);
fsm.setFinalState...

If you have something simple like this, it'll separate your code out and make it much easier for you to think of just one section at a time (your "UI" section, which is parsing the input and passing it to the FSM, should become trivial) This just leaves the question you ACTUALLY asked: how to implement the FSM.

There are probably a million ways, but I think the easiest to reference and work with has to be an int[][]; the transition syntax will be clear and straight forward like:

newState=table[oldState][transition];

once you've populated the array.

But remember to break your code apart and think of how you want to access the classes, not just what's the next step in the code.

Bill K 2009-12-09 00:35:30

ansaurus

tags:

views:

answers:

Modelling a Finite Deterministic Automaton via this data Edit with new code

related questions