Chomsky Normal Form Transformation

68 Views Asked by At

I've been struggling a bit with creating the Chomsky normal form derivation of a grammar that I have been given

The grammar in question is:

$S \to BB \mid 0A0 \mid 1B1 \\ A \to C \\ B \to S \mid \varepsilon \\ C \to S \mid A$

So far I have ended up with

$S0 \to S \\ S \to BB \mid 0A0 \mid 1B1 \mid 00 \mid 11 \\ A \to BB \mid 0A0 \mid 1B1 \mid 00 \mid 11 \\ B \to BB \mid 0A0 \mid 1B1 \mid 00 \mid 11 \\ C \to BB \mid 0A0 \mid 1B1 \mid 00 \mid 11$

I assume i am doing something horribly wrong, when doing eliminating unit transitions; would anybody be able to give me a clear explanation of the steps taken?

Thank you!