The GATE Grind

GATE 2020 CS – Question 20

Theory of Computation · Regular and Context-Free Languages, Pumping Lemma · 1 mark · Multiple choice

Consider the language $L=\{a^n\mid n\ge 0\}\cup\{a^nb^n\mid n\ge 0\}$ and the following statements.

I. $L$ is deterministic context-free.

II. $L$ is context-free but not deterministic context-free.

III. $L$ is not LL($k$) for any $k$.

Which of the above statements is/are TRUE?

  1. I only
  2. II only
  3. I and III only
  4. III only

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) I and III only

Explanation

A DPDA can accept $L$ by pushing a's and, at the end of input or on seeing b's, accepting appropriately, so $L$ is a DCFL and I is true. II is false. No LL($k$) lookahead can decide between $a^n$ and $a^nb^n$ while reading the a's, so III is true.