0
$\begingroup$

I have two languages that I am trying to prove are recognizable or not:

Let $$L_1 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and doesn't accept $\varepsilon$}\}$$ where TM is short for "Turing Machine", $w$ is a string, and $ε$ is the empty string.

Is $L_1$ recognizable? Prove your answer is correct.

Let $$L_2 = \{(\langle M\rangle, w) \mid \text{$M$ is a TM that accepts $w$ and rejects $\varepsilon$} \}$$ Is $L_2$ recognizable? Prove your answer is correct.

I've been having trouble with these proofs using mapping reducibility. I know that the language $$A_\mathrm{TM} = \{\langle M, w \rangle \mid \text{$M$ is a Turing machine that accepts the string $w$}\}$$ is undecidable but recognizable. My approach is to say that $$L = \{\langle M, \varepsilon\rangle \mid \text{$M$ is a Turing machine that rejects $\varepsilon$} \}$$ is recognizable and, knowing that recognizable languages are closed under intersection, this shows $L$ is also recognizable.

I'm not too sure about the first question, however. Is there a better approach to proving these two languages are recognizable or not?

$\endgroup$
  • $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Mar 26 '16 at 10:43
  • 2
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Mar 26 '16 at 10:43
  • $\begingroup$ Deleting your question after receiving answers is bad style. Don't do that! $\endgroup$ – Raphael Mar 27 '16 at 18:26

Your Answer

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

Browse other questions tagged or ask your own question.