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$
1
  • $\begingroup$ Its the same proof as for regular languages. Check that out first (under "closure properties of regular languages") $\endgroup$
    – nir shahar
    Commented Jul 4, 2020 at 21:23

1 Answer 1

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.
$\endgroup$
1
  • 1
    $\begingroup$ @Evil, thank you! I fixed the symbol. $\endgroup$
    – Steven
    Commented Aug 5, 2020 at 22:50

Your Answer

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

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