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
+2
votes
1
answer
1
is the set of recursively enumerable languages countable?
asked
Jul 15, 2015
in
Theory of Computation
by
Shubham Sahu
(
111
points)

1.7k
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+21
votes
1
answer
2
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
Boss
(
30.1k
points)

2.1k
views
gate20151
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
+19
votes
1
answer
3
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
Boss
(
13.5k
points)

1.5k
views
turingmachine
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
+7
votes
3
answers
4
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 15, 2014
in
Theory of Computation
by
Manu Thakur
Boss
(
43.7k
points)

1.6k
views
theoryofcomputation
difficult
recursiveandrecursivelyenumerablelanguages
decidability
+37
votes
1
answer
5
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
Veteran
(
105k
points)

4k
views
gate2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
normal
+37
votes
4
answers
6
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
Veteran
(
105k
points)

4.5k
views
gate20142
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
+22
votes
2
answers
7
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
Veteran
(
105k
points)

2.2k
views
gate20141
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+18
votes
2
answers
8
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 22, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

1.5k
views
gate2005
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
easy
+30
votes
3
answers
9
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 16, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

2.8k
views
gate2003
theoryofcomputation
normal
recursiveandrecursivelyenumerablelanguages
+15
votes
3
answers
10
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
Veteran
(
52.2k
points)

2.1k
views
gate2008
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
+19
votes
4
answers
11
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
Veteran
(
52.2k
points)

3.7k
views
gate2008
theoryofcomputation
easy
isro2016
recursiveandrecursivelyenumerablelanguages
+34
votes
4
answers
12
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
(
77
points)

5.1k
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
REGARDING ISRO TEST SERIES BY MADEESASY
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
@mohan123 Do you have all standard book...
bro can be upload all standard book questions in...
it'll take 34 days but for most purpose you can...
50,647
questions
56,459
answers
195,376
comments
100,266
users