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?
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
[...]