Removing lambda-productions when it's at the start symbol

Question

I had a question regarding removing lambda-productions from context-free grammars.

I understand that the basic theorem or process for removing lambda-productions is to find nullable productions and replace them with the version of the same production when we use lambda. However, I had a question regarding special cases.

For example:

$$S \rightarrow aSSS$$ $$S \rightarrow bb\ |\ \lambda$$

How do I remove the lambda-production here? Is it even allowed to be removed? If we remove this, then we're fundamentally changing the grammar from one that accepts the empty string to one that doesn't.

This question has been really confusing me, and any help would be greatly appreciated.

thank you!

Answer 1

You cannot, in general, remove all $\lambda$ productions. Indeed, if you grammar produces the empty string, then somewhere in the grammar there must be a $\lambda$ production.

There are two ways to handle this problem:

• Consider only grammars not producing the empty string. Such a grammar won't contain the product $S \to \lambda$.
• Allow arbitrary context-free grammars, and also allow the production $S \to \lambda$ (but not $A \to \lambda$ for $A \neq S$). If the grammar does contain the rule $S \to \lambda$, then we also ask $S$ not to be on the right-hand side of any production. Such grammars behave very similarly to grammars without $\lambda$ productions, since the production $S \to \lambda$ can only be used in the derivation $S \Rightarrow \lambda$.