Give an equivalent CFG for the following PDA. Include state transition table.
Summary
We have given PDA for which we have to construct a context Free Grammar and we also have a Push Down Automata. Pushing the ‘Z’ symbol into it, we are considering empty character as stack top and from state q1 on taking empty string.’$’ symbol will not become stack top. So, it is not possible to be at the final state. (This is the flaw in the question.)
Explanation
In the given PDA, we have to perform certain steps :
Step 1: Taking ᵋ(empty string) and ᵋ of stack top, we will push $ into the stack.
Step 2: Now state q1, taking ᵋ and also having ᵋ on stack top, we will now push Z.
Step 3: Now state q2, on getting ‘a’ we will push ‘a’ into our stack, and on getting ‘b’ we have ‘a’ on the top of the stack, we will pop ‘a’.
Step 4: In the state q3 on taking ᵋ and having ᵋ on the top of the stack we push ‘a’ into the stack and again on ᵋ as input character having ‘a’ as stack top, we pop ‘a’ from the stack.
Step 5: From q4 state on having any number of ‘a’ on ‘b’ on ‘$’ we pop and remain in the same state. And an accusing a final ‘$’ we move to the final state.
Note: Initially we pushed two symbols ‘$’ and ‘Z’ into the stack’s ‘Z’’ is never popped out. In that case, we never reach the final ‘$’ so we never reach the final state.
The given PDA doesn’t accept any string.
State transition table
| Input | ε | a | b | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| stack top | ε | a | b | $ | ε | a | b | $ | ε | a | b | $ |
| q1 | q2,Z | |||||||||||
| q2 | q3,a | q2,a | q2,ε | |||||||||
| q3 | q4,ε | |||||||||||
| q4 | (q4,ε)
(q5,ε) |
q4,ε | q4,ε | |||||||||
| q5 | ||||||||||||
| q0 | q1,$ | |||||||||||
Also, Read Break and Continue in C.