GATE CSE 2020 | Question: 10

Question

Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements.

1. $L$ is deterministic context-free.
2. $L$ is context-free but not deterministic context-free.
3. $L$ is not $LL(k)$ for any $k$.

 Which of the above statements is/are TRUE?

• A. Ⅰ only
• B. Ⅱ only 
• C. Ⅰ and Ⅲ only
• D. Ⅲ only

Comments

• Is $\text{DCFL} \cup \text{Regular}$ always a CFL? Yes.

• Is $\text{DCFL} \cup \text{Regular}$ always a DCFL? No.

• The Twin Contrast: Note that $\text{DCFL} \cap \text{Regular}$ is cleanly closed and is always a DCFL (via cross-product state construction with a DFA). But the moment you flip the operator to a Union ($\cup$), determinism is lost!

1. The Core Limitation of $LL(k)$

 

An $LL(k)$ parser is strictly top-down and predictive. It must commit to a single grammar production rule immediately, using a lookahead window of at most $k$ symbols into the future. It cannot backtrack or change its mind later.

 

2. The Lookahead Defeat

 

Suppose you design a parser with a lookahead window of size $k = 10$. If the input stream begins with 11 consecutive $a$'s (aaaaaaaaaaa...), your lookahead window is completely filled with nothing but $a$'s.Because the lookahead window cannot see past the 10th symbol, the parser cannot see whether there are matching $b$'s hiding further down the line (making it $a^n b^n$) or if it's just a clean run of $a$'s (making it $a^n$).3. The Fatal ChoiceIf the parser guesses the rule for $a^n$, it will crash when it eventually hits a $b$ later in the string.If the parser guesses the rule for $a^n b^n$, it will crash if the string ends up being just $a$'s with no $b$'s.Since $k$ is a fixed constant, we can always choose an input length $n > k$ to blindfold the parser. Because it requires an infinite lookahead to see the end of the $a$'s, the language is strictly not $LL(k)$ for any $k$.

---

stmt 3:

• Suppose the fixed lookahead is $k = 5$.

• When the parser sees an input starting with $a^{100} \dots$, the next $5$ tokens in the lookahead window are just aaaaa.

• At this moment, the parser cannot know whether the input will be:

  • $a^{100}$ (which needs the $a^n$ rule), or

  • $a^{100} b^{100}$ (which needs the $a^n b^n$ rule).

• To know which branch to take, the parser would need to look ahead $100$ steps to see if a $b$ or the end-of-string appears.

• Since $n$ can be made larger than any chosen constant $k$ ($n > k$), no fixed finite lookahead $k$ is ever enough.

so, no $LL(k)$ grammar can generate it for any finite $k$. 

---

In an \(LL(k)\) parser, the first "L" stands for Left-to-right scan, and the second "L" stands for Leftmost derivation

Because it must build a leftmost derivation top-down, the parser is forced to choose the correct production rule at the very beginning (at the start symbol \(S\)) before it has even read past the first few characters. Since it cannot know whether to expand into the \(a^{n}\) branch or the \(a^{n}b^{n}\) branch with only a finite lookahead, it cannot make a deterministic choice.

Answer 1

Correct Option is (C).

1. L1 is Regular and L2 is DCFL , and as we know DCFL is closed under union operation with regular set hence L is  DCFL. 

2. so option b is eliminated.

3. LL(K)  parser needs to determine the next grammar production by seeing the next  input symbols. but here parser is not able to find whether a^n or a^n b^n is to be accepted.

 

Answer 2

for opt 3,

A -> a1/a2

then,

first (a1) intersection first (a2)  not equals phi

then only not LL(k)