Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

migrated from Jan 30 '12 at 21:35

This question came from our site for professional and enthusiast programmers.

Both statements are wrong. True is this: If L is acceptable but not decidable, then L' is not acceptable. – Raphael Jan 29 '12 at 15:26

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.