HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Undecidable problem intersection of two DCFL languages is DCFL?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemundecidablelanguagesdcfltwointersection

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#98355, answer score: 4

Revisions (0)

No revisions yet.