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
3
answers
1
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is a) Decidable b) Semi decidable c) not even semidecidable
asked
Dec 30, 2017
in
Theory of Computation
by
Abhishek Kumar Singh
Junior
(
829
points)

257
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
2
Turing Machine
A. L is undecidable B. L is decidable C. L is regular. D. None of these. Please explain in detail.
asked
Dec 23, 2017
in
Theory of Computation
by
Shubham Kumar Gupta
(
449
points)

151
views
turingmachine
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
3
Previous year gate question Toc
Define languages L0L0 and L1L1 as follows : L0={⟨M,w,0⟩∣M halts on w}L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halts on w}L1={⟨M,w,1⟩∣M does not halts on w} Here ⟨M,w,i⟩⟨M,w,i⟩ is a triplet, whose first ... @others As L0 is recursive as it halt And L1 is recursive enumerable as it does not halt So recursive U recursive enumerable will recursive enumerable rt?
asked
Dec 1, 2017
in
Theory of Computation
by
hem chandra joshi
Active
(
4.1k
points)

352
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
4
What is meant by enumeration in context of language?
What is meant by enumeration in context of language?What are not recursively enumerable language?
asked
Dec 1, 2017
in
Theory of Computation
by
hem chandra joshi
Active
(
4.1k
points)

97
views
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
5
Turing Machine
L1={<M> M is a Turing Machine , P is a TM that halts on all input, and P$\epsilon$L(M)} L2={<M> M is a Turing Machine , P is a TM that halts on all input, and M$\epsilon$L(P)} Which one REC, or RE or non RE ?
asked
Nov 29, 2017
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

244
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
6
Turing machine and Recursive Language
If total turing machine is a proper subset of turing machine then why recursive language is not a proper subset of Recursive Enumerable ?
asked
Nov 26, 2017
in
Theory of Computation
by
Mk Utkarsh
Boss
(
35.7k
points)

296
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
7
#TOC Turing Machine Question
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine. I know, other way is correct i.e for every DTM there exist a NDTM, but is above TRUE/FALSE. Thank you!
asked
Nov 1, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.3k
points)

258
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
selfdoubt
+1
vote
2
answers
8
Decidability Question
a) language accepted by a CFG(Context free grammar) is nonempty. is it D or UD?
asked
Oct 30, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.3k
points)

416
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
contextfreelanguage
0
votes
1
answer
9
Turing Machine Question
The set of turning machines which halt on empty input forms a recursively enumerable set?! True or False. Please also state your reason/explanation. AFAIK  TM accept Epsilon if it sees a Blank and goes to accepting state. Thank you!
asked
Oct 30, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.3k
points)

138
views
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
10
R.E Language Question
Let A≤mB denotes that language A is mapping reducible (also known as manytoone reducible) to language B. then what can you say about this  True/False a) A is Recursive, but B is not R.E
asked
Oct 30, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.3k
points)

98
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
2
answers
11
Recursive Enumerable Language Doubt
We know, Recursive Enumerable Language is not closed under complement. a) So, let's say Y is a R.E language and recursive, then what would be Y' (Y complement)? b) Again Y is a R.E language, but this time Y is not recursive then what would be Y' (Y ... ! P.S  I get that answer for b) is Y' (Y complement) is not R.E, but why? and also please explain option a)
asked
Oct 27, 2017
in
Theory of Computation
by
iarnav
Loyal
(
8.3k
points)

535
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
complement
+5
votes
1
answer
12
TOC Test Series
Consider the languages (I) L1= {w#x , where w,x ∈ (0+1)* and # is a special character and w is a prefix of x } . (II) L2={w#x , where w,x ∈ (0+1)* and # is a special character and wR, is a prefix of x}. (III) L3={w#x , where w,x ∈ (0+1)* and # is a ... (II) and (III) is DCFL (I) and (IV) is recursive but not CFL. (I) is recursive , (II) is DCFL , (III) and (IV) are CFL but not DCFL
asked
Oct 14, 2017
in
Theory of Computation
by
sunil sarode
Active
(
1.2k
points)

131
views
theoryofcomputation
dcfl
recursiveandrecursivelyenumerablelanguages
+2
votes
2
answers
13
MadeEasy Subject Test: Theory of Computation  Recursive And Recursively Enumerable Languages
asked
Sep 28, 2017
in
Theory of Computation
by
rajoramanoj
Active
(
4.5k
points)

132
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
14
Decidability
1. {<M,w> M is a TM, and w is a string, and there exist a TM, M' such that w (does not belongs to) L(M) Intersection L(M')} 2. {<M> M is a TM, and M is the only TM that accepts L(M) = { } = empty set} ... of the TM, whose decimal value must be less than 100. Binary Encoding: 0no of states10no of input symbol10no of tape symbol1... like this other information. Ryt??
asked
Sep 19, 2017
in
Theory of Computation
by
Shubhanshu
Boss
(
18.2k
points)

297
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
15
Is this language accepted by a Turing Machine?
Is this language L accepted by a Turing Machine? L = a1n a2n a3n a4n .........amn  m,n > 0 Also, what about this language? L = a1n a2n a3n a4n .........ann  n > 0
asked
Sep 11, 2017
in
Theory of Computation
by
Akash Mishra
Active
(
1.3k
points)

359
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
16
language (TM)
what is the difference between recursive, RE and REL language?? confuse...
asked
Aug 24, 2017
in
Theory of Computation
by
Hira Thakur
Boss
(
14.7k
points)

625
views
recursiveandrecursivelyenumerablelanguages
+4
votes
1
answer
17
decidability
C = { <G,x>  G is a CFG and x is substring of some y ∈ L(G) } . Then C is  a) undecidable b) Turing unrecognizable c) Recursive enumerable d) decidable
asked
Aug 22, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

145
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+3
votes
2
answers
18
decidability
C = { <G,k>  G is a CFG and L(G) contains exactly k strings where k>=0 or k=∞ } . Then C will be a) decidable b) Turing unrecognizable c) Recursive enumerable d) undecidable
asked
Aug 22, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

232
views
decidability
contextfreelanguage
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
19
Recusive enumerable recursive
If a language L and its complement L' are recursively enumerable then choose the correct statement a) L is recursive but not L' b) Both L and L' are recursive c) L' is recursive but not in L d) None of these
asked
Aug 22, 2017
in
Theory of Computation
by
Anshul Shankar
Active
(
1k
points)

381
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
complement
+3
votes
0
answers
20
decidability
S = { < R >  R is a regular expression describing a language containing at least one string w has 111 as a substring (i.e., w = x111y for some x ans y)}. Then what will be S  a) decidable b) undecidable c) Recursive enumerable d) Turing unrecognizable
asked
Aug 20, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

102
views
decidability
recursiveandrecursivelyenumerablelanguages
+4
votes
2
answers
21
decidability
A = { <M>  M is a DFA that accepts some string with more 1s than 0s }. Then A is  a) undecidable b) recursive enumerable c) decidable d) none of the above
asked
Aug 20, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

210
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+2
votes
2
answers
22
decidability
A = { <R,S>  R and S are regular expressions and L(R) ⊆ L(S) }. Then what about A  a) Turing recognizable b) decidable c) undecidable d) Turing unrecognizable
asked
Aug 20, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

387
views
decidability
recursiveandrecursivelyenumerablelanguages
+3
votes
2
answers
23
decidability
INFINITEDFA= {<A>  A is a DFA and L(A) is an infinite language } . Then  a) INFINITEDFA is decidable. b) INFINITEDFA is undecidable. c) INFINITEDFA is Turingrecognizable. d) INFINITEDFA is Turingunrecognizable.
asked
Aug 20, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

127
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
24
decidability
INFINITEPDA = {<M>  M is a PDA and L(M) is an infinite language } . Then  a) INFINITEPDA is undecidable. b) INFINITEPDA is decidable. c) INFINITEPDA is recursive enumerable. d) INFINITEPDA is Turing corecognizable.
asked
Aug 20, 2017
in
Theory of Computation
by
amrendra pal
Active
(
2.2k
points)

104
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
25
Turing machines and Recursively enumerable languages
If L1 and L2 are TuringRecognizable then L1 ∪ L2 will be (a) Decidable (b) Turingrecognizable but may not be decidable (c) May not be Turing recognizable (d) None of above
asked
Aug 20, 2017
in
Theory of Computation
by
codingo1234
Junior
(
877
points)

423
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
Recursive and Recursively Enumerable
A language in NOT  RE is uncountably infinite. true or false? pls elaborate the answer you post.
asked
Aug 18, 2017
in
Theory of Computation
by
Arnabi
Loyal
(
7.9k
points)

226
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
27
DECIDABILITY
Is complement of language same type or not decidable by CFL and recursive language or not??? Grammar is ambiguous or not? Grammar in regular/CFL/rel decidable or not?
asked
Aug 15, 2017
in
Theory of Computation
by
learner_geek
Active
(
3.2k
points)

233
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
contextfreelanguage
badquestion
+1
vote
1
answer
28
geeksforgeeks
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 Y' reduces to W, and Z reduces to X' (reduction means the standard manyone reduction). Which one of the following ... is recursively enumerable. C W is not recursively enumerable and Z is recursive. D W is not recursively enumerable and Z is not recu
asked
Aug 15, 2017
in
Theory of Computation
by
Sunil8860
(
113
points)

83
views
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
29
geeksforgeeks
L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, … Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions. S1 : L1 is recursive implies L2 is recursive S1 is correct can anyone explain how?
asked
Aug 15, 2017
in
Theory of Computation
by
Sunil8860
(
113
points)

40
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
30
geeksforgeeks
asked
Aug 15, 2017
in
Theory of Computation
by
Sunil8860
(
113
points)

44
views
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
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
Amazing work Sir
50,644
questions
56,531
answers
195,622
comments
101,346
users