5
$\begingroup$

I am really struggling with determining the decidability of languages and cant figure out whether this problem is decidable or not.

I have a language

$\qquad\displaystyle L = \{ (R(M_1), R(M_2)) \mid L(M_1) \cap L(M_2) = \emptyset \}$,

where $R(M_1)$ and $R(M_2)$ are representations of Turing machines $M_1$, resp $M_2$ and $L(M_1)$, $L(M_2)$ are the languages accepted by these machines.

Is language $L$ a decidable language?

I have found this theorem: It is undecidable whether or not the languages generated by two given context-free grammars have an empty intersection. (but I dont know whether $L(M_1)$ and $L(M_2)$ are context-free, I only know that they are accepted by some machines, so I dont know if I can use this theorem).

I think that this problem is undecidable and my attempt to prove this would go like this:

In order for this language to be decidable. I would have to build a Turing machine that tests whether an arbitrary word is accepted by $M_1$ and not $M_2$ (and vice versa) but I cannot guarantee that it will halt for all inputs (since language acceptence does not guarantee that the language is decidable) so it proves the undecidability.

Is this correct approach?

Is $L$ at least recursively enumarable?

$\endgroup$
  • $\begingroup$ think about it like this. look at the chomsky hierarchy. if a language is CFL its also RE. so the CFL theorem applies. just choose CFL languages to show it applies. $\endgroup$ – vzn Nov 26 '15 at 20:35
7
$\begingroup$

It is undecidable whether a Turing machine accepts any input at all (reduction from the halting problem). So, take a machine $M_1$ that accepts all inputs. $L(M_1)\cap L(M_2) = L(M_2)$ so non-emptiness is undecidable.

The intersection of two RE sets is RE. This is a standard fact: simulate the accepting machines in parallel and accept iff they both accept.

$\endgroup$
  • $\begingroup$ Thank you, I understand it now... And I suppose that the assumption that L is not r.e. (I cannot enumarate all representations of TM with empty intersection) and complement L is r.e. (I can enumerate outputs of both TMs and halt when I find a common word in both languages). Is this assumption right? $\endgroup$ – Smajl Sep 17 '14 at 12:45
  • $\begingroup$ @Smajl Yes, that seems to be correct. $\endgroup$ – David Richerby Sep 17 '14 at 12:58
  • 1
    $\begingroup$ It is not even necessary to find a machine $M_1$ that accepts all words, as $L(M)\cap L(M) = L(M)$. $\endgroup$ – Hendrik Jan Nov 29 '15 at 12:05
3
$\begingroup$

Your approach does not give you a formal proof: There could be other ways to decide membership for $L$ than testing for membership in $L(M_1)$ and $L(M_2)$ separately.

You can prove this by reduction instead: Assume you had a TM that decides $L$ and use this TM plus some pre- and/or postprocessing to decide a problem that you know is undecidable. (The intersection of context-free languages is a good candidate here.)

Also the complement of $L$ is recursively enumerable, so $L$ is not (as that would imply decidability).

$\endgroup$
  • $\begingroup$ Thansk for the answer. Could you sketch the beginning of the reduction? I suppose I have to input the $R(M_1), R(M_2)$ to some pre-processing TM and output two languages that are generated by context free grammar. But I am not sure how to do that (and whether it is even possible!). $\endgroup$ – Smajl Sep 17 '14 at 10:50
  • $\begingroup$ You are given two context-free grammars and want to use a decider for $L$ to decide, if their intersection is empty. How do you do this? $\endgroup$ – FrankW Sep 17 '14 at 10:53
  • $\begingroup$ But initially, I am just given two representations of TM that accept some languages. I cannot guarantee that they are context free. $\endgroup$ – Smajl Sep 17 '14 at 10:56
  • $\begingroup$ en.wikipedia.org/wiki/Reduction_%28complexity%29 $\endgroup$ – FrankW Sep 17 '14 at 11:00
  • $\begingroup$ What you described in your previous comment is basically the empty intersection problem for context-free languages. I understand it and I found the proof of its undecidability. What I do not understand is how to convert an arbitray language from TM representation to a context free language... $\endgroup$ – Smajl Sep 17 '14 at 11:04
2
$\begingroup$

If $G$ is a context-free grammar, there exists a turing machine whose language is the language generated by $G$. Let two context-free grammars $G_1$ and $G_2$ be given, and let $M_1$ and $M_2$ be Turing machines accepting the languages of $G_1$ and $G_2$, respectively.

A decider for your $L$ would in particular decide whether $L(M_1) ∩ L(M_2) = ∅$, which is impossible according to the theorem you quoted.

$\endgroup$
-3
$\begingroup$

We can reduce this problem to the decision of an empty language by a turing machine (Etm), as previous posted. In this case I think that the problem can be more easily solved if we use the Etm Decider as a post-processing.

First, we know that L(M1) $\cap$ L(M2) = L(M1) if L(M1) $\subseteq$ L(M2). So we construct a decider that tests if L(M1) $\cap$ L(M2) = L(M1). If the answer is no, we reject. If it is yes, we test if L(M1) $\neq$ $\emptyset$. If yes, we accept. If no, we reject.

It is a contradicition, since Etm is undecidable.

Is this approach correct to this problem?

$\endgroup$
  • $\begingroup$ Reducing this problem to some undecidable problem proves nothing. For example, every decidable problem reduces to the halting problem. "We know that L(M1) ∩ L(M2) = L(M1)" -- that's certainly not true in general. $\endgroup$ – David Richerby Nov 26 '15 at 21:14
  • $\begingroup$ Please don't use the answer box to request feedback or to post candidate answers and ask us to check whether they are correct. You should only post answers that you are confident in. $\endgroup$ – D.W. Nov 26 '15 at 21:28
  • $\begingroup$ @DavidRicherby In Sipser's book this is the usual manner that he uses to proves undecidable problems. $\endgroup$ – Jas Nov 26 '15 at 22:26
  • $\begingroup$ @D.W. Sorry, but there are a lot of problems about Turing Machines that uses different approaches, it confuses me and not allow non-experts to be confident about his choices. $\endgroup$ – Jas Nov 26 '15 at 22:32
  • $\begingroup$ @Jas You have the reduction the wrong way around. To prove that a language L is undecidable, you need to reduce a known undecidable langauge to L, not reduce L to the known undecidable language. $\endgroup$ – David Richerby Nov 27 '15 at 8:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.