# Convert this CFG to Chomsky normal form.

S -> uvSS | u | v | $\epsilon$

The Chomsky normal form of a context-free grammar is such that the grammar is in the form:

A -> BC

A -> a

S -> $\epsilon$

Now, to start converting, I set the rule $S_0$ to be $S_0$ -> S.

The would make the grammar

$S_0$ -> S

S -> uvSS | u | v | $\epsilon$

Removing the epsilon from S (and then $S_0$) , we get:

$S_0$ -> S

S -> uvSS | u | v

I do not really know how to continue the conversion. I know there should be some rules applied for variables and terminals, but I'm not sure how to apply them here. Could anyone give me any pointers on how to solve this? Thanks so much.

2. Next, deal with right-hand sides of length $0$: make sure that the only $\varepsilon$-productions are of the form $S \rightarrow \epsilon$.
3. Next, deal with right-hand sides of length $1$
4. Finally, deal with right-hand sides of length $> 2$.