A Simulator for a non-deterministic Push-Down Automaton

Question

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 :((..

Answer 1

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.

Answer 2

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

Answer 3

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