# Undecidable problem intersection of two DCFL languages is DCFL?

We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an intersection of the languages of A and B. This problem is known to be undecidable. But I can't find a proof for it.

Problem statement

We have two deterministic pushdown automatas (DPDA) $$D_1$$ and $$D_2$$. The problem is to decide whether there exists a DPDA $$D$$ such that $$L(D) = L(D_1) \cap L(D_2)$$.

Post correspondence problem

The proof is based on the fact that Post correspondence problem (PCP) is undecidable. Suppose we have a PCP problem with two input lists $$\alpha = (\alpha_1, ..., \alpha_n)$$ and $$\beta = (\beta_1, ..., \beta_n)$$

Define languages

Let $$L = \{i_1...i_k\#j_m...j_1\\beta_{j_1}...\beta_{j_m}\\alpha_{i_k}^R...\alpha_{i_1}^R | \;1 \leq i_l \leq n, 1 \leq j_l \leq n \}$$ One can constructively show that there exists a DPDA $$D_1$$ that accepts $$L$$. From the other hand, the language with words $$u\u^R\#v\v^R$$ also has DPDA $$D_2$$. Let's call this language $$L_{rev}$$.

Let intersection language be $$L_{\cap} = L \cap L_{rev}$$

Emptiness of $$L_{\cap}$$ is equivalent to PCP decidability

Consider a word from $$L_{\cap}$$. It is like $$i_1...i_k\#j_m...j_1\\beta_{j_1}...\beta_{j_m}\\alpha_{i_k}^R...\alpha_{i_1}^R$$ and like $$u\u^R\#v\v^R$$. So $$\alpha_{i_1} = \beta_{i_1},..., \alpha_{i_k} = \beta_{i_k}.$$

Since then, if $$L_{\cap} \neq \varnothing$$ then there is a solution for PCP. Otherwise, there is no solution.

Emptiness of $$L_{\cap}$$ is equivalent to existing of $$D$$

Furthermore if $$L_{\cap} = \varnothing$$ then $$L_{\cap}$$ has DPDA because it is empty. Using pumping lemma, one can show that if $$L_{\cap}$$ is not empty then this language is not context-free. Since languages of DPDAs are subset of context-free languages then $$D$$ does not exist.

Conclusion

Assume we can decide if $$D$$ exists. Let's take our PCP, construct our languages and answer if $$D$$ exists. If it does exist, then the intersection language is empty and the PCP doesn't have a solution. Otherwise, it has. This way, we decide whether a solution for PCP exists. But this problem is known to be undecidable. We have come to a contradiction. Consequently, the assumption is wrong and the problem of deciding whether $$D$$ exists is undecidable.