1
$\begingroup$

I'm taking a computational structures course and we just started going over context free grammars. I was confused when I started seeing lambda productions. What are they? Can't seem to find an answer anywhere.

$\endgroup$
2
$\begingroup$

$\lambda$ (lambda) is sometimes used to denote the empty string. Thus, a "lambda production" is a production like $A \to \lambda$, i.e., a production that allows a non-terminal to generate the empty string.

Other sources will use $\epsilon$ (epsilon) to denote the empty string. They might refer to them as epsilon productions. They're the same thing. It's just a difference in notation.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So if were thinking of this as a binary tree, the lambda productions are the leafs that have no children? $\endgroup$ – user406955 May 6 '17 at 0:25
  • $\begingroup$ @user406955 Not quite, since any production resulting in a terminal string (e.g., $A\to b$) is a leaf. $\lambda/\varepsilon$-productions are productions that generate nothing at all. $\endgroup$ – David Richerby May 6 '17 at 11:04

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.