Question 10010 – Algorithms

(a) Solve the following recurrence relation:

  x_n = 2x_n-1 - 1, n>1
  x₁ = 2

(b) Consider the grammar

  S →  Aa | b
  A → Ac | Sd | ε

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

Correct Answer: A

Theory Explanation.