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!
