Skip to main content
edited body
Source Link
reinierpost
  • 5.9k
  • 1
  • 22
  • 38

Sipser clearly impliedimplies 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 saysame 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.

Sipser clearly implied 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 say 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.

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.

Source Link
reinierpost
  • 5.9k
  • 1
  • 22
  • 38

Sipser clearly implied 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 say 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.