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
shakssage 34 Junior Poster in Training
shakssage 34 Junior Poster in Training
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 34 Junior Poster in Training
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 761 Senior Poster
Do you think a Finite Automaton can represent a PDA? If it can the you would have proved that PDA = FA
shakssage 34 Junior Poster in Training
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 761 Senior Poster
Oh didn't see the finite part. Yes your right.
Saiiiira 0 Newbie Poster
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 34 Junior Poster in Training
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 0 Newbie Poster
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:)
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.