[SOLVED] Left recursion elimination questions

Left recursion elimination questions

I'm working on remove left recursion in grammar. (3 grammars)

1. A->Ab | aC
   B->BaBB | BA       
   C->bC | BA                     

2. T->Txxy | TaabT | TTa               


3. A-> BA | Baa         
   B-> Ab | Abb

I've tried to do it, but I'm not sure about my answers. First one, I have no idea how to do it. Second, the third one I think it will fail. Is my answer right? How can I change that? Please someone explain it in detail.

Solution

I have written the solution. I didn't have much time to type the entire thing and also I was not sure if this question will be available anymore because of offtopic.

Check the solution for first grammar here at first grammar solution

For the second grammar, either the Grammar is incomplete or left recursion can't be removed, there is no null production nor it has any production with only terminals. It is infinitely recurring and hence can't remove left recursion.

For the third grammar, we can do

A-> BA | Baa         
B-> Ab | Abb  

Replace All B's into A
A-> AbA | Abaa | AbbA | Abbaa

Now again all the productions are recursive and can't even terminate the grammar. You either need a null production or a production with only terminals.