turing machine decidability language

Question

I must show that this language is decidable but I think it's not

{D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think

I give a reduction from E(TM). I suppose that this language is decidable. Let T be a Turing machine that decides it. Then we can construct a Turing machine $T'$ deciding E(TM), that behaves as follows on input $\langle D,P\rangle$.

(a) Simulate T on input $\langle D,D'\rangle$, where $D'$ is a Turing machine recognizing the empty language.

(b) Accept if and only if T accepts.

Suppose that D accepts the empty language. Then T accepts $\langle D, D'\rangle$, and so $T'$ accepts.

But suppose that D accepts some string. Then T rejects $\langle D, D'\rangle$, and so $T'$ rejects. Thus, $T'$ decides (ETM).

Can anyone help?

Answer 1

There are two major problems that prevent your argument from working.

First, you're completely missing that a Turing machine is not the same as a DFA. DFAs are much weaker than Turing machine, but in your construction you seem to be assuming that you can feed an arbitrary Turing machine into $T$, which is only assumed to work when its input is a DFA.

Second, even if we ignore the differences between machine types, if $D'$ accepts the empty language -- by which I assume you mean $L(D')=\varnothing$, then $L(D)\cap L(D')=\varnothing$ no matter what $D$ is, so your assumption that $T$ should reject $\langle D,D'\rangle$ if $D$ accepts anything is false. Here I think you have confused $\cap$ for $\cup$ in the problem statement.

---

The language you consider is actually decidable. A sketch of a procedure to decide this might be

1. Given a DFA $D$ and a new PDA $P$ we can construct a PDA $P'$ that accepts $L(D)\cap L(P)$ -- its states will be pairs of a $D$-state and a $P$-state.

2. Given a PDA you can construct a context-free grammar for the language it accepts.

3. Given a context-free grammar you can decide whether the language it generates is empty or not.

I will let you fill in the details -- how much work you need to do here depends on which prerequisites you already have available.