693 views
0 votes
0 votes

Here i am getting ans 8. Please explain

1 Answer

Best answer
5 votes
5 votes
Left recursion is eliminated by converting the grammar into a right recursive grammar.

Consider the grammar with left recursion: $A\rightarrow A\alpha/\beta$

Then we can eliminate left recursion by: $A\rightarrow\beta A’,A’\rightarrow\alpha A’/\epsilon$

Consider the given grammar:

$A → Ba / Aa / c$

$B → Bb / Ab / d$

First eliminate left recursion from $A →  Aa/Ba / c$ we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

Now the given grammar is:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → Bb / Ab / d$

Now put the A productions into $B\rightarrow Ab$ we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → Bb / BaA’b / cA’b / d$

now remove the left recursion from B’s production we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → cA’bB’ / dB’$

$B’ → bB’ / aA’bB’ / ∈$

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
1 answer
2
yashss2001 asked Jan 1
199 views
Consider the following C code:d=a+be=a-bf=c+dg=c-ea=f+gb=f-gc=d+eThe minimum number of total variables required to convert the above code segment to static single assignm...
2 votes
2 votes
0 answers
3
1 votes
1 votes
3 answers
4
Rahhul A asked Nov 10, 2023
466 views
$\text{ Find $\textbf{First(A)}$ and $\textbf{Follow(B)}$ }?$