I am trying to convert the below context-free grammar into Chomsky Normal Form, specifically, removing rules that have three or more variables or terminators. $$S \to A a B \;\vert\; B b C$$ $$A \to A a B \;\vert\; B b C$$ $$B \to B b C$$ $$C \to x$$

I am trying to understand if the right converstion would result in this:

$$S \to A_1B \;\vert\; B_1C$$ $$A_1 \to Aa,$$ $$B_1 \to Bb,$$ $$A \to A_2B \;\vert\; B_2C $$ $$A_2 \to Aa,$$ $$B_2 \to Bb,$$ $$B \to B_3C $$ $$B_3 \to Bb,$$ $$C \to x$$

Or if it would be ok and accepted to condense the new variables into one (as they have the exact same rule):

$$S \to A_1B \;\vert\; B_1C$$ $$A \to A_1B \;\vert\; B_1C $$ $$B \to B_1C $$ $$A_1 \to Aa,$$ $$B_1 \to Bb,$$ $$C \to x$$

Thanks, I've been trying to find examples online and follow them but none seem to follow the same issue so any help will be very much appreciated :)


1 Answer 1


Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences".

Note that your final result does not yet satisfy Chomsky normal form. Productions are either of the form $A\to BC$ or $A\to a$. That means that one cannot produce a nonterminal and a terminal symbol at the same time.

  • $\begingroup$ thanks! amazing, yeah, this was just where I got stuck but I'll do that as a next step :) $\endgroup$ Feb 5 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.