The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged recursiveandrecursivelyenumerablelanguages
+5
votes
1
answer
1
decidability
Consider the following languages L1={<M> there exists x,y belonging to (sigma*) such that either x belongs to L(M) or y does not belong to L(M)}. Answer Recursive, This is the language of all turing machines L2={<M1,M2> L(M1) < L(M2)} Answer Not even recursively enumerable. Arjun sir plzz explain these languages.
asked
Dec 27, 2016
in
Theory of Computation
by
sushmita

701
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
2
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??
asked
Dec 24, 2016
in
Theory of Computation
by
sushmita

177
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+1
vote
1
answer
3
Decidability
L1 = {<M> M is a turing machine that accepts all even numbers.} L2={<M,x> M is a Turing machine and x is a string and there exists a TM M1 such that x does not belong to L(M) and L(M1)} Can someone explain it informally/ intuitivelywithout the concrete proof??
asked
Dec 23, 2016
in
Theory of Computation
by
sushmita

135
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
4
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.
asked
Dec 22, 2016
in
Theory of Computation
by
firki

261
views
recursiveandrecursivelyenumerablelanguages
turingmachine
decidability
theoryofcomputation
0
votes
1
answer
5
Ace Test Series: Theory Of Computation  Recursive And Recursively Enumerable Languages
asked
Dec 17, 2016
in
Theory of Computation
by
Kai

233
views
acetestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
6
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/ricestheorem/ it says they are not recursive ..but are they R.E??
asked
Dec 16, 2016
in
Theory of Computation
by
Akriti sood

69
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
7
RE language
asked
Dec 16, 2016
in
Theory of Computation
by
vaishali jhalani

136
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
8
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}.
asked
Dec 15, 2016
in
Theory of Computation
by
vaishali jhalani

73
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
9
Decidability
asked
Dec 14, 2016
in
Theory of Computation
by
Rahul Jain25

331
views
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+20
votes
2
answers
10
GATE19903vi
Choose the correct alternatives (More than one may be correct). Recursive languages are: A proper superset of context free languages. Always recognizable by pushdown automata. Also called type $0$ languages. Recognizable by Turing machines.
asked
Nov 23, 2016
in
Theory of Computation
by
makhdoom ghaya

2.6k
views
gate1990
normal
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
11
TestBook Test Series: Theory Of Computation  Recursive and Recursively Enumerable Languages
asked
Nov 17, 2016
in
Theory of Computation
by
thor

103
views
testbooktestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
12
Ace Test Series: Theory Of Computation  Recursive And Recursively Enumerable Languages
asked
Nov 17, 2016
in
Theory of Computation
by
thor

322
views
acetestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
13
Doubt  TOC
State True/False A subset of recursive language can be recursive enumerable that is not recursive. P.S : I don't know the answer.. but it should be false according to me.. Kindly let me know if i am wrong with an example ..
asked
Nov 8, 2016
in
Theory of Computation
by
Gate Mission 1

219
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
0
answers
14
toc decidability
Which of the following statements regarding $L_1$ and $L_2$ is true? $L_1$ ={⟨M⟩ ∣ M has a state that is visited no more than 2017 times when started on an empty tape} $L_2$ ={⟨M⟩ ∣ M has a state that is visited at least 2017 times when ... L1 is decidable and L2 is undecidable. L1 is undecidable and L2 is decidable Both L1 and L2 are decidable. Both L1 and L2 are undecidable
asked
Oct 21, 2016
in
Theory of Computation
by
Amit puri

366
views
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
15
RECURSIVE & R.E.
Is L(M) context free language? Tell whether language is re or non re.
asked
Sep 11, 2016
in
Theory of Computation
by
Çșȇ ʛấẗẻ

108
views
recursiveandrecursivelyenumerablelanguages
+4
votes
2
answers
16
toc recuresively ennumerable
Let L be a regular language, and R be a turing recognizable language but not acceptable language. Which of the following is possible? a) Set of strings common in L and R' can be in not RE(where ' is a complement operation) b)Set of strings common in L and R' can be recursive. 1) only a 2)only b 3) both 4) none
asked
Aug 2, 2016
in
Theory of Computation
by
resilientknight

346
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+2
votes
2
answers
17
TocRecursively Ennumerable
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A. True or false.Cite with reasons.
asked
Aug 2, 2016
in
Theory of Computation
by
resilientknight

312
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+1
vote
2
answers
18
Relation between NP, recursive and recusive enumerable
I) Every language in NP is recursive. II)Every language in NP is recursively enumerable. Which of the statements is /are true? A. I only B. II only C. Both I and II D Neither I nor II
asked
Jul 13, 2016
in
Theory of Computation
by
sh!va

1k
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
–3
votes
1
answer
19
Toc Recursive and Recursive enumberable Language
asked
Jun 30, 2016
in
Theory of Computation
by
geet.m

512
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+5
votes
3
answers
20
ISRO201179
A problem whose language is recursion is called? Unified problem Boolean function Recursive problem Decidable
asked
Jun 24, 2016
in
Theory of Computation
by
jothee

2.4k
views
isro2011
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+37
votes
4
answers
21
GATE2016144
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard manyone ... recursively enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.
asked
Feb 12, 2016
in
Theory of Computation
by
Sandeep Singh

5.4k
views
gate20161
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+75
votes
6
answers
22
GATE2016244
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$, $L_{2} = \left\{\left\langle M \right\rangle \mid M \text { takes at least 2016 steps on all inputs} \right\}$ ... $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
asked
Feb 12, 2016
in
Theory of Computation
by
Akash Kanase

14.5k
views
gate20162
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
23
Complement of a recursive language
Given a TM M, complement of L(M) is contextfree. True/False?
asked
Jan 9, 2016
in
Theory of Computation
by
Arjun

1.6k
views
recursiveandrecursivelyenumerablelanguages
contextfreelanguages
+2
votes
1
answer
24
Turing Recognizable L
If $L$ is Turingrecongnizable. Then (A) $L$ and $\bar{L}$ must be decidable. (B) $L$ must be decidable but $\bar{L}$ need not be. (C) Either $L$ is decidable or $\bar{L}$ is not Turing recognizable. (D) None of above.
asked
Jan 4, 2016
in
Theory of Computation
by
bahirNaik

231
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
25
Two languages reducible to each other in polynomial time. Which is false option for them?
asked
Jan 4, 2016
in
Theory of Computation
by
Utk

219
views
recursiveandrecursivelyenumerablelanguages
normal
compoundautomata
+2
votes
1
answer
26
Please explain?
Consider the following Languages: $L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$ $L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$ where $\langle M \rangle$ denotes encoding of a Turing Machine $M$ Then which of the following is true? (a) $L_{ne}$ is r.e. but not ... .e. (b) Both are not r.e. (c) Both are recursive (d) $L_{e}$ is r.e. but not recursive and $L_{ne}$ is not r.e.
asked
Dec 15, 2015
in
Theory of Computation
by
Rajat Sharma 1

502
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
ricetheorem
+4
votes
1
answer
27
turing machine plzz xplain
Let $A=\{\langle M\rangle \mid M$ is turing machine that halts on all inputs and $L(M)=L'$ for some undecidable language $L'\}$. Then $A$ is ____ a. Regular language b. Recursive language but not regular c. Recursively enumerable language but not recursive language d. Nonrecursively enumerable language
asked
Dec 6, 2015
in
Theory of Computation
by
Jay Singh

358
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+21
votes
2
answers
28
TIFR2012B19
Which of the following statements is TRUE? Every turning machine recognizable language is recursive. The complement of every recursively enumerable language is recursively enumerable. The complement of a recursive language is recursively enumerable. The complement of a ... contextfree. The set of turning machines which do not halt on empty input forms a recursively enumerable set.
asked
Nov 3, 2015
in
Theory of Computation
by
makhdoom ghaya

940
views
tifr2012
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+4
votes
1
answer
29
Which of the folowing are R.E
Which of the following problem(s) is/are Recursively enumerable or its complement is recursively enumerable? I. The language of all Turing machines that accept nothing. II. The language of all Turing machines that accept everything. III. The language of all CFG’s that are ambiguous.
asked
Oct 17, 2015
in
Theory of Computation
by
Mari Ganesh Kumar

899
views
turingmachine
recursiveandrecursivelyenumerablelanguages
+15
votes
1
answer
30
TIFR2010B40
Which of the following statement is FALSE? All recursive sets are recursively enumerable. The complement of every recursively enumerable sets is recursively enumerable. Every Nonempty recursively enumerable set is the range of some totally recursive function. All finite sets are recursive. The complement of every recursive set is recursive.
asked
Oct 11, 2015
in
Theory of Computation
by
makhdoom ghaya

993
views
tifr2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
Page:
« prev
1
2
3
4
5
6
7
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IISc CDS Interview Experience, 2020
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
PGEE 2020 (CSE) Experience
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.3k)
Digital Logic
(2.9k)
Programming and DS
(5k)
Algorithms
(4.4k)
Theory of Computation
(6.2k)
Compiler Design
(2.2k)
Operating System
(4.6k)
Databases
(4.2k)
CO and Architecture
(3.4k)
Computer Networks
(4.2k)
Non GATE
(1.2k)
Others
(1.5k)
Admissions
(595)
Exam Queries
(562)
Tier 1 Placement Questions
(23)
Job Queries
(71)
Projects
(19)
Unknown Category
(1k)
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
Thank brother !! Bookmarked it :)
Check out goxul.github.io, it has all the...
congratulation brother ! Can you please tell me...
I got selected for this, in case someone lands up...
After the written exam and at the time of...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,375
questions
60,586
answers
202,005
comments
95,409
users