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
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

441
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
+6
votes
4
answers
2
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

933
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
3
is the set of recursively enumerable languages countable?
asked
Jul 15, 2015
in
Theory of Computation
by
Shubham Sahu

2k
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+26
votes
1
answer
4
GATE201513
For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is contextfree and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? $\bar{L}_{1}$ ( Compliment of $L_{1}$) is recursive $\bar{L}_{2}$ ... $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable I only III only III and IV only I and IV only
asked
Feb 11, 2015
in
Theory of Computation
by
makhdoom ghaya

2.6k
views
gate20151
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
+20
votes
1
answer
5
Which of the following languages are Recursively Enumerable language?
Which of the following languages are Recursively Enumerable language? $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ ... $\{ \langle M1, M2, M3 \rangle \mid L(M1) = L(M2) \cup L(M3) \}$ All of these
asked
Jan 27, 2015
in
Theory of Computation
by
Vikrant Singh

1.9k
views
turingmachine
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+7
votes
3
answers
6
Given Language is REC or Non RE
Which of the following is true for the given language? $L=$ {<TM>  TM halts on every input} <TM> is encoding of the Turing machine (A) $L$ is Recursive and $\overline{L}$ is also Recursive (B) $L$ is Recursive ... Enumerable and $\overline{L}$ is Recursive Enumerable (D) $L$ is Non Recursive Enumerable and $\overline{L}$ is Non Recursive Enumerable
asked
Nov 16, 2014
in
Theory of Computation
by
Manu Thakur

1.7k
views
theoryofcomputation
difficult
recursiveandrecursivelyenumerablelanguages
decidability
+44
votes
1
answer
7
GATE201017
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2  L_1 \:\text{is recursively enumerable.}$ $L_1  L_3 \:\text{is recursively enumerable.}$ $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
asked
Sep 29, 2014
in
Theory of Computation
by
jothee

5.2k
views
gate2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
normal
+43
votes
4
answers
8
GATE2014216
Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as manytoone reducible) to language $B$. Which one of the following is FALSE? If $A\: \leq_m B$ and $B$ is recursive then $A$ is recursive. If $A\: \leq_m B$ ... enumerable then $A$ is recursively enumerable. If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.
asked
Sep 28, 2014
in
Theory of Computation
by
jothee

5.6k
views
gate20142
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
+26
votes
2
answers
9
GATE2014135
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.
asked
Sep 26, 2014
in
Theory of Computation
by
jothee

2.8k
views
gate20141
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+21
votes
2
answers
10
GATE200556
Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE? $L_1$' is recursive and $L_2$' is recursively enumerable $L_1$' is recursive and $L_2$' is not recursively enumerable $L_1$' and $L_2$' are recursively enumerable $L_1$' is recursively enumerable and $L_2$' is recursive
asked
Sep 23, 2014
in
Theory of Computation
by
Kathleen

1.8k
views
gate2005
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
easy
+32
votes
3
answers
11
GATE200313
Nobody knows yet if $P=NP$. Consider the language $L$ defined as follows.$L = \begin{cases} (0+1)^* & \text{ if } P = NP \\ \phi & otherwise \end{cases} $Which of the following statements is true? $L$ is recursive $L$ is ... enumerable but not recursive $L$ is not recursively enumerable Whether $L$ is recursively enumerable or not will be known after we find out if $P=NP$
asked
Sep 17, 2014
in
Theory of Computation
by
Kathleen

3.6k
views
gate2003
theoryofcomputation
normal
recursiveandrecursivelyenumerablelanguages
+17
votes
3
answers
12
GATE200848
Which of the following statements is false? Every NFA can be converted to an equivalent DFA Every nondeterministic Turing machine can be converted to an equivalent deterministic Turing machine Every regular language is also a contextfree language Every subset of a recursively enumerable set is recursive
asked
Sep 12, 2014
in
Theory of Computation
by
Kathleen

2.7k
views
gate2008
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+22
votes
4
answers
13
GATE200813, ISRO201636
If $L$ and $\bar L$ are recursively enumerable then $L$ is regular contextfree contextsensitive recursive
asked
Sep 12, 2014
in
Theory of Computation
by
Kathleen

4.6k
views
gate2008
theoryofcomputation
easy
isro2016
recursiveandrecursivelyenumerablelanguages
+39
votes
4
answers
14
GATE200315
If the strings of a language $L$ can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true? $L$ is necessarily finite $L$ is regular but not necessarily finite $L$ is context free but not necessarily regular $L$ is recursive but not necessarily contextfree
asked
Aug 24, 2014
in
Theory of Computation
by
gauravsachan9188

6.3k
views
theoryofcomputation
gate2003
normal
recursiveandrecursivelyenumerablelanguages
Page:
« prev
1
2
3
4
5
6
7
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
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
IIT Tirupati MS Interview 2020
IIT Bombay Mtech RA  interview experience (2020)
Subjects
All categories
General Aptitude
(2k)
Engineering Mathematics
(8.2k)
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
After getting so many mails from you...
Refund will be given for such cases if applied...
@sreejit007 they don't publish any cutoff or...
@ranjanabhi Can you please elaborate what did...
ISI 2019 : Aarushi Aiyyar's answer to How do...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,315
questions
60,434
answers
201,780
comments
95,261
users