Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Year
Exams
Recent questions tagged recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
Theory Of Computation, Decidability, Rice's Theorem
asked
5 days
ago
in
Theory of Computation
by
pranavsettaluri9
(
8
points)

9
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
#ricestheorem
0
votes
0
answers
GATE2016244 Video Solution
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\}$ ... are not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
asked
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

5
views
gate20162
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE200315 Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

4
views
theoryofcomputation
gate2003
normal
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE2014216 Video Solution
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$ ... then $A$ is recursively enumerable. If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.
asked
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20142
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
videosolution
0
votes
0
answers
GATE2016144 Video Solution
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 ... enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.
asked
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

3
views
gate20161
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE201017 Video Solution
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_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
asked
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

3
views
gate2010
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
normal
videosolution
0
votes
0
answers
GATE200813, ISRO201636 Video Solution
If $L$ and $\bar L$ are recursively enumerable then $L$ is regular contextfree contextsensitive recursive
asked
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2008
theoryofcomputation
easy
isro2016
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE200313 Video Solution
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 ... 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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

5
views
gate2003
theoryofcomputation
normal
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE2014135 Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate20141
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE201513 Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

4
views
gate20151
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
normal
videosolution
0
votes
0
answers
GATE200848 Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2008
theoryofcomputation
easy
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE19903vi Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

4
views
gate1990
normal
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
videosolution
0
votes
0
answers
GATE200556 Video Solution
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
Apr 18
in
Theory of Computation
by
admin
(
3.6k
points)

2
views
gate2005
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
easy
videosolution
To see more, click for the
full list of questions
or
popular tags
.
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
Top Users
2020 Aug 03  09
Ashutosh07091999
18 Points
Mellophi
13 Points
prashastinama
6 Points
manas_kulkarni
4 Points
srestha
2 Points
Unnayan kumar
1 Points
aryashah2k
1 Points
Jhaiyam
1 Points
prabhat0987
1 Points
Kushagra गुप्ता
1 Points
Weekly Top User (excluding moderators) will get free access to
GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users
Aug 2020
Ashutosh07091999
21 Points
Mellophi
19 Points
Unnayan kumar
8 Points
Sourav Kar
7 Points
anurag_yo
7 Points
Shaik Masthan
7 Points
prashastinama
6 Points
sureshthiyam
6 Points
manas_kulkarni
6 Points
srestha
4 Points
7,688
questions
1,815
answers
11,053
comments
95,077
users