1

There is just one part of the grammar I am having trouble with, it reads:

$$C\to CBA\mid\epsilon$$

After removing the epsilon production, I get:

$$C\to CBA\mid BA\mid CB\mid B$$

I'm confused as to whether this is correct or not. Does the latter grammar have to also include all other possible combinations from $CBA$, such as $CA$ and/or $A$?

Brian M. Scott
  • 616,228
user1889966
  • 13
  • This is incorrect, as $\epsilon$ is not in the second language. – copper.hat Nov 12 '13 at 02:59
  • @copper.hat Sorry, I'm not sure if I quite understand your comment. Can you elaborate? Thanks for the help! – user1889966 Nov 12 '13 at 03:04
  • There seems to be two issues above: (1) The first language contains the empty string ($\epsilon$), and the second doesn't. (2) Even ignoring the empty string the first language is $(BA)^$, and the second is $(B|BA)^(B|BA)$, which are different. Perhaps you wanted $C \leftarrow CAB | AB$, which is $(BA)^* BA$ (that is, the first language without the empty string). – copper.hat Nov 12 '13 at 05:24

1 Answers1

1

Removing the $\epsilon$ production from $C\to CBA\mid\epsilon$ gives you $C\to CBA\mid BA$, where the production $C\to BA$ represents the possibility of a derivation $C\Rightarrow CBA\Rightarrow BA$ using the original $C$ productions. It does not give you $C\to CB$ or $C\to B$: there is no derivation from $C$ to $CB$ or to $B$ that uses only the original $C$ productions $C\to CBA$ and $C\to\epsilon$.

If the grammar originally had a production $A\to\epsilon$, removing that $\epsilon$ production would force you to include $C\to CB$, and then removing $C\to\epsilon$ would force you to add $C\to B$ as well, but neither is needed just to compensate for removing $C\to \epsilon$.

Brian M. Scott
  • 616,228
  • Great thank you. I should have mentioned that B is also a nullable variable in the grammar. So, would the resulting grammar be C-> CBA | BA | CA | A ? – user1889966 Nov 12 '13 at 18:15
  • @user1889966: Yes, that looks right. – Brian M. Scott Nov 12 '13 at 18:17
  • @BrianM.Scott:Even though you're answer is perfect could you tell whether we could remove $\epsilon$ productions from start symbol.This article(p.6) says that we can't remove $\epsilon$ productions from start symbol. – justin Mar 22 '16 at 08:30
  • @justin: The article is correct. If the grammar has the production $S\to\epsilon$, the language contains the empty word. And once you've eliminated all of the other $\epsilon$ productions, the only way to generate the empty word is with $S\to\epsilon$, so you need to keep it. This is true whether it was originally present in the grammar, or whether it arose during the process of elimination. – Brian M. Scott Mar 22 '16 at 10:47
  • @BrianM.Scott:That's right.I forgot about the empty word in the language. – justin Mar 22 '16 at 10:52