NOTE: This question is NOT the same as this other nearly-identically worded question with some amazing answers. I learned a lot from it regarding the mathematical importance of the empty string, but my question is specifically regarding its usage and purpose in a context-free grammar.
Update: After @Raphael's comments, maybe a better way to word my question is this: If the presence of the empty string in a non-terminal's RHS derivation is intended to remove the non-terminal from the resulting string, why would one want to do this? In what case would it make sense to remove a non-terminal?
Original Question:
I had an assignment to create a non-deterministic derivation, which I created as follows:
\begin{align} A \rightarrow aAaBaC \ | \ aAaBc \ | \ aAaBC \ | \ aABC \ | \ d \end{align}
This I then left-factored into the following deterministic grammar:
\begin{align} A & \rightarrow aAA{'} \ | \ d \\ A' & \rightarrow aBA'' \ | \ BC \ | \ \epsilon \\ A'' & \rightarrow aC \ | \ c \ | \ C \ | \ \epsilon \end{align}
This was marked as correct by my professor.
My question though is regarding the use of the empty string. I wasn't sure if including the empty string in the derivations was correct, but it was the pattern used in some examples I've seen and I followed that usage thinking that including the empty string was expected (or implied) in every factored derivation.
But when I asked the professor for clarification on that point he stated that the empty string is not implied in every derivation, and its usage has important connotations and is rarely used.
So given that:
- What is the importance of the empty string in CFG derivations? I read that it is used to "erase" a LHS, presumably to terminate derivation and proceed to the next derivation? But I'm not clear on if there is more to it than that.
- If the empty string is rarely used in a derivation or factored derivation, when is it actually meant to be used? If it should be used sparingly I'd like to have some guidance on that so I don't just litter my derivations with it.
Thank you.