91Ó°ÊÓ

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

a).

Assume OVERLAP_CFG is decidable. Then this case there must be a decider for OVERLAP_CFG . So we can use S to solve Post Correspondence Problem.

Now for a given example: (B, T) of Post Correspondence Problem

Here, $B=\left\{b_1,b_2,.....b_n\right\}andT=\left\{t_1,t_2.....t_n\right\}$

We are going to define two Context Free Grammar G and H as following:

$$\begin{gathered} G=\left(\left\{b\right\},∑\text{'},B,\left\{B→s_i{B}_i\overline{)1≤i≤n}\right\}∪\left\{B→s_i{\$}_i\right\}\right) \\ H=\left(\left\{T\right\},∑\text{'},T,\left\{T→t_i{T}_i\overline{)1≤i≤n}\right\}∪\left\{T→t_i{\$}_i\right\}\right) \end{gathered}$$

Here,$∑\text{'}=∑∪\left\{\$,1,2,...,n\right\}$

Then,$L\left(G\right)âˆ\copyright L\left(H\right)≠âˆ\dots$if and only if Post Correspondence Problem has some solution.

This is because, the string within$L\left(G\right)âˆ\copyright L\left(H\right)$are the solutions of Post Correspondence Problem.

So our assumption is contradict, thus OVERLAP_CFG is undecidable.