Question

Prove that the following two languages are undecidable.

1. and are CFGs where. (Hint: Adapt the hint in Problem 5.21.)
2. .

Short answer

1. OVERLAP_CFG is undecidable.
2. PREFIX - FREE_CFG is undecidable.

Step-by-step solution

Undecidability

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

Solution of part (a).

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\},\sum \text{'},B,\left\{B\to s_i{B}_i\overline{)1\le i\le n}\right\}\cup \left\{B\to s_i{\$}_i\right\}\right) \\ H=\left(\left\{T\right\},\sum \text{'},T,\left\{T\to t_i{T}_i\overline{)1\le i\le n}\right\}\cup \left\{T\to t_i{\$}_i\right\}\right) \end{gathered}$$

Here,$\sum \text{'}=\sum \cup \left\{\$,1,2,...,n\right\}$

Then,$L\left(G\right)\cap L\left(H\right)\ne \varnothing$if and only if Post Correspondence Problem has some solution.

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

So our assumption is contradict, thus OVERLAP_CFG is undecidable.