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:

C

lasses: class transit: list -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 :((..

From stackoverflow

• 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.

  avakar : Wasn't the question about *push-down* automata?

  Charlie Martin : Sure. And what's the definition of a push-down automaton? A stack with a finite state controller. So you do a nondeterministic PDA as a stack with a nondeterministic finite state controller. Solve the problem of simulating an NFA and you've got NPDA and NTM solved.

• ^ How then can you account for the fact that not all context-free languages can be recognized by a DPDA? If what you're saying is true, then any NPDA can be implemented via a NFA and a stack, ergo a DFA and a stack. Are there special restrictions on a DFA which, with a stack, simulates a DPDA? Because if not, Charlie, I think there might be a problem.

• JFLAP is open source and does this (and much more!) - why not check it out?