I know that if L is decidable and L' is acceptable, than L is not-acceptable. Is it also true to say that if L is decidable and acceptable, than L' is not-acceptable? I'm sorry if this question sounds dumb, but I have a test on these stuff in 2 days and I just wanna be 100% sure.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
migrated from stackoverflow.com Jan 30 '12 at 21:35
This question came from our site for professional and enthusiast programmers.
Your initial statement
Is incorrect. If L is decidable, then L' is also decidable, because the decidable languages are closed under complement. Since every decidable language is also acceptable, the above statement is incorrect.
Consequently, the statement
Is also incorrect, because if L is decidable, so is L'. Consequently, L' is acceptable as well.