325 views
0 votes
0 votes
can we say languages which are not R.E as undecidable but partially decidable??

example:

sigma={0,1] and L={<M>| M is a TM that accepts a string of length 2014 } a/c to rice theoram it should be non R.E (Tyes is subset of Tno)but answer is

"Undecidable but partially decidable"

same for the state entry problem

L= {<M> | L is regular?} etc

I know all are undecidable but how they are partially decidable if they are not even R.E

1 Answer

0 votes
0 votes
No..We cannot say that.

Not Re--> undecidable,not even semidecidable.

Re--> Semidecidable.

 

And how are u saying Tyes is a subset of Tno.?Please tell what u assumed there.

Related questions

1 votes
1 votes
1 answer
1
shreshtha5 asked Jul 11, 2015
641 views
let q0 and q1 are two states and q0 is always initial state over the alphabet {a,b}, the possible number of dfa's with two states q0 and q1 are16,32,64,80
0 votes
0 votes
1 answer
2
shreshtha5 asked Jun 17, 2015
658 views
2 votes
2 votes
3 answers
3
shreshtha5 asked Apr 26, 2015
2,814 views
the minimum number of states in the PDA accepting the language$L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$a) 2b) 3c) 4d) 5
0 votes
0 votes
2 answers
4
Hcas Hgnis asked Dec 7, 2014
298 views