# Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

• Given any Context-Free-Grammar, $G$, and another in Chomsky Normal Form, $G_c$, how can we check if both $G$ and $G_c$ generate the same language?

One of the trivial ways I know of is to convert $G$ into a CNF form. which motivates my second question,

• Can two different Context-Free-Grammars in CNF, $G_c$ and $G_c^\prime$, generate the same language? (I would appreciate a proof of it)
• Equivalence of CFGs is undecidable. – G. Bach Sep 22 '13 at 15:08

Compare \begin{align}S &\to AB \\ B &\to BB \\ A &\to a \\ B &\to b\end{align} With \begin{align}S &\to AB \\ A &\to AB \\ A &\to a \\ B &\to b \end{align} By what comparison would these grammars be equal?