Question

1. Remove left recursions if any

A -> Aab | abA | ab
B -> bb | Bb | bB

Answer 1

Solution:

Left Recursion:

If a grammar contains the Productions of the form A --> Aα / β it is called Left Recursive grammar.

Left Recursion can be eliminated by the two Productions

A --> β A¹

A¹  --> α A¹ /  ξ

The Given Grammar is:

A --> Aab / abA/ab

B --> bb / Bb /bB

First take ,

A --> Aab / abA/ab here left recursion production is : A --> Aab / ab ( A--> abA is not left recursive)

Elimination of Left Recursion is : A --> Aab / ab

here ab=α(alpha)/ β(beta) ie ab

using the following productions: A --> abA¹

  A¹ --> abA¹  / ξ (epsilon)

where as alpha (α) = ab and beta(β) = ab

Next take the production B --> bb / Bb /bB

Here left Recursion is : B --> Bb / bb ( B--> bB is not left Recursive)

Elimination of Left Recursion is :B --> Bb / bb

here b=α(alpha)/ β(beta) ie bb

using the following productions: B --> bbB¹

  B¹--> bB¹ / ξ (epsilon)

where as alpha (α) = b and beta(β) = bb