Given an arbitrary w:
P = {L|L is in RE, {w}=L}
Il Lp in RE?
I've tried making a TM for Lp, but I would have to prove that w is the ONLY string in L, which means rejecting every string that isn't w, which is impossible.
Then I thought of working with notP = {L | L is in RE, {w}!=L} and tried to rewrite it to understand better what I have to check to accept:
P={L | L is in RE, w is not in L OR (w is in L, with |L|>1)} but still couldn't find a TM for it since Lp' is not in RE (P'={L | L is in RE, w is not in L}).
At this point, I think I'd need a reduction, but I can't think of a language to use.
Any suggestions?
In reply to MATTEO ZANELLA
Re: Set of languages that are not {w} being RE
I'm not sure of the solution but that's what I would do (Pdf in attachment)
In reply to ANTONINO ANDREA CARE'
Re: Set of languages that are not {w} being RE
by MATTEO ZANELLA -
Consider though an input enc(M) s.t. L(M) is the empty language, enc(M) is in LnotP since L(M)!={w}.
If I pass enc(M) into your TM, no string would accept, hence enc(M) isn't accepted even if it should've.
If I pass enc(M) into your TM, no string would accept, hence enc(M) isn't accepted even if it should've.
In reply to MATTEO ZANELLA
Re: Set of languages that are not {w} being RE
ok, you're right, I hadn't thought about this case. I need to think about it, but probably the exercise has to be faced with a different approach.
This exercise must be from something like two years ago, right? This year you do not have the knowledge to solve it, forget about this exercise.