[deathblader900]

Let G be the grammar :

S --> A | B

A --> aaB | Aab | Aba

B --> bB | Bb | aba
construct a new grammar G' that contains no left recursive rules and is equivalent to G.

This is the answer i came up with, but i brought it to my professor and he advised me it was wrong. He refused to tell me how to fix it because it is has to be turned in for a grade later. All help is appreciated. I AM VERY CONFUSED ON THIS, AND ALL INSIGHT IS GREATLY APPRECIATED

GL: S0→ S | λ
S→ ABC | AB
A→ aA | a
B→ bB | A
C→ cC

[mojo666]

Based on your answer, you do seem incredibly confused. I feel like we need to start at the beginning. I'll try to be brief.

A grammar is simply a set of rules that can produce all strings that belong to a particular language. Grammars function by replacement. We start with a letter and we keep replacing letters until we are left with nothing but terminals (letters which have no replacement rules). Using your grammar G as an example, we can start with S and then

//replace S with A
A

//replace A with Aba
Aba

//replace A with aaB
aaBba

//replace B with aba
aaababa
//There is nothing left that can be replaced

//alternatively we could replace S with B
B

//replace B with Bb
Bb

//replace B with aba
abab
//There is nothing left to replace

So "aaababa" and "abab" are two of the strings that are in the language defined by the grammar.

You are given a grammar and are required to come up with an equivalent grammar that is not left recursive. In order to be equivalent, your grammar would need to produce the exact same strings that G produces. We already notice a problem in that your grammar GL can produce strings with the terminal "c" in them while the grammar G cannot. So, your grammar is clearly not equivalent to the given grammar.

If we perform a replacement rule X and later produce a string that begins with X, then X is left recursive. There are formal algorithms to remove left recursion, but this problem is simple enough to just think through. I would first identify the left recursive elements. Then, move the recursive letter in that element to the end of the string. Finally, you will have to adjust the rules to maintain the equivalence of the language. This usually involves breaking one rule into multiple rules and adding terminals. Here is an example.

X->XYZ | a
//the strings produced by this rule are an "a" followed by 1 or more "YZ"

//"XYZ" is left recursive.  First move the "X" to the end
X -> YZX | a
//now this produces 1 or more "YZ" followed by an "a"

//to move the "a" back to the front, we break this into two rules
X -> aB
B -> YZB
//this produces an "a" followed by infinite YZ

//to make it 1 or more "YZ" we add an element that allows B to end its loop
X -> aB
B -> YZB|YZ
//this produces an "a" followed by 1 or more "YZ".  It is equivalent and non left recursive

I hope this helps you out a bit with grammars.