0
$\begingroup$

Is L = $\{\langle M,w\rangle \mid \text{$M$ accepts string epsilon or string $w$, or both} \}$ decidable?

I attempted to use Rice's Theorem for this question to prove that it is undecidable.

Is my approach in the right direction if I let S, the non-trivial subset of recognizable languages, in this case to be S = {L | $\epsilon$ $\in$ L or $w$ $\in$ L and when both $\in$ L}?

$\endgroup$
3
  • $\begingroup$ Have you tried using Rice's theorem to prove this? $\endgroup$ Apr 19 '18 at 7:27
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Apr 19 '18 at 9:04
  • $\begingroup$ I specified my approach further. $\endgroup$
    – kitkat
    Apr 19 '18 at 11:08