Question

Consider the following expression grammer 'G'.
$A\to B|a|CBD$
$B\to C|b$
$C\to A|c$
$D\to d$

Which of the following grammer is non-left recursive but is equivalent to G?

• A. $A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }|$
  $A^{\prime }\to BD{A}^{\prime }|ϵ$
  $B\to C|b$
  $C\to A|c$
  $D\to d$
  
• B. $A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }$
  $A^{\prime }\to cBD{A}^{\prime }|BD{A}^{\prime }|ϵ$
  $B\to C|b$
  $C\to A|c$
  $D\to d$
  
• C. $A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }|cBD{A}^{\prime }$
  $A^{\prime }\to BD{A}^{\prime }|ϵ$
  $B\to C|b$
  $C\to A|c$
  $D\to d$
  
• D. $A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }|cBD{A}^{\prime }$
  $A^{\prime }\to BD{A}^{\prime }|ϵ|B{A}^{\prime }$
  $B\to C|b$
  $C\to |c$
  $D\to d$
  

Answer 1

The correct option is C $A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }|cBD{A}^{\prime }$

$A^{\prime }\to BD{A}^{\prime }|ϵ$
$B\to C|b$
$C\to A|c$
$D\to d$

Given grammer:
$A\to B|a|CBDA\to A|a|ABD|c|b|cBD$
$B\to C|b\equiv B\to C|b$
$C\to A|cC\to A|c$
$D\to dD\to d$

Removing left recurssion from $A\to A|a|b|c|ABD|cBD$

$A\to a{A}^{\prime }|b{A}^{\prime }|c{A}^{\prime }|cBD{A}^{\prime }$
$A^{\prime }\to BD{A}^{\prime }|ϵ$
$B\to C|b$
$C\to A|c$
$D\to d$