Chomsky Normal form removing epsilon transitions

1
votes

I'm working on converting a CFG to Chomsky Normal Form but I'm having some difficulty.

I have this CFG

A-> BAB|B|epsilon B -> 00|epsilon

Ok I add a new start state

S -> A A-> BAB|B|epsilon B -> 00|epsilon

Then I have to remove epsilon transitions so I start with B

S -> A A-> BAB|B|AB|BA|A|epsilon B -> 00

How do I then remove the epsilon from A? Can the start have an epsilon in it? And how do I convert A-> A?

1
chomsky-normal-form

1 Answers

0
votes

You can't convert this grammar to one without ε, and therefore it cannot be written in Chomsky Normal form. This is because all productions can reduce to ε, therefore ε is a valid sentence in the language.