Undecidability of "is this CFG prefix-free?"

Question

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition).

Another thread has the very different question "is this regular language prefix-free". One of the answers in that thread claims to prove undecidability for CFLs (even though that did not explicitly ask for a proof of undecidability for CFLs) using the usual Post Correspondence Problem (PCP) method.

The proof in the other thread claimed (as of Oct 11, 2020) that a certain CFL with an endmarker $\#$ is prefix free if and only if there's no PCP solution. However, it seems to be possible to have prefixes in the CFL even without any PCP solutions, which would mean the proof is wrong.

I also tried using the fact that "non-emptiness of intersection of two CFGs" is undecidable. However, we are only able to use undecidability of CFGs being prefix-free to prove undecidability of intersection non-emptiness, not the other way around.

Answer 1

One endmarker is insufficient to prove this. Instead, we must use multiple endmarkers. Here's the full proof, with the same basic idea taken from the other answer.

Using the notation from Sipser 3rd edition problem 5.21, let the string pairs $(t_i, b_i)$ for $i \in \{1, 2 \ldots k\}$ be an instance of the PCP problem. Define grammar rules $T \rightarrow t_i T \texttt{a}_i$ and $T \rightarrow t_i \texttt{a}_i$ (where $\texttt{a}_i$ are new symbols) along with $B \rightarrow b_i B \texttt{a}_i$ and $B \rightarrow b_i \texttt{a}_i$. This instance of PCP has a solution if and only if $T \cap B$ is non-empty. (This construction can be used to prove many other undecidability properties of CFGs; for more, see Sipser 3rd edition chapter 5 or Hopcroft and Ullman 3rd edition chapter 9).

Define more rules $W \rightarrow T\#$ and $W \rightarrow B\#\#$, where $\#$ is another new symbol. Clearly, $W$ is prefix free if and only if $T \cap B$ is non-empty. Hence, a decider for prefix-free CFGs would also decide any PCP problem. Since PCP is undecidable, we have a contradiction, and thus the language of prefix free CFGs is also undecidable.