GATE 2015 CS – Question 50
Consider the NPDA $\langle Q = \{q_0, q_1, q_2\}, \Sigma = \{0, 1\}, \Gamma = \{0, 1, \bot\}, \delta, q_0, \bot, F = \{q_2\} \rangle$, where (as per usual convention) $Q$ is the set of states, $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, $\delta$ is the state transition function, $q_0$ is the initial state, $\bot$ is the initial stack symbol, and $F$ is the set of accepting states. The state transition is as follows:
[Transitions: at $q_0$, on input 1 with top $Z$, push 1 on top ($1, Z \to 1Z$), and on input 0 with top $Z$, push 0 ($0, Z \to 0Z$). From $q_0$ to $q_1$ on $0/1/\epsilon$ with top $Z$ the stack is unchanged ($Z \to Z$). At $q_1$, input 0 with top 1 pops it ($0, 1Z \to Z$) and input 1 with top 0 pops it ($1, 0Z \to Z$). From $q_1$ to $q_2$ on $\epsilon$ with top $\bot$, pop it ($\epsilon, \bot \to \epsilon$).]
Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) 10010
Explanation
In $q_0$ the machine pushes the symbols it reads, then optionally reads one middle symbol on the move to $q_1$. In $q_1$ each input symbol must be the opposite of the symbol on top of the stack, and the stack must be exactly empty at the end. Take the first 5 symbols of 101100 as the pushed part, which is 10110, so the stack from top to bottom is 0, 1, 1, 0, 1. The last symbol 0 of 101100 is the middle symbol read on the move to $q_1$. The remaining input must be the opposites of the stack from the top: 1, 0, 0, 1, 0, which is 10010.