GATE CS 2015 Set 1 Q.61 (CS Q.51): Context-Free Grammars, Pushdown Automata and CFLs

Consider the NPDA $(Q = \{q_0, q_1, q_2\}, \Sigma = \{0, 1\}, \Gamma = \{0, 1, \bot\}, \delta, q_0, \bot, F = \{q_2\})$ , 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:

State transition diagram of NPDA with states q0, q1, and accepting state q2 — State transition diagram of NPDA

Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton?

$10110$

$10010$

$01010$

$01001$

Official answer and solution

Official answer: B
From: Official GATE 2015 answer key

Solution

Trace the push and pop operations of the NPDA for each stage to determine the matching suffix.

Automaton behavior:
- In state $q_0$ :
  Input 1 pushes 1: $(1, Z \to 1Z)$
  Input 0 pushes 0: $(0, Z \to 0Z)$
- Transition $q_0 \to q_1$ :
  On $0/1/\epsilon$ , stack is unchanged: $(0/1/\epsilon, Z \to Z)$ . This corresponds to the midpoint symbol or boundary between halves.
- In state $q_1$ :
  Input 0 pops 1 from stack top: $(0, 1Z \to Z)$
  Input 1 pops 0 from stack top: $(1, 0Z \to Z)$
  Each bit read in $q_1$ pops its complement from the stack.
- Transition $q_1 \to q_2$ :
  $(\epsilon, \bot \to \epsilon)$ empties the initial stack marker and accepts.
Tracing the prefix $101100$ :
All candidate options are 5 bits long, making the total string length $6 + 5 = 11$ bits.
In an 11-bit string accepted via an odd-length transition with center symbol $c$ , the first 5 bits are pushed in $q_0$ , the 6th bit is the center symbol read on transition $q_0 \to q_1$ , and the remaining 5 bits pop the stack in $q_1$ :
- Prefix of 5 bits: $10110$ .
- Pushing $10110$ onto the stack yields (bottom to top): $[\bot, 1, 0, 1, 1, 0]$ .
- 6th bit is $0$ : read by the transition $q_0 \to q_1$ without altering the stack.
- Now in state $q_1$ $q_{1}$ , to completely empty the stack to $\bot$ $⊥$ , the input bits must pop elements in order:
  - Stack top is 0 -> requires input 1 to pop.
  - Stack top is 1 -> requires input 0 to pop.
  - Stack top is 1 -> requires input 0 to pop.
  - Stack top is 0 -> requires input 1 to pop.
  - Stack top is 1 -> requires input 0 to pop.
Resulting sequence:
The sequence of bits required to pop the stack is $10010$ .

This matches option B.

Final answer

Common trap

Treating the NPDA as an ordinary palindrome acceptor instead of noticing that q1 pops the complement bit (0 pops 1, and 1 pops 0).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2015 Computer Science and Information Technology (CS) Session 1
Question: 61 of 65, printed as CS Q.51
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source