(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. Give an algorithm that, on input of any word $v$ on the terminals of $G$, decides if $v \in \mathcal{L}(G)$ or not. Explain why your algorithm works.

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

$$\begin{aligned} S \rightarrow & S b b|a S| T \\ & T \rightarrow c c \end{aligned}$$

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