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.


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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.