3
$\begingroup$

Here's what Wiki says: wiki screenshot And here's what Mike Sipser says in his Introduction to Theory of Computation: enter image description here

The problem arises when you try to read the two definitions - Mike Sipser seems to be suggesting that for a grammar to be in Chomsky's normal form, it should have all of those forms while Wiki explicitly says that it has to be only one of the many.

Which one should I be believing?

$\endgroup$
1
  • 7
    $\begingroup$ I don't read the Sipser definition as saying that every possible form must be used. $\endgroup$
    – Pseudonym
    Commented Apr 17, 2023 at 4:55

2 Answers 2

16
$\begingroup$

Sipser clearly implies an or between those two rules. The two definitions say the same thing.

Meanwhile, in formal language theory, it is quite common for two textbooks or article to not say the same thing when defining terms. For instance, some definitions of context-free grammars do not permit $\epsilon$ rules at all.

So in general, the definition you should "believe" is the one used in the article or textbook you're using at the time, and when writing your own, you supply your own definition. It will be OK as long as it is essentially equivalent to a definition used by somebody else.

For instance, there is an easy and well-known rewriting process to eliminate all $\epsilon$ rules from any context-free grammar except possibly leaving $S \rightarrow \epsilon$. As a consequence, for most purposes it is of little consequence whether or not a definition of context-free grammars allows $\epsilon$ rules; that is just a detail to bear in mind while reading the text at hand.

$\endgroup$
1
  • 6
    $\begingroup$ Indeed! The $S\to\varepsilon$ is only for people that get nervous about the empty word missing in the language. Here is Hopcroft and Ullman: "Theorem 4.5 (Chomsky narmal form, or CNF) Any context-free language without $\epsilon$ is generated by a grammar in which all productions are of the form $A\to BC$ or $A\to a$. Here $A$, $B$, and $C$, are variables, and $a$ is a terminal." $\endgroup$ Commented Apr 17, 2023 at 11:22
8
$\begingroup$

Sipser doesn't require that both of those forms be used. It just requires that every rule fit one of those two patterns.

$\endgroup$

Your Answer

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

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