Java – A Simulator for a non-deterministic Push-Down Automaton

java

Well, I need to make simulator for non-deterministic Push-Down Automaton.
Everything is okey, I know I need to do recursion or something similar. But I do not know how to make that function which would simulate automaton.

I got everything else under control, automaton generator, stack …
I am doing it in java, so this is maybe only issue that man can bump on, and I did it.
So if anyone have done something similar, I could use advices.

This is my current organisation of code:

Classes:  class transit:
  list<transit> -contains non deterministic transitions
  state
  input  sign
  stack sign class generator
  it generate automaton from file clas NPA
  public boolean start() - this function I am having trouble with

Of course problem of separate stacks, and input for every branch.

I tried to solve it with collection of objects NPA and try to start every object, but it doesn work.

Best Solution

Okay, think about the definition of the automaton. You have states and a state transition function. You have the stack. What makes life exciting is the non-determinism.

however, it is a theorem (look it up) that every nondeterministic finite automaton has an equivalent deterministic FSA.

One approach you could try is to construct the equivalent DFA. That's exponential space in the worst case, though: every state in the DFA maps to a subset of the powerset of the NFA states.

So you could try it "on line" instead. Now, instead of constructing the equivalent DFA, you simulate the NFA; at state transitions you construct all the next states you reach and put them on some data structure; then go back and see what happens next for each such state.

Related Solutions

Java – Modelling a Finite Deterministic Automaton via this data

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.

Best Solution

Related Solutions

Java – Modelling a Finite Deterministic Automaton via this data

Related Question