What would be the general approach for that? And what are the things that generally overlooked while proving such things?

For example,

I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a where a$\in \sum^{*}$}?

Is it possible,
1. To prove its not a CE, Can we reduce $(Acceptance\space problem)^{complement}$ to L?
2. To prove its not a Co-CE, Can we reduce Acceptance problem to L?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.