5,934 views

Consider the grammar

• S $\rightarrow Aa \mid b$
• A $\rightarrow Ac \mid Sd \mid \epsilon$

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

## 2 Answers

Best answer

(b) As it is the case of indirect recursion so let first make it as direct recursion then apply rules of removal of left recursion.

to make it as direct recursion first production remain unchanged while in second production substitute the right hand side of first production wherever it comes.In the question $S$ comes in middle of $A$ so substitute the right hand side of production $S$.Now after substituting it looks like:

• $A \rightarrow Ac\mid Aad \mid bd \mid \epsilon$

Now remove direct recursion from it

For removal of direct recursion rule:

• $A \rightarrow A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m$

Replace these with two sets of productions, one set for $A:$

• $A \rightarrow \beta_1A^\prime \mid \ldots \mid \beta_mA^\prime$

and another set for the fresh nonterminal $A^{\prime}$

• $A^\prime \rightarrow \alpha_1A^\prime \mid \ldots \mid \alpha_nA^\prime \mid \epsilon$

After applying these rule we'll get:

• $A \rightarrow bdA'\mid A'$
• $A' \rightarrow cA'\mid adA' \mid \epsilon$

Now complete production without left recursion is:

• $S \rightarrow Aa \mid b$
• $A \rightarrow bdA'\mid A'$
• $A' \rightarrow cA'\mid adA' \mid \epsilon$

### 4 Comments

Why did

A→bdA′∣A′   →  Here why did this single A’  come  that is the A’  in the second production come
Here is the epsilon also consider as  Beta ?????
Yes $\epsilon$ is also being considered as $\beta$ for the conversion… If you see the problem a bit intuitively, then you shall get your answer as to why is it working…
• S →Aa∣b
• A →Ac∣Sd∣ϵ

Remove indirect recursion first:-

A-> Ac | Aad | bd |ϵ

I have replace S production with RHS in above . Now we have got the grammer with direct left recursion.

Now let us remove left recursion

S →Aa∣b

A -> bd A' | A'

A' -> cA' | ad A' | ϵ

### 4 Comments

i still didn't get it, that why u haven't replaced A in S  production??

how will we get to know in exam ,that 3 is the minimum no, we might get confused!!

@Gate Fever there is a rule of doing it , we number the productions then replace in an order, you can google how to remove indirect left recursion.

ive seen in many examples that

in starting symbol,left recursion is not removed however in all non terminals,left recursion is removed

12 votes
4 answers
1
3,314 views
17 votes
1 answer
2
22 votes
2 answers
3
25 votes
1 answer
4
7,052 views