1

Let $G$ be an unrestricted grammar. Then the problem of determining whether or not $L(G) = ∅$ is undecidable. Let $M_1$ and $M_2$ be two arbitrary Turing machines. Show that the problem $L(M_1) ⊆ L(M_2)$

This is a potential question for the exam and I have no clue how to solve it. Any help would be really appreciated.

BlackAdder
  • 4,029
  • 1
    Please do not vandalize your question upon receiving an answer. I have rolled back the edit. –  Dec 02 '13 at 04:02

1 Answers1

2

HINT: Use $M_1$ and $M_2$ to construct a Turing machine $M$ such that $L(M)=L(M_1)\setminus L(M_2)$. Construct a grammar $G$ such that $L(G)=L(M)$. Then ... ?

Brian M. Scott
  • 616,228
  • I'm not sure what that means. please provide a direct answer it could help more than the hint. thank you –  Dec 02 '13 at 03:05
  • What part of it is unclear? Is there some notation there that you don’t understand? – Brian M. Scott Dec 02 '13 at 03:08
  • L(M)=L(M1)∖L(M2) but I don't know what to do for the "Construct a grammar G such that L(G)=L(M). Then ... ?" –  Dec 02 '13 at 03:16
  • @Mike: For any sets $A$ and $B$, $A\setminus B$ is just the set of things that are in $A$ but not in $B$. Thus, $L(M_1)\setminus L(M_2)$ is the set of words that are in the language of $M_1$ but not in the language of $M_2$. This is $\varnothing$ if and only if $L(M_1)\subseteq L(M_2)$, so the problem of determining whether $L(M_1)\subseteq L(M_2)$ is equivalent to the problem of determining whether $L(G)=\varnothing$; this is the point that I was hoping that you’d see. As for the rest, if this is a reasonable question for your exam, I’d expect you already to know that there are effective ... – Brian M. Scott Dec 02 '13 at 03:23
  • ... procedures for converting a Turing machine into an equivalent grammar and vice versa. You might have been expected to take that on faith, I suppose, instead of being shown a proof, but I don’t at the moment see any way to do the problem without making use of that fact. – Brian M. Scott Dec 02 '13 at 03:24
  • oh I think I kinda see how to argue for this question but I'm not sure on how to express/produce a formal answer to show the problem L(M1) ⊆ L(M2) is undecidable ? –  Dec 02 '13 at 03:31
  • @Mike: That would depend entirely on the level of detail/rigor required. If you actually had to explain how to produce $G$ from $M$, the proof would be long and involved; if you can simply use the fact that such a construction exists, then that step is less than a line. The same goes for the first step, getting $M$ from $M_1$ and $M_2$; the idea, of course, is just to have $M$ simulate running $M_1$ and $M_2$ in parallel on the same input and accepting the input if $M_1$ does and $M_2$ does not. The details, however, would be messy. I can’t help here, because it depends on the course. – Brian M. Scott Dec 02 '13 at 03:36
  • alright, I like to thank you very much for your efforts :) –  Dec 02 '13 at 03:38
  • @Mike: You’re very welcome. – Brian M. Scott Dec 02 '13 at 03:40