$!$ Exercise $10\mathrm{.}1\mathrm{.}5$: Suppose we have an encoding of context$-$free grammars us$-$

ing some finite alphabet. Consider the following two languages:

is a $($coded$)$ CFG$,$ A and $B$ are $($coded$)$ variables of

$G,$ and the sets of terminal strings derived from A and $B$ are the same $\}.$

$L_2=\{\begin{array}{cc}(G_1,& G_2)|G_1\end{array}$ and $G_2$ are $($coded$)$ CFG$\text{'}$s$,$ and $\{$:$L(G_1)=L(G_2)\}.$

Answer the following:

a$)$ Show that $L_1$ is polynomial$-$time reducible to $L_2.$

b$)$ Show that $L_2$ is polynomial$-$time reducible to $L_1.$

c$)$ What do $($a$)$ and $($b$)$ say about whether or not $L_1$ and $L_2$ are NP$-$

complete?