Convert this CFG to Chomsky normal form.

Question

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.

Answer 1

Michael Sipser's book Introduction to the Theory of Computation describes an algorithm that will convert a context-free grammar to an equivalent context-free grammar in Chomsky normal form in Section 2.1.

The underlying idea is to replace all the rules that fail to obey the CNF format with equivalent rules that obey the format.

1. First, make sure that the start symbol does not occur on the right-hand side of any rule and that no right-hand sides contain a mix of nonterminals and terminals.
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$.

The book contains examples that show how this is to be carried out. Have a look at them.