2
$\begingroup$

In their book, Ullman et al says:

Every nonempty CFL without $\epsilon$ has a grammar $G$ in which all productions are in one of two simple forms, either:

  1. $A\rightarrow BC$, where $A,B$ and $C$, are each variables, or
  2. $A\rightarrow a$, where $A$ is a variable and $a$ is a terminal

Further $G$ has no useless symbols. Such a grammar is said to be in Chomsky Normal Form or CNF.

whereas wikipedia says:

In formal language theory, a context-free grammar $G$ is said to be in Chomsky normal form if all of its production rules are of the form:
$A → BC$, or
$A → a$, or
$S → ε$,
where $A$, $B$, and $C$ are nonterminal symbols, $a$ is a terminal symbol (a symbol that represents a constant value), $S$ is the start symbol, and $ε$ denotes the empty string. Also, neither $B$ nor $C$ may be the start symbol, and the third production rule can only appear if $ε$ is in $L(G)$.

Also this site says:

Any Context free Grammar that do not have $ε$ in it’s language has an equivalent CNF.

So, whats correct?

  1. Can we have $S\rightarrow \epsilon$ in CNF or not? (According to Ullman, no, according to wikipedia, yes) If yes, can other non terminals have $\epsilon$ production? (According to all sources, no)
  2. Can $L(G)$ contain $\epsilon$? (According to Ullman and third reference, no, according to wikipedia, yes)

Am I missing something? and incorrectly trying to relate these sources out of some context?

$\endgroup$
4
  • 2
    $\begingroup$ It is a matter of taste. Either you include $\epsilon$ and allow a special $S\to\epsilon$ rule (as Wikipedia does), or do not care about $\epsilon$ in the language and have a clean definition (following Hopcroft&Ullman). I side with Hopcroft, and Chomsky himself. You may read my rant on this matter. $\endgroup$ Commented Dec 28, 2019 at 11:59
  • $\begingroup$ Is there any specific reason for those sources to decide to allow / disallow $\epsilon$ for it to have equivalent Chomsky Normal Form? Is there any effect of allowing / disallowing $\epsilon$ on any other related concept? $\endgroup$
    – RajS
    Commented Dec 28, 2019 at 15:52
  • $\begingroup$ The reason is "elegance", does it look right for you. Does the definition look good, does it match your intuition about what it should formalize. Note how Wikipedia is cheating: they claim to adhere to Hopcroft and Ullman, with reference and fancy pagenumbers, and then cite an alternative definition. $\endgroup$ Commented Dec 28, 2019 at 16:17
  • $\begingroup$ In several cases including/excluding $\epsilon$ might be important. One that comes to mind is in allowing $\epsilon$ as image for string homomorphisms in the theory of Abstract Families of Languages. $\endgroup$ Commented Dec 28, 2019 at 16:19

0

Your Answer

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

Browse other questions tagged or ask your own question.