(a) Solve the following recurrence relation xₙ = 2xₙ₋₁ − 1, n > 1 x₁ = 2 (b)…

PYQ GATE 1998

(a) Solve the following recurrence relation

xₙ = 2xₙ₋₁ − 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 sales.

Sign up free to check your answer

Sign up free

Explore the full course: Zero To Hero

Loading lesson…