Question 20

Given language: $L = \{a^n \mid n \ge 0\} \cup \{a^n b^n \mid n \ge 0\}$ over $\Sigma = \{a, b\}$.

Evaluation of Statements I and II (DCFL property):

• To test if $L$ is a deterministic context-free language (DCFL), check if a DPDA with an endmarker $\$$ can accept $L$ by final state:
  1. Read all $a$'s and push them onto the stack.
  2. If the endmarker $\$$ is read immediately (no $b$'s follow), enter an accepting state (accepts $a^n$).
  3. If $b$'s follow, transition to a state that pops one $a$ for each $b$ read. When the endmarker $\$$ is reached with an empty stack, enter an accepting state (accepts $a^n b^n$).
• Since all transitions are deterministic with the lookahead endmarker $\$$, $L$ is deterministic context-free (DCFL).
• Thus, Statement I is TRUE and Statement II is FALSE.

Evaluation of Statement III (LL(k) property):

• An $\text{LL}(k)$ parser must decide whether to expand $S \to a^n$ or $S \to a^n b^n$ after reading at most $k$ tokens of lookahead.
• If an input string starts with $a^{k+1}$, lookahead of length $k$ only sees a sequence of $a$'s ($a^k$). The parser cannot determine whether the string will terminate as $a^{k+1}$ or continue with $b^{k+1}$.
• Since $k$ is finite and the length of $a$'s can be arbitrarily large, no $\text{LL}(k)$ grammar can parse $L$.
• Thus, Statement III is TRUE.

Statements I and III only are TRUE.