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
+1
vote
1
answer
1
Turing machine
If L is accepted by TM, which halts on every string over alphabet {a, b}, then L′ is recursive language. True or False ? I think false because L′ = TM halts on no string in {a,b} = $\phi$ and L(TM) = $\phi$ is non RE, let alone it being recursive
asked
Jan 1, 2018
in
Theory of Computation
by
just_bhavana

232
views
recursiveandrecursivelyenumerablelanguages
+1
vote
3
answers
2
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

275
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
3
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

166
views
turingmachine
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
4
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

532
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
5
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

131
views
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
6
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

333
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
7
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

409
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
8
#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

285
views
turingmachine
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
selfdoubt
+1
vote
2
answers
9
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

540
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
contextfreelanguages
0
votes
1
answer
10
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

176
views
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
11
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

116
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
2
answers
12
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

1.1k
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
complement
+5
votes
1
answer
13
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

161
views
theoryofcomputation
dcfl
recursiveandrecursivelyenumerablelanguages
+2
votes
2
answers
14
MadeEasy Subject Test: Theory of Computation  Recursive And Recursively Enumerable Languages
asked
Sep 28, 2017
in
Theory of Computation
by
rajoramanoj

148
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
15
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

329
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
16
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 12, 2017
in
Theory of Computation
by
Akash Mishra

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

946
views
recursiveandrecursivelyenumerablelanguages
+4
votes
1
answer
18
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 23, 2017
in
Theory of Computation
by
amrendra pal

157
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+3
votes
2
answers
19
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 23, 2017
in
Theory of Computation
by
amrendra pal

392
views
decidability
contextfreelanguages
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
20
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

414
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
complement
+3
votes
0
answers
21
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 21, 2017
in
Theory of Computation
by
amrendra pal

163
views
decidability
recursiveandrecursivelyenumerablelanguages
+4
votes
2
answers
22
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 21, 2017
in
Theory of Computation
by
amrendra pal

277
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+3
votes
3
answers
23
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

508
views
decidability
recursiveandrecursivelyenumerablelanguages
+3
votes
2
answers
24
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

166
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
25
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

150
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
26
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

573
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
27
Recursive and Recursively Enumerable
A language in NOT  RE is uncountably infinite. true or false? pls elaborate the answer you post.
asked
Aug 19, 2017
in
Theory of Computation
by
Arnabi

270
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
28
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

329
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
contextfreelanguages
badquestion
+1
vote
1
answer
29
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

106
views
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
30
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

58
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
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,433
answers
201,778
comments
95,257
users