UGC NET CSE | June 2013 | Part 2 | Question: 23

Question

The equivalent production rules corresponding to the production rules $S \rightarrow S \alpha_1 \mid S \alpha_2 \mid \beta_1 \mid \beta_2$ is

• A. $S \rightarrow \beta_1 \mid \beta_2, A \rightarrow \alpha_1 A \mid \alpha_2 A \mid \lambda$
• B. $S \rightarrow \beta_1 \mid \beta_2 \mid \beta_1 A \mid \beta_2 A$, $A \rightarrow \alpha_1 A \mid \alpha_2 A$
• C. $S \rightarrow \beta_1 \mid \beta_2, A \rightarrow \alpha_1 A \mid \alpha_2 A$
• D. $S \rightarrow \beta_1 \mid \beta_2 \mid \beta_1 A \mid \beta_2 A, A \rightarrow \alpha_1 A \mid \alpha_2 A \mid \lambda$

Answer 1

$S \rightarrow S \alpha_1 \mid S\alpha_2 \mid \beta_1 \mid \beta_2 ,$

After removing left recursion we got 

$S \rightarrow \beta_1 \mid \beta_2 \mid \beta_1 A \mid \beta_2 A, A \rightarrow \alpha_1 A \mid \alpha_2 A \mid \lambda$

Hence,Option(D)$S \rightarrow \beta_1 \mid \beta_2 \mid \beta_1 A \mid \beta_2 A, A \rightarrow \alpha_1 A \mid \alpha_2 A \mid \lambda$

Comments

sir please explain how you do the left factoring in this question