(a) Define what it means for a context-free grammar (CFG) to be in Chomsky normal form (CNF). Can a CFG in CNF ever define a language containing $\epsilon$ ? If $G_{\text {Chom }}$ denotes the result of converting an arbitrary CFG $G$ into one in CNF, state the relationship between $\mathcal{L}(G)$ and $\mathcal{L}\left(G_{\text {Chom }}\right)$.

(b) Let $G$ be a CFG in CNF, and let $w \in \mathcal{L}(G)$ be a word of length $|w|=n>0$. Show that every derivation of $w$ in $G$ requires precisely $2 n-1$ steps. Using this, give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not.

(c) Convert the following CFG $G$ into a grammar in CNF:

$$S \rightarrow a S b|S S| \epsilon$$

Does $\mathcal{L}(G)=\mathcal{L}\left(G_{\text {Chom }}\right)$ in this case? Justify your answer.