GATE CS 2020 Q10 — Regular and Context-free Languages

To determine which statements are true, let us analyze the language $L = \{a^n \mid n \geq 0\} \cup \{a^n b^n \mid n \geq 0\}$.

Statement I is TRUE (and Statement II is FALSE):

We can construct a Deterministic Pushdown Automaton (DPDA) that accepts $L$ by final state:

• Start state $q_0$ is accepting (to accept $\epsilon$).
• For each $a$ read, push $a$ onto the stack and transition to state $q_1$ (which is an accepting state). This ensures any string of the form $a^n$ is accepted.
• If a $b$ is encountered while in $q_1$, transition to state $q_2$ (non-accepting) and pop $a$ from the stack.
• For subsequent $b$'s, stay in $q_2$ and pop $a$.
• If the stack becomes empty (only $Z_0$ remains) after reading all $b$'s, transition to state $q_3$ (accepting).

Since all transitions are deterministic, $L$ is a Deterministic Context-Free Language (DCFL).

Statement III is TRUE:

For any fixed lookahead $k$, if the parser sees $a^k$, it cannot determine whether the string is of the form $a^n$ (with no $b$'s) or $a^n b^n$ (where $b$'s appear after $n \ge k$ symbols). Since this ambiguity cannot be resolved with a finite lookahead of $k$ symbols, $L$ is not $LL(k)$ for any $k$.

Thus, statements I and III only are TRUE.