turing machine decidability language

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?

• What is the purpose of $D'$? $T$ will never accept a Turing machine because it only accepts pairs of DFA and PDA, hence it cannot decide E(TM), at least not without modification.
– mrp
Commented Apr 6, 2016 at 12:48
• @HenningMakholm is this i wrote completely wrong? Commented Apr 6, 2016 at 16:23
• @theorcp: Completely, I'm afraid. The language is in fact decidable ... Commented Apr 6, 2016 at 16:57

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.

• I might not have all the prerequisites that's why I am posting here Commented Apr 6, 2016 at 17:15
• What details to fill? you mean that I should prove all the procedure steps? Commented Apr 6, 2016 at 17:21
• @theorcp: Yes, each of the steps needs to be explained, to the extent it is not already covered by your textbook or earlier exercises. Commented Apr 6, 2016 at 17:24
• Can you help me a bit more? Because I can't prove them, it's a bit hard for me Commented Apr 6, 2016 at 18:47
• @theorcp: I'm afraid that would start to veer into "doing your homework for you" territory. Commented Apr 6, 2016 at 18:53