1
$\begingroup$

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:

  1. 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.
  2. 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.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ I'm not sure there's much of an answerable question here. You seem to be asking of what use, intuitively, a certain syntactic construct is. I don't think there's a clear answer: we know (by CNF and GNF) that we don't need $\varepsilon$-rules for anything but deriving the empty word (in the context-free realm, that is) but they may come in handy. This is similar to using non-determinism in finite automata. When and how to use such superfluous features is a matter of taste -- hence there is no objective answer. $\endgroup$ – Raphael♦ Nov 7 '16 at 10:25
  • $\begingroup$ @Raphael I get what you are saying. Maybe I'm just not able to ask the question more clearly because I'm still learning the topic. What I'm trying to get at is, when I see derivations in a CFG, why are empty strings used in some derivations but not others? What is the empty string supposed to signal to the parser when processing the input string against the specified language? There has to be a purpose for it to be there, I'm just not clear on what that purpose is, and therefore not sure when I should include it and when to leave it out. Does that make more sense? Thanks. $\endgroup$ – Dave Nov 7 '16 at 19:06
  • 2
    $\begingroup$ "There has to be a purpose for it to be there" -- why does there have to be a deeper reason? If you looks at the standard parsing algorithms, I think you'll find that, quite clearly, $\varepsilon$ doesn't "signal" anything; it does not have a special meaning in this sense. In fact, it can invite trouble (as it is easy to make a grammar ambiguous by accident). So, imho, the answer here is "no" but it's probably impossible to prove that to you, because your question is not a formal one. $\endgroup$ – Raphael♦ Nov 7 '16 at 19:14
  • 3
    $\begingroup$ @Dave: The only real answer is that an empty production indicates that a non-terminal could derive the empty string. For example, given $OptionalNumber \to Number | \epsilon$, the difference between $ExitStatement \to "exit" Number$ and $ExitStatement \to "exit" OptionalNumber$ should be obvious. Clearly, it would be easy to avoid the use of the epsilon rule here, but it seems more intuitive this way, no? $\endgroup$ – rici Nov 7 '16 at 21:30
  • 1
    $\begingroup$ 1) Your recursive rule works perfectly (if not exactly equivalently) without the empty word: $A \to aA \mid a$. 2) Well, I've told you "no"; now it's your turn to work with that. Keep in mind that in CS (or any science) it's rarely about fixed patterns or rules; if you have such, it's almost too boring to talk about! ;) $\endgroup$ – Raphael♦ Nov 8 '16 at 10:29

Your Answer

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

Browse other questions tagged or ask your own question.