5
$\begingroup$

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!

$\endgroup$
5
$\begingroup$

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$.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the clear answer. I'm taking a Theory of Computation class, and the textbook I'm using didn't provide a clear explanation on this. I was quite surprised because it seems like a rather important concept to handle lightly. $\endgroup$ – Seankala May 24 '18 at 1:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.