Hi,
I have a grammar:
A->Aa|bB|c

The above is the left recursive language.
I understand that I have to remove the string "Aa" from the above grammar.

Some body please guide me how to do that.

Zulfi.

 

Have you tried Googling "How to eliminate left recursion"?

It seems like you'll search the Internet for answers to the exact, specific problem you want an answer to, but you won't search the Internet for how to solve the general kind of problem yourself.

 

I can't find any example. If you have one, please provide me the link.
Zulfi.

 

If I can find one by searching with Google, then you can as well! Since I’m watching TV and it’s your homework, perhaps you should do the search.

 

If I can find one by searching with Google, then you can as well! Since I’m watching TV and it’s your homework, perhaps you should do the search.

Hi,
Thanks for your reply. I found one but I did find it useful. If I find something useful, I really mention it on the forum to appreciate other's work. Also this is not homework question but I have to post it on this forum as in the past I was asked to do so. I think home work questions have a better response time.

I have found one link which I am providing:


Example Eliminating left recursion



<Example 12 Consider again the following grammar.

S-->Aa | b

A-->Ac | Sd | epsilon>


Sorry I can't understand what is meant by ordering here
<We order the nonterminals: S < A.>
Maybe just because of this problem I did not mention this post earlier. Even the first step is not clear to me.

<There is no left recursive S-productions.

So the next step is to remove S from the right-hand side of the A-productions of the form A-->S



S-->Aa | b

A-->Ac | Aad | bd | epsilon



Then we remove the left recursive A-productions.>

Both "Ac" and "Aad" are left recursive, how they created A'? Why they can't have:
A-->cA'| adA'|bd |expsilon? Why changed "bd" to "bdA'"?

Somebody please guide me.
<
S-->Aa | b

A-->bdA' | A'

A'-->cA' | adA' | epsilon>

Zulfi.

 

If you have

A -> Ac | ε

then you can replace that with

A -> cA | ε

because at the end of the day both produce a string of zero or more a's and that's it.

But as soon as you add something else, all bets are off.

A -> Ac | b | ε

is NOT the same as

A -> cA |b | ε

because the first can produce "bc" while the second can't. Similarly, the second can produce "cb" while the first can't.