For each of the above languages, we have stated that they aren't in R. Are they in Re? coRe?
I have them as:
Will of course be glad to be corrected if I'm wrong.
from rice we get that CFLtm and REGtm aren't in RE .
reduction from Htm (so it isn't in coRE):
<M,w> -> <M'>
M' given x: run M on w for |x| steps. if stopped naturally, accept. else check if x is of the form <M1,w1> and run M1 on w1.
<M,w> e Htm ==> L(M') = sigma* \ A , s.t. A is finite , so L(M') is Regular ( L(M')^c is regular and regular lang. is closed under complement )
<M,w> !e Htm ==> L(M') = Htm
this reduction is good to both CFLtm , REGtm
ALLCFG in coRE/R cause in lecture 9 slide 52 we've shown reduction from complement of ATM, which in coRE and thus ALLCFG also in coRE.
Notice that the only thing we can conclude from this reduction is the ALL-CFG is not in R and not in RE (since the complement of A-TM is not in R and not in RE).
But we can't say that since the complement of A-TM is in coRE that ALL-CFG is also in coRE.
We need to show a machine that accepts the complement of ALL-CFG and then we will know that ALL-CFG is in coRE\R.
And that machine was showed by hila above.
is ALL-DFA's status the same? of course it is in coRE just as ALLCFG. But what reduction can we do to prove that it isn't R? We can't do a reduction as the ALLCFG