0

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

4
Contributors
9
Replies
10
Views
6 Years
Discussion Span
Last Post by Saiiiira
0

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))}

Edited by shakssage: n/a

0

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

0

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.

0

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?

0

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.

Edited by shakssage: n/a

0

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:)

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.