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.
If L is decidable and acceptable, is L' (complementary language) not-acceptable?
1
$\begingroup$
computer-science
-
1Both statements are wrong. True is this: If L is acceptable but not decidable, then L' is not acceptable. – 2012-01-29
1 Answers
2
Your initial statement
if L is decidable and L' is acceptable, then L is not-acceptable
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
if L is decidable and acceptable, then L' is not-acceptable
Is also incorrect, because if L is decidable, so is L'. Consequently, L' is acceptable as well.