Section A (2 × 6 = 12 marks)

1. Answer any two questions.
   1. Given the grammar:
      S → Aa | b
A → Sd | ε
      a) Identify and prove if there's indirect left recursion.
      b) If yes, eliminate the indirect left recursion.
      c) Compute First(S) and Follow(S) for the transformed grammar.
      d) Is the resulting grammar LL(1)? Prove using intersection conditions.
   2. Given the grammar:
      S → AB | aB
A → ε | a
B → b | ε
      a) Derive First(S) and Follow(S).
      b) Justify with reasoning whether this grammar is LL(1) or not.
      c) What is the real cause of any LL(1) conflict in this case: ambiguity, common prefix, or left recursion?
   3. Given CFG:
      S → AB | C
A → Aa | ε
B → bB | ε
C → cD
D → d | C
      a) Identify and remove unreachable or non-generating symbols.
      b) Prove whether the grammar is ambiguous using two distinct leftmost derivations of the same string.
      c) Is this grammar inherently ambiguous? Justify.

Section B (1 × 18 = 18 marks)

2. Answer any one question.
   1. Given the grammar:
      S → (S)S | ε
      a) Prove whether this grammar is ambiguous or unambiguous.
      b) Does it have left recursion?
      c) Perform left factoring if needed.
      d) Construct the First and Follow sets for S.
      e) Build the LL(1) parsing table.
      f) Simulate LL(1) parsing for the string: "(()())"
      g) Identify the exact point where backtracking would be required if the parser is not LL(1)-compliant.
   2. Given:
      S → aA | bB | ε
A → aS | b
B → bS | a
      a) Show all possible leftmost derivations for the string "aba".
      b) Compute First and Follow sets.
      c) Identify non-determinism, if any.
      d) Construct the LL(1) table and mark the conflicting cells (if present).
      e) Suggest a grammar refactoring to make it LL(1).
      f) Prove whether the original or transformed grammar is predictive parseable or not.