Context Free Grammars : How do I terminate the lambda in my non-terminal when it has left recursion?

Question

I have this context-free grammar and I am trying to remove the lambda in non terminal B. How do I go about this without it recursively having a lambda in B?

S -> B
A -> λ | aAb
B -> BB | λ | C
C -> A | aCc

Answer 1

During λ elimination, it's possible that the same production would be added twice or more to the set of a productions. Since it is a set, it can only have at most one of any element, so adding an element which is already present does nothing. The fact that the right-hand side is empty changes nothing.

So to λ-eliminate B, we need to find all instances of B and add new productions with that use removed. The only uses of B are in S and B itself, so we proceed to add the productions:

• S → λ
• B → B (by removing the first B in B → B B);
• B → B (by removing the second B in B → B B);
• B → λ (by removing the B from the production B → B which we just added.)

However, none of the new productions for B are actually added to the set. Recursive unit productions (B → B) are simply dropped, and B → λ is already present.

If we add a new λ production for a symbol other than the start symbol, we need to mark that symbol as needing λ-elimination (or call the elimination procedure recursively). But that doesn't happen here because the added production was already present.

Once we have finished λ-elimination, we remove all λ productions except for the start symbol.

In practice, there are some optimisations possible but the algorithm is probably clearer this way.