Section A (5 Marks)

1. Answer the only question.
   1. Given the grammar:
      

      S → aSa | bSb | c

      a) Prove whether this grammar is ambiguous or unambiguous.
      b) Is this grammar left-recursive, right-recursive, or both? Explain.
      c) Can it be parsed using any LL(k) parser for finite k?
      d) If not, justify theoretically using the pumping lemma for context-free languages and parse tree symmetry.
      e) Suggest a strategy (not a solution) to transform this grammar to make it suitable for predictive parsing, and explain why it fails.

Section B (10 Marks)

2. Answer all questions.
   1. Given:
      

      S → Aa | b  
      A → Sd | B  
      B → Sa | ε

      a) Is this grammar left-recursive? If yes, identify both direct and indirect cases.
      b) Try to eliminate left recursion. At what point does the transformation break the parse structure? Prove.
      c) Show that no order of FIRST/FOLLOW expansion yields a disjoint LL(1) table.
      d) Construct as much of the LL(1) table as possible, and clearly indicate why it fails.

Section C (15 Marks)

3. Answer all questions.
   1. Design a context-free grammar G that satisfies all the following simultaneously:
      • Accepts palindromes over {a, b} with odd length.
      • Uses no ε-productions.
      • Has no left recursion, no common prefixes, and is LL(1)-parsable.
      • Must not use stack simulation or palindromic mirror tricks like reversing strings.

      Tasks:

      1. Define the grammar clearly.
      2. Prove G is unambiguous.
      3. Construct First and Follow sets.
      4. Show LL(1) parse table for at least 3 productions.
      5. Justify why your grammar uniquely generates odd-length palindromes without ambiguity or backtracking.
   2. Construct or identify a context-free grammar such that:
      • It is unambiguous.
      • It generates a language in P (decidable in polynomial time).
      • But it cannot be parsed by any LL(k) parser for any finite k.

      Prove all three properties mathematically using:

      • Recursive descent impossibility.
      • Necessity of infinite lookahead.
      • Optional: Reference to Ogden’s lemma or Greibach’s Theorem.