A grammar $G=(V, \Sigma, R,S)$ is in chomsky normal form if every production rule $\in R$ has one of the following shapes:

• $S \rightarrow \epsilon$
• $A \rightarrow x, x\in \Sigma$
• $A \rightarrow BC: B,C \in V \wedge B, C \neq S$

<aside> 🆕 The start variable $S$ never appears on the right side.

</aside>

Proof

We claim:

<aside> 🤔 Every context free language can be generated by a context free grammar in chomsky normal form.

</aside>

We will demonstrate a general way to convert any grammar into CNF.

Consider the grammar $G=(V, \Sigma, R,S)$, not yet in CNF.

• Create a new start variable $S_0 \rightarrow S$

And somehow we must

1. Eliminate $A \rightarrow \epsilon$ rules where $A \neq S$
2. Eliminate unit productions $A \rightarrow B$
3. Eliminate $A \rightarrow u$ where $|u| \gt 2$ for any $u \in (V \cup \Sigma)^*$

1

We add, for every rule with an instance of $\alpha A\beta$ on the RHS, another rule $\alpha \epsilon \beta = \alpha \beta$. we can then get rid of $A \rightarrow \epsilon$ . Rather intuitive.

$(\alpha, \beta \in (V \cup \Sigma_\epsilon)^*)$

2

Similar to 1. Cut out the middle man. replace all instances of $B$ in any $A \rightarrow B$ with the RHS of the $B$ production rule. Trivial.