patternMinor
Undecidable problem intersection of two DCFL languages is DCFL?
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 (
Post correspondence problem
The proof is based on the fact that Post correspondence problem (
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
Using pumping lemma, one can show that if $L_{\cap}$ is not empty then this language is not context-free. Since languages of
Conclusion
Assume we can decide if $D$ exists. Let's take our
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.