1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Apr 6 '16 at 12:25
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Apr 6 '16 at 12:26
  • $\begingroup$ @Raphael it should be decidable but maybe is the way I think.. It should be described in Turing Machine $\endgroup$ – theorcp Apr 6 '16 at 12:29
  • 1
    $\begingroup$ 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$). $\endgroup$ – Ran G. Apr 6 '16 at 13:33
  • $\begingroup$ @RanG. yes I see ..How I can make it for P too $\endgroup$ – theorcp Apr 6 '16 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.