# 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 . (a) Simulate T on input , 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 , and so T´ accepts. But suppose that D accepts some string. Then T rejects , and so T´ rejects. Thus, T´ decides (ETM).

Can anyone help?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Apr 6 '16 at 12:25
• Do you have a specific question? What do you think of your attempt? Hint: check out the proof for closure of CFL against intersection with regular languages. – Raphael Apr 6 '16 at 12:26
• @Raphael it should be decidable but maybe is the way I think.. It should be described in Turing Machine – theorcp Apr 6 '16 at 12:29
• Why is your reduction valid, in particular, what it has to do with $D$ and $P$?? Your reduction doesn't even consider $P$, thus cannot be correct (since $L(D)\cap L(P)$ does depend on $P$). – Ran G. Apr 6 '16 at 13:33
• @RanG. yes I see ..How I can make it for P too – theorcp Apr 6 '16 at 14:11