Project ForgeConsider the language L = {aⁿ | n ≥ 0} ∪ {aⁿbⁿ | n ≥ 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?
- AI only
- BII only
- I and III only
- DIII only
Explanation
A deterministic PDA CAN recognize L: read a's, and on seeing the FIRST 'b' commit to matching aⁿbⁿ mode using the stack, while on reaching end-of-input while still reading a's, accept as the aⁿ case — a DPDA never needs to guess since it can use end-of-input / arbitrary lookback via the stack pushed so far, making L deterministic context-free (I is TRUE, so II is false). However, L is NOT LL(k) for any fixed k: to decide (using only the next k symbols of lookahead) whether the current a's belong to the 'aⁿ' branch or the 'aⁿbⁿ' branch, a parser may need to look arbitrarily far ahead to see whether a 'b' eventually appears — no fixed k suffices (III is TRUE). So I and III only.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.