Translating Pushdown Automata to FSA

[shakssage]

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.

Thanks

[apines]

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

[shakssage]

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?

Q = {s0, 1, 2}, Σ = {a, b}, Γ = {a, b}, F = {2}, Δ = {((s0,a,e),(s0,a)), ((s0,b,e),(s0,b)), ((s0,a,e),(1,e)), ((s0,b,e),(1,e)), ((1,a,e),(1,e)), ((1,b,e),(1,e)), ((1,a,a),(2,e)), ((1,b,b),(2,e)), ((2,a,a),(2,e)), ((2,b,b),(2,e))}

[shakssage]

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

[mrnutty]

Do you think a Finite Automaton can represent a PDA? If it can the you would have proved that PDA = FA

[shakssage]

A PDA with a finite stack can be translated into an FSA. What you need to do is encode the stack as states.

I've done it though, so it's solved. Thanks.

[mrnutty]

Oh didn't see the finite part. Yes your right.

[Saiiiira]

A PDA with a finite stack can be translated into an FSA. What you need to do is encode the stack as states.

I've done it though, so it's solved. Thanks.

I have the same question,would you please explain to me,how should I encode the stack?

[shakssage]

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.

[Saiiiira]

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.

Thank you very much:)