context-free-grammarcomputation-theorycontext-free-languagechomsky-normal-form

Converting to chomsky normal form, eliminating epsilon


I have a following CFG rule :

I am on the epsilon elimination stage of the algorithm, I have eliminated following eplsions C -> epsiolon, B -> epsilon and here is what i got so far :

  • S_0 -> S
  • S -> BSA | SA | epsilon
  • A -> abC | a | c| ab
  • B -> baC | b | ba
  • C -> aCc | AB | ac| A Should I also eliminate S-> epsilon(shown in bold) since S is the original start variable?

Should I also copy the epsilon to S_0 at the unit rule stage of the algorithm?


Solution

  • I your first grammar, You can derive epsilon from S. So the empty word belong to the described language. Therefore you must have a epsilon in the second equivalent grammar. Now in a normal form grammar, when there is a derivation S -> epsilon, then S can't appear on the right of a derivation. So the rule

    S -> BSA | SA | epsilon
    

    is not allowed is a Chomsky normal form. So you probably want something as

    S_0 -> S | epsilon      // initial
    S -> BA | A | BSA | SA
    [...]