The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
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
+1
vote
1
answer
1
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
Boss
(
17.3k
points)

122
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
2
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
(
53
points)

239
views
recursiveandrecursivelyenumerablelanguages
turingmachine
decidability
theoryofcomputation
0
votes
1
answer
3
Ace Test Series: Theory Of Computation  Recursive And Recursively Enumerable Languages
asked
Dec 16, 2016
in
Theory of Computation
by
Kai
Active
(
2.6k
points)

191
views
acetestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
4
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
Boss
(
12.2k
points)

63
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
5
RE language
asked
Dec 16, 2016
in
Theory of Computation
by
vaishali jhalani
Active
(
4.7k
points)

103
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
6
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
Active
(
4.7k
points)

59
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
7
Decidability
asked
Dec 14, 2016
in
Theory of Computation
by
Rahul Jain25
Boss
(
11.1k
points)

308
views
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+18
votes
2
answers
8
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 22, 2016
in
Theory of Computation
by
makhdoom ghaya
Boss
(
30.2k
points)

1.8k
views
gate1990
normal
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
9
TestBook Test Series: Theory Of Computation  Recursive and Recursively Enumerable Languages
asked
Nov 17, 2016
in
Theory of Computation
by
thor
Loyal
(
6.8k
points)

91
views
testbooktestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
10
Ace Test Series: Theory Of Computation  Recursive And Recursively Enumerable Languages
asked
Nov 17, 2016
in
Theory of Computation
by
thor
Loyal
(
6.8k
points)

281
views
acetestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
11
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 7, 2016
in
Theory of Computation
by
Gate Mission 1
Active
(
4.1k
points)

206
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
12
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
Active
(
2.4k
points)

308
views
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
13
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
Çșȇ ʛấẗẻ
Active
(
1.8k
points)

91
views
recursiveandrecursivelyenumerablelanguages
+4
votes
2
answers
14
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
Active
(
2.1k
points)

314
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+2
votes
2
answers
15
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
Active
(
2.1k
points)

273
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+1
vote
2
answers
16
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
Boss
(
32.5k
points)

871
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
–3
votes
1
answer
17
Toc Recursive and Recursive enumberable Language
asked
Jun 29, 2016
in
Theory of Computation
by
geet.m
(
105
points)

424
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+5
votes
3
answers
18
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
Veteran
(
105k
points)

2.2k
views
isro2011
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+34
votes
3
answers
19
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
Loyal
(
7.2k
points)

4.6k
views
gate20161
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+65
votes
5
answers
20
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
Boss
(
41.6k
points)

11.2k
views
gate20162
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
21
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
Veteran
(
425k
points)

988
views
recursiveandrecursivelyenumerablelanguages
contextfreelanguage
+2
votes
1
answer
22
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
Active
(
3k
points)

184
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
23
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
Active
(
2k
points)

192
views
recursiveandrecursivelyenumerablelanguages
normal
compoundautomata
+2
votes
1
answer
24
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
Junior
(
541
points)

364
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
ricetheorem
+4
votes
1
answer
25
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
(
179
points)

332
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+20
votes
2
answers
26
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 2, 2015
in
Theory of Computation
by
makhdoom ghaya
Boss
(
30.2k
points)

764
views
tifr2012
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+4
votes
1
answer
27
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
Active
(
2k
points)

806
views
turingmachine
recursiveandrecursivelyenumerablelanguages
+12
votes
1
answer
28
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
Boss
(
30.2k
points)

867
views
tifr2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+5
votes
1
answer
29
Which of the following is not a recursive Language? Please explain the reason for each
asked
Sep 11, 2015
in
Theory of Computation
by
Shefali
Junior
(
867
points)

409
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
+6
votes
4
answers
30
Let A and B be disjoint, R.E. languages. Let A' U B' also be recursive enumerable. What can you say about A and B?
asked
Aug 19, 2015
in
Theory of Computation
by
ari
(
95
points)

787
views
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
Really helpful sir Thanks a ton👍👍
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
50,644
questions
56,523
answers
195,602
comments
101,282
users