GATE 2020 CS – Question 20
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?
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.
More Regular and Context-Free Languages, Pumping Lemma questions
- GATE 2020 CS Q42
- GATE 2019 CS Q17
- GATE 2019 CS Q25
- GATE 2017 CS (CS1) Q48
- GATE 2014 CS (CS1) Q25
- GATE 2014 CS (CS2) Q25
All Regular and Context-Free Languages, Pumping Lemma questions →