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
0
votes
1
answer
1
Peter Linz Edition 5 Exercise 11.1 Question 19 (Page No. 284)
Show that the set of all irrational numbers is not countable.
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

62
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
2
Peter Linz Edition 5 Exercise 11.1 Question 18 (Page No. 284)
$\text{Theorem}:$ Let $S$ be an infinite countable set. Then its powerset $2^S$ is not countable. Why does the argument in Theorem fail when $S$ is finite$?$
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

24
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
3
Peter Linz Edition 5 Exercise 11.1 Question 17 (Page No. 284)
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$. Show that in fact $S_2S_1$ cannot be countable.
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

34
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
4
Peter Linz Edition 5 Exercise 11.1 Question 16 (Page No. 284)
Let $S_1$ be a countable set, $S_2$ a set that is not countable, and $S_1 \subset S_2$. Show that $S_2$ must then contain an infinite number of elements that are not in $S_1$.
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

44
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
5
Peter Linz Edition 5 Exercise 11.1 Question 15 (Page No. 284)
$\text{Theorem}:$ There exists a recursively enumerable language whose complement is not recursively enumerable. Choose a particular encoding for Turing machines, and with it, find one element of the languages $\bar{L}$ in Theorem
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

24
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
6
Peter Linz Edition 5 Exercise 11.1 Question 14 (Page No. 284)
If $L$ is recursive, is it necessarily true that $L^+$ is also recursive$?$
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

25
views
theoryofcomputation
proof
recursiveandrecursivelyenumerablelanguages
turingmachine
peterlinz
peterlinzedition5
0
votes
0
answers
7
Peter Linz Edition 5 Exercise 11.1 Question 13 (Page No. 284)
Suppose that $L$ is such that there exists a Turing machine that enumerates the elements of $L$ in proper order. Show that this means that $L$ is recursive.
asked
Mar 17, 2019
in
Theory of Computation
by
Rishi yadav

19
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
8
Peter Linz Edition 5 Exercise 11.1 Question 12 (Page No. 284)
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2L_1$ is necessarily recursively enumerable.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

34
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
9
Peter Linz Edition 5 Exercise 11.1 Question 11 (Page No. 284)
Prove that the complement of a contextfree language must be recursive.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

31
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
10
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

39
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
Peter Linz Edition 5 Exercise 11.1 Question 9 (Page No. 284)
Show that the families of recursively enumerable and recursive languages are closed under reversal.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

25
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
12
Peter Linz Edition 5 Exercise 11.1 Question 8 (Page No. 284)
Show that the family of recursive languages is closed under union and intersection.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

16
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
13
Peter Linz Edition 5 Exercise 11.1 Question 7 (Page No. 284)
Is the family of recursively enumerable languages closed under intersection$?$
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

34
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 11.1 Question 6 (Page No. 284)
Show that the family of recursively enumerable languages is closed under union.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

22
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 11.1 Question 5 (Page No. 284)
Show that if a language is not recursively enumerable, its complement cannot be recursive.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

9
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 11.1 Question 4 (Page No. 284)
Let $L$ be a contextfree language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for it.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

14
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 11.1 Question 3 (Page No. 284)
Let $L$ be a finite language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for $L^+$
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

59
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 11.1 Question 2 (Page No. 284)
Prove that the set of all languages that are not recursively enumerable is not countable.
asked
Mar 17, 2019
in
Computer Networks
by
Rishi yadav

13
views
peterlinz
peterlinzedition5
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
19
ACE Full Length Mock Test8
Let L be recursively enumerable languages. There is an algorithm that can enumerate all string of L in proper order. If language M is reducible to L then which of the following is correct ? M is REL but not recursive Complement of M is not REL M $\cap$ L is recursive None of these
asked
Jan 25, 2019
in
Theory of Computation
by
register_user_19

59
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
20
Ace Test Series: Theory Of Computation  Decidablity
asked
Jan 24, 2019
in
Theory of Computation
by
Shankar Kakde

100
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
acetestseries
decidability
0
votes
0
answers
21
ACE Test series on Recursively Enumerable Language
asked
Jan 14, 2019
in
Theory of Computation
by
Shankar Kakde

54
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
22
MadeEasy Test Series: Theory of Computation  Recursive and RE Languages
Which of the following languages are recursive? L1: { <M,k>  M is a turing machine and { w ∈ L(M) : w ∈ a*b* }  <=k} L2: { <M>  there exists a turing machine M’ such that <M> ≠ <M’> and L(M) = L(M’)
asked
Jan 10, 2019
in
Theory of Computation
by
Sambhrant Maurya

69
views
madeeasytestseries
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
23
RE or non RE
CONSIDER THE FLLOWING LANGUAGE L={<M> M is a TM and L(M)=empty} Which of the following is true? a Decidable REC B Undecidable and RE cUndecidable and non RE d Decidable but RE
asked
Jan 8, 2019
in
Theory of Computation
by
bts1jimin

173
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
24
Language accepted by this Turing Machine
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
asked
Jan 5, 2019
in
Theory of Computation
by
sripo

90
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
regularexpressions
0
votes
1
answer
25
Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.
asked
Dec 30, 2018
in
Theory of Computation
by
Ayan21

158
views
decidability
theoryofcomputation
contextfreelanguages
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
SELF DOUBT_ RICE THEOREM
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
asked
Dec 30, 2018
in
Theory of Computation
by
Deepanshu

145
views
ricetheorem
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
27
MadeEasy Test Series: Theory Of Computation  Recursive And Recursive Enumerable Languages
asked
Dec 24, 2018
in
Theory of Computation
by
suneetha

215
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
28
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
asked
Dec 24, 2018
in
Theory of Computation
by
Rahul_Rathod_

168
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
29
Self doubt
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every recursive language, there is a grammar or not, and if there is, is there a formal definition of the same?
asked
Dec 20, 2018
in
Theory of Computation
by
subho16

83
views
theoryofcomputation
turingmachine
grammar
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
30
Zeal Theory of Computation module.
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
asked
Dec 17, 2018
in
Theory of Computation
by
Ayan21

75
views
theoryofcomputation
decidability
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
IITD MS CSE (Systems) Experience
IIT Bombay M.Tech. (RA)  Interview Experience
Interview Experience for MS(R)IIT Delhi (School of Information Technology)
How am I preparing
PGEE 2020 (CSE) Experience
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
Very helpful. can't thank you enough! :) :)
@toxicdesire I don't remember the exact...
Will you please tell what they answered to your...
@commenter max marks for part A was 75. They did...
Hope you get selected bhaiya
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
52,345
questions
60,506
answers
201,910
comments
95,339
users