Hi, I've been trying to translate a PDA with a finite stack to an FSA and haven't succeeded. What approach do I take to do this? It can be non-deterministic.

I recommend that you'll start here, read about regular grammar to give you a direction.

I know about regular grammars and how to construct CFG's etc. But I don't see how that will help translating a pushdown automata with finite stack size to an FSA?

More specifically. If my PDA has the following characteristics with stack of size two, how do I go about translating it into an fsa?

I've tried to create states for each stack state. So there are 2 stack alphabets and stack size of 2, so that would be (2+1)^2 stack states right (including empty stacks)?

After having done that, I can't seem to figure out how to make the transitions.
Totally confused :S

This is taken from the solutions provided by my lecturer:

For every state in the PDA, produce new states for an FSA so that each new state corresponds to the old state, plus one of its possible stack configurations. As the stack is of finite size, there are only finitely many of these. Then for each transition of the PDA, produce a transition for the FSA from the state corresponding to the first state and stack, going to the state corresponding to the resulting state and stack. The start state of the FSA is the start state of the PDA with empty stack. The accept states of the FSA are the accept states of the PDA with empty stack.

This is taken from the solutions provided by my lecturer:

For every state in the PDA, produce new states for an FSA so that each new state corresponds to the old state, plus one of its possible stack configurations. As the stack is of finite size, there are only finitely many of these. Then for each transition of the PDA, produce a transition for the FSA from the state corresponding to the first state and stack, going to the state corresponding to the resulting state and stack. The start state of the FSA is the start state of the PDA with empty stack. The accept states of the FSA are the accept states of the PDA with empty stack.

I hope not to scare you with this long post. I'm testing Solr (read solar) and it works fine. I have an issue with the DataImport handler, it's set ...