GATE CS 2020 Set 1 — Question 20

Statement I: TRUE. $L = a^* \cup \{a^n b^n \mid n \ge 0\}$ is accepted by a DPDA by final state. The DPDA pushes one symbol for each $a$ and stays in an accepting state while it is reading $a$'s, because every $a^n$ is in $L$. On the first $b$ it switches to a popping state and pops one symbol for each $b$. It accepts exactly when the stack returns to its bottom marker, and it rejects any $a$ that comes after a $b$. Every move is forced by the next input symbol, so $L$ is a DCFL.Statement II: FALSE. It contradicts I. $L$ is context-free and deterministic context-free.Statement III: TRUE. While reading the leading $a$'s, a top-down (LL) parser must already have committed to whether those $a$'s will later be matched by $b$'s (the $a^n b^n$ part) or not (the $a^*$ part). Take the inputs $a^m$ and $a^m b^m$ with $m > k$. Their first $k$ symbols are both $a^k$, so $k$ symbols of lookahead never reveal which choice is right. Hence $L$ has no $LL(k)$ grammar for any $k$. This is a standard example of a DCFL that is not $LL(k)$: every DCFL is $LR(1)$, but not every DCFL is $LL(k)$.So statements I and III are true.Answer: (C) I and III only