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


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
  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 Question