1
$\begingroup$

We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$.

We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don't have much more information than this. Anything to get started would be appreciated.

$\endgroup$
  • $\begingroup$ Its the same proof as for regular languages. Check that out first (under "closure properties of regular languages") $\endgroup$ – nir shahar Jul 4 at 21:23
2
$\begingroup$

What you ask might not be possible in general. If $L(T)$ denotes the set of words $x$ for which $T(x)$ accepts, and you do not have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, then you could choose:

  • $M$ as a Turing machine that takes another Turing machine $T$ as input and accepts if and only if $T$ halts on empty input. (Notice that such a Turing Machine $M$ exists).
  • $M'$ as a Turing Machines that recognizes $\Sigma^*$.

Then, there is no Turing Machine $T$ that recognizes $L(M) \cap L(M') = L(M)$ since $T$ would solve the halting problem.

On the other hand, if you are fine with a Turing machine that accepts $L(M) \cap L(M')$ or if you have the additional assumption that $M$ and $M'$ recognize $L(M)$ and $L(M')$, respectively, your problem is solved by a Turing machine that, on input $x$, operates as follows:

  • Simulate $M(x)$ until it halts (possibly never).
  • If $M(x)$ rejects, reject.
  • Simulate $M'(x)$ until it halts (possibly never).
  • If $M'(x)$ rejects, reject.
  • Accept.
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @Evil, thank you! I fixed the symbol. $\endgroup$ – Steven Aug 5 at 22:50

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.