The GATE Grind

GATE 2016 CS – Question 53

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple choice

Consider the transition diagram of a PDA given below with input alphabet $\Sigma = \{a, b\}$ and stack alphabet $\Gamma = \{X, Z\}$. $Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA.

[PDA diagram: three states, the first one accepting and the last one accepting. The first state loops on $a, X/XX$ and $a, Z/XZ$ (pushing an $X$ for each $a$). It moves to the second state on $b, X/\epsilon$. The second state loops on $b, X/\epsilon$ and moves to the third state on $\epsilon, Z/Z$.]

Which one of the following is TRUE?

Diagram for GATE 2016 CS question 53
  1. $L = \{a^n b^n \mid n \geq 0\}$ and is not accepted by any finite automata
  2. $L = \{a^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$ and is not accepted by any deterministic PDA
  3. $L$ is not accepted by any Turing machine that halts on every input
  4. $L = \{a^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$ and is deterministic context-free

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) $L = \{a^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$ and is deterministic context-free

Explanation

The first state is accepting, so any string of $a$'s is accepted, since pushing $X$'s never blocks it. A $b$ moves the machine to the second state, where each $b$ removes one $X$, and when only $Z$ is left it moves to the final state on $\epsilon$. That accepts $a^n b^n$ for $n \geq 1$. So $L = \{a^n\} \cup \{a^n b^n\}$. The moves are all forced by the input and the stack, apart from the end move that fires only on $Z$, so the PDA is deterministic and $L$ is a deterministic context-free language.