Register

Recent questions tagged recursive-and-recursively-enumerable-languages

2 votes
4 answers
181
Recursive languages.
If L1 is Recursive language and L2 is RE. Then L1 ⋂ L2 is RE? Since every Recursive language is RE, then how intersection of the Recursive and RE is RE?
If L1 is Recursive language and L2 is RE. Then L1 ⋂ L2 is RE? Since every Recursive language is RE, then how intersection of the Recursive and RE is RE?
User Avatar
0 votes
0 answers
182
theory of computation
L = { <M> / M is a Turing machine and M accepts a regular language }. This Language L is recursively enumerable but not recursive. ...right ??
L = { <M / M is a Turing machine and M accepts a regular language }.This Language L is recursively enumerable but not recursive. ...right ??
User Avatar
0 votes
1 answer
184
theory of computation
This language, L = { <M,w> / M is a TM,w is a string and M does not halt on string w } is not recursively enumerable ...right ???
This language,L = { <M,w / M is a TM,w is a string and M does not halt on string w }is not recursively enumerable ...right ???
User Avatar
1 votes
2 answers
186
decidability
is intersection of two context sensitive decidable?? I think since they are closed under intersection, it must be decidable. please answer
is intersection of two context sensitive decidable??I think since they are closed under intersection, it must be decidable.please answer
User Avatar
0 votes
0 answers
202
decidability doubt
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems??
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems...
User Avatar
3 votes
1 answer
204
doubt
Which of the following is RE / NOT RE ? I.<M>|M is a TM that accepts all even numbers. II.<M>|M is a TM that does not accept all even numbers. II.<M>|M is a TM rejects all even numbers.
Which of the following is RE / NOT RE ?I.<M>|M is a TM that accepts all even numbers.II.<M>|M is a TM that does not accept all even numbers.II.<M>|M is a TM rejects all e...
User Avatar
1 votes
0 answers
206
recursive enumerable or not??
L(M) has at least 10 strings L(M) has at least 10 strings these two languages i have taken from this link http://gatecse.in/rices-theorem/ it says they are not recursive ..but are they R.E??
L(M) has at least 10 stringsL(M) has at least 10 stringsthese two languages i have taken from this link http://gatecse.in/rices-theorem/it says they are not recursive ..b...
User Avatar
1 votes
1 answer
208
recursive or recursively enummerable
State whether these languages are recursive ,RE, non RE? L1 = {<M>| M is a TM and |L(M)| ≤ 3}. L2 = {<M>|M is a TM and |L(M)| ≥ 3}.
State whether these languages are recursive ,RE, non RE?L1 = {<M>| M is a TM and |L(M)| ≤ 3}.L2 = {<M>|M is a TM and |L(M)| ≥ 3}.
User Avatar
Page: