Consider the NPDA \(\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right…
2015
Consider the NPDA \(\left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \perp, F =\left \{ q_{2} \right \} \right \rangle\), where (as per usual convention) \(Q\) is the set of states, \(∑\) is the input alphabet, \(Γ\) is the stack alphabet, \(𝛿\) is the state transition function, \(q_0\) is the initial state, \(⊥\) is the initial stack symbol, and \(F\) is the set of accepting states. The state transition is as follows:
Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?
- A.
10110
- B.
10010
- C.
01010
- D.
01001
Attempted by 72 students.
Show answer & explanation
Correct answer: B
Answer: 10010
Explanation:
Behaviour of the NPDA (key points):
In the first state the machine pushes each read bit onto the stack.
There is a nondeterministic transition to the popping state that can be taken either without consuming input or while consuming one input symbol (it does not change the stack).
In the popping state each input bit must be the bitwise complement of the stack top in order to pop that top symbol (so reading 1 pops a 0 and reading 0 pops a 1). Acceptance occurs when the stack bottom is reached and the machine takes the epsilon transition to the final state.
Apply this to the given prefix 101100: choose the run that pushes the first five symbols (1,0,1,1,0) and then takes the transition while consuming the sixth symbol (the final 0).
After pushing the first five symbols the stack (top to bottom) is: 0, 1, 1, 0, 1
To pop these five symbols the machine must read their bitwise complements in the same order (top to bottom): 1, 0, 0, 1, 0, which is the string 10010.
Therefore appending 10010 will exactly pop the five pushed symbols and reach the stack bottom, allowing the final epsilon transition to the accepting state. The other listed continuations do not match the required complement sequence and so will not cause the NPDA to accept.