HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
threeconversionchomskysrepeatedwiththanmorenormalformfor

Problem

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 :)

Solution

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.

Context

StackExchange Computer Science Q#165392, answer score: 5

Revisions (0)

No revisions yet.