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
1
answer
1
geeksforgeeks
?
asked
Aug 15, 2017
in
Theory of Computation
by
Sunil8860
(
113
points)

67
views
recursiveandrecursivelyenumerablelanguages
decidability
+1
vote
1
answer
2
TOC RE REC
A RE language can also be called as Turing Recognizable,Turing Acceptable or Turing Enumerable. And REC can be called as Turing Decidable. Now When we say that a language is Turing Computable, Strictly what we could say that it is RE or REC? (Ofcourse if it is REC then it is RE also) PS : It would be great if you could provide some reliable source for it.
asked
Aug 9, 2017
in
Theory of Computation
by
VS
Boss
(
10.5k
points)

421
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
3
TOC Not RE language Set
Why set of Not RE languages is uncountable infinite ?Not RE is discrete in nature?
asked
Aug 7, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
25.3k
points)

292
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
4
Self Doubt TOC Enumeration Method
If language L is countable infinite set then, L is Recursive as we can define enumeration method for the countable set. or It can Regular ??
asked
Jul 17, 2017
in
Theory of Computation
by
AnilGoudar
Active
(
4.3k
points)

175
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
5
Union of R.E and non R.E
What is the class of the language resulting from Union of R.E and non R.E ? (R.E => recursively enumerable)
asked
Jun 18, 2017
in
Theory of Computation
by
Xylene
Active
(
3.6k
points)

196
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
6
Language which is not a CSL but can be accepted by TM
Can anyone give me an example of a language which is not a CSL but can be accepted using a TM?
asked
Jun 15, 2017
in
Theory of Computation
by
Xylene
Active
(
3.6k
points)

352
views
theoryofcomputation
contextfreelanguage
pushdownautomata
contextsensitive
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
7
Peter Linz Exercise 11.1
If L is recursive, is it necessarily true that L+ is also recursive?
asked
May 14, 2017
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
27.6k
points)

255
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
Peter Linz Exercise 11.1
Prove that the complement of context free language is recursive.
asked
May 14, 2017
in
Theory of Computation
by
Ayush Upadhyaya
Boss
(
27.6k
points)

94
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
contextfreelanguage
+1
vote
2
answers
9
ISRO201777
If $L$ and $P$ are two recursively enumerable languages then they are not closed under Kleene star $L^*$ of $L$ Intersection $L \cap P$ Union $L \cup P$ Set difference
asked
May 7, 2017
in
Theory of Computation
by
sh!va
Boss
(
32.5k
points)

3k
views
isro2017
sets
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
closureproperty
+2
votes
4
answers
10
Recursive languages.
If L1 is Recursive language and L2 is RE. Then L1 ⋂ L2 is RE? Since every Recursive language is RE, then how intersection of the Recursive and RE is RE?
asked
May 2, 2017
in
Theory of Computation
by
AnilGoudar
Active
(
4.3k
points)

223
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
theory of computation
L = { <M> / M is a Turing machine and M accepts a regular language }. This Language L is recursively enumerable but not recursive. ...right ??
asked
Apr 21, 2017
in
Theory of Computation
by
vignesh
(
209
points)

94
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
12
theory of computation
L = { <M,w> / M is a TM,w is a string and M on simulating w,the Read/write head of M moves 100 steps away from the left most symbol of input }.Assume initially the Read/write head is in leftmost symbol of input. MY ANSWER : This language is Recursively enumerable but not recursive ...right ???
asked
Apr 21, 2017
in
Theory of Computation
by
vignesh
(
209
points)

146
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
13
theory of computation
This language, L = { <M,w> / M is a TM,w is a string and M does not halt on string w } is not recursively enumerable ...right ???
asked
Apr 21, 2017
in
Theory of Computation
by
vignesh
(
209
points)

90
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
14
theory of computation
Which of the following languages below are NOT recursively enumerable ? L1 = {<M> / M is a TM that accepts all even numbers }. L2 = {<M> / M does not accept all even numbers } L3 = {<M> / M rejects all even numbers } A) Only L1 B) Only L1 and L2 C) Only L1 and L3 D) All of L1,L2 and L3
asked
Apr 21, 2017
in
Theory of Computation
by
vignesh
(
209
points)

185
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
15
decidability
is intersection of two context sensitive decidable?? I think since they are closed under intersection, it must be decidable. please answer
asked
Feb 10, 2017
in
Theory of Computation
by
sushmita
Boss
(
17.2k
points)

267
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+3
votes
0
answers
16
Are CSL, RE, Recursive languages closed under Subset operation?
Regular languages are not closed under Subset  Example anbn is subset of a*b* which is nonregular. DCFL/CFL languages are not closed under Subset  Example anbncn is subset of anbnc* which is noncfl. Are the languages CSL,Recursive or Recursively Enumerable lanuages closed under Subset operation?
asked
Feb 8, 2017
in
Theory of Computation
by
yg92
Active
(
3.2k
points)

573
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
contextsensitive
contextsensitivelanguages
closureproperty
0
votes
1
answer
17
Decidablity+DCFL
I) LR where L is DCFl and R is regular. Is LR also DCFL decidable or not??? II)If L1 is reducible to L2 and L2 is nonRE then L1 is also NonRE??? III) If L1 is reducible to L2 and L1 is nonRE then L2 is also nonRE??
asked
Feb 7, 2017
in
Theory of Computation
by
Rahul Jain25
Boss
(
11.1k
points)

336
views
theoryofcomputation
decidability
dcfl
closureproperty
regularlanguages
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
18
MadeEasy Subject Test: Theory of Computation  Recursive And Recursively Enumerable Languages
asked
Feb 1, 2017
in
Theory of Computation
by
vaishali jhalani
Active
(
4.7k
points)

71
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
1
answer
19
RE or Non RE
1) Language describing the ambiguity of CFG is RE or Non RE? 2) Language describing the nonambiguity of a CFG (whether a given CFG is nonambiguous) and complement of the language of ambiguity of CFG are RE or Non RE? 3) Inherent Ambiguity of CFL is RE or Non RE? 4) Is language of the complement of Ambiguity and the language of nonambiguity of CFG same?
asked
Jan 30, 2017
in
Theory of Computation
by
srestha
Veteran
(
117k
points)

294
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
20
Countable and recursive language relation
Is every countable language recursive enumerable?
asked
Jan 27, 2017
in
Theory of Computation
by
Purple
Active
(
3k
points)

70
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
countableuncountableset
0
votes
0
answers
21
Gate Practice
Let L be regular language and R be turing recognizable but not accepting language. How many of the following is possible.? 1.compliment of R can be Turing recognizable. 2.L U (R)' can be recursive. 3.set of strings common in R and L can be in not RE. 4.L U R can be recursive. 5.set of strings common in R' and L can be recursive.
asked
Jan 23, 2017
in
Theory of Computation
by
Ravi_1511
Active
(
2k
points)

53
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
22
REC or NONREC
asked
Jan 19, 2017
in
Theory of Computation
by
vaishali jhalani
Active
(
4.7k
points)

123
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+3
votes
1
answer
23
L = { 0n+m 1n+m 0m  n, m >= 0 } CSL or RE?
L = { 0n+m 1n+m 0m  n, m >= 0 } The above language is (a) CFL but not Regular (b) CSL but not CFL (c) RE but not CSL (d) None of the above I thought the answer would be (b) CSL but not CFL but it was given as (c) RE but not CSL Can anyone explain how?
asked
Jan 16, 2017
in
Theory of Computation
by
asterixbachman
(
155
points)

672
views
theoryofcomputation
contextsensitivelanguages
contextsensitive
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
24
Doubt in GateCse Decidability Blog
In the deciadability chart mentioned on http://gatecse.in/grammardecidableandundecidableproblems/ The undecidable problems mentioned here are semidecidable(RE but not REC) not NOT RE.Or there is no such relation? Can someone have a look and tell please?
asked
Jan 15, 2017
in
Theory of Computation
by
rahul sharma 5
Boss
(
25.3k
points)

219
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
+3
votes
1
answer
25
toc doubt
asked
Jan 14, 2017
in
Theory of Computation
by
Arnabi
Loyal
(
7.9k
points)

578
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
TOC Recurive language
R = RE ∩ CoRE where R is the set of recursive language,RE is the set of languages of which membership can be proved in finite time and CoRE is the set of language of which membership can be disproved in finite amount of time True/False?
asked
Jan 6, 2017
in
Theory of Computation
by
Prajwal Bhat
Boss
(
11.2k
points)

33
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+2
votes
0
answers
27
Turing Recognizable (TestBook Question)
Which of the following is/are NOT turingrecognizable? 1. L1={M1M2M1M2 are Turing Machines with L(M1)=L(M2)} 2. L2={M,wM is a Turing Machine that halts on input w} 3. L3={M,wM is a Turing Machine that accepts string w} 4.All of the Above
asked
Jan 2, 2017
in
Theory of Computation
by
Archies09
Active
(
1.1k
points)

276
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
28
TOC Recursive languages
How does complement of a Recursively enumerable but not recursive is not recursively enumerable?
asked
Dec 27, 2016
in
Theory of Computation
by
Veerendra V
(
437
points)

118
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
decidability
+5
votes
1
answer
29
decidability
Consider the following languages L1={<M> there exists x,y belonging to (sigma*) such that either x belongs to L(M) or y does not belong to L(M)}. Answer Recursive, This is the language of all turing machines L2={<M1,M2> L(M1) < L(M2)} Answer Not even recursively enumerable. Arjun sir plzz explain these languages.
asked
Dec 26, 2016
in
Theory of Computation
by
sushmita
Boss
(
17.2k
points)

596
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
30
decidability doubt
While applying decidability theorem, can we only apply this theorem to undecidable problems or can we also apply them to recursively enumerable ie semidecidablle problems??
asked
Dec 23, 2016
in
Theory of Computation
by
sushmita
Boss
(
17.2k
points)

164
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
turingmachine
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
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,648
questions
56,459
answers
195,335
comments
100,184
users