I'm still quite new to regex, and I've seen topics online of people talking about removing lambda productions, but that has yet to be discussed in the class and the only formal definition of the rules in a grammar that I was given by my teacher:

$rule ∈ V$ $\times$ $(V ∪ Σ)^*$

where V is the set of variables and Σ is the set of terminals. Going strictly from this definition, I would assume I should be able to generate an empty string since V and Σ are both sets and that I believe the empty string can be generated from either of those sets.

For an exam I was given this definition of a grammar G:

$S \rightarrow aS | Sb | a$

and I was later asked to write a regex that would represent this grammar. I figured that $S \rightarrow λ$ should be implicit. In other words, I should be able to generate the string 'b' from $Sb \rightarrow λb$

The regex I gave was $a^*b^*$

The T.A. marked it as incorrect because my regex can generate b, but the grammar G cannot, and because G does not have $S \rightarrow λ$

Can someone explain why $S \rightarrow λ$ would not be included in this grammar based on the definition of $rule ∈ V$ $\times$ $(V ∪ Σ)^*$?

Thank you!


1 Answer 1


No. $S \to \lambda$ is not implicit. It is only present if it is explicitly listed in the grammar, otherwise there is no such production. There are no implicit rules. You've misinterpreted the definition. The definition says what kinds of rules are allowed to be present in the grammar, not what will definitely be present.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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