6
$\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?

Improve this question
$\endgroup$
1
  • $\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, 2015 at 20:35

4 Answers 4

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\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, 2014 at 12:45
  • $\begingroup$ @Smajl Yes, that seems to be correct. $\endgroup$
    – David Richerby
    Sep 17, 2014 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, 2015 at 12:05
  • $\begingroup$ I understand that $L(M_1) \cap L(M_2) = L(M_2)$ but why does this make non-emptiness undecidable? I tried reading the other answers also to see if I'm missing anything obvious here $\endgroup$
    – sprajagopal
    Jan 13, 2021 at 15:20
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).

Improve this answer
$\endgroup$
6
  • $\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, 2014 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, 2014 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, 2014 at 10:56
  • $\begingroup$ en.wikipedia.org/wiki/Reduction_%28complexity%29 $\endgroup$
    – FrankW
    Sep 17, 2014 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, 2014 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.

Improve this answer
$\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?

Improve this answer
$\endgroup$
6
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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