ISRO | CS ISRO 2013 | Pregunta 6 – Part 5

¿Cuál de las siguientes producciones elimina la recursividad por la izquierda en las siguientes
producciones:
S → Aa | b
A → Ac | SD | ε
(A) S → Aa | b
A → bdA’
A’ → A’c | A’ba | un | ε
(B) S → Aa | b
A → A’ | bdA’,
A’ → cA’ | adA’ | ε
(C) S → Aa | b
A → A’c | A’d
A’ → bdA’ | CA | ε
(D) S → Aa | bA
→ cA’ | adA’ | bdA’
A’ → A | ε

Respuesta: (B)
Explicación:

To remove left recursion from the grammar of the
form :  A → Aα | β
We rewrite the production rules as:
           A → βA'
           A'→ αA'| ε

Given Grammar: S → Aa | b
               A → Ac | Sd | ε

after finding indirect left recursion, grammar:

               S → Aa | b
               A → Ac | Aad | bd | ε

here, α = c, ad, β = bd

So, Grammar after removing left recursion = 
               S → Aa | b
               A → A' | bdA'
               A'→ CA'| ada'| ε 

Entonces, la opción (B) es correcta.
Cuestionario de esta pregunta