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
0
votes
0
answers
1
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

16
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
2
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

25
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
3
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

31
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
4
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
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

16
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
5
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 16
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

16
views
theoryofcomputation
proof
recursiveandrecursivelyenumerablelanguages
turingmachine
peterlinz
0
votes
0
answers
6
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 16
in
Theory of Computation
by
Rishi yadav
Boss
(
11.4k
points)

13
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
7
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

20
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
8
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

10
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
9
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
asked
Mar 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

20
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
10
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

12
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

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

18
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
13
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

16
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
14
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

6
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
15
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

7
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
16
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

13
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
17
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 16
in
Computer Networks
by
Rishi yadav
Boss
(
11.4k
points)

4
views
peterlinz
theoryofcomputation
proof
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
18
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
in
Theory of Computation
by
register_user_19
Active
(
2.3k
points)

43
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
19
Ace Test Series: Theory Of Computation  Decidablity
asked
Jan 23
in
Theory of Computation
by
Shankar Kakde
(
195
points)

72
views
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
acetestseries
decidability
0
votes
0
answers
20
ACE Test series on Recursively Enumerable Language
asked
Jan 14
in
Theory of Computation
by
Shankar Kakde
(
195
points)

41
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
21
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 9
in
Theory of Computation
by
Sambhrant Maurya
Active
(
3.4k
points)

63
views
madeeasytestseries
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
22
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
in
Theory of Computation
by
bts1jimin
(
199
points)

110
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
23
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
in
Theory of Computation
by
sripo
Active
(
2.4k
points)

67
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
regularexpressions
0
votes
1
answer
24
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
(
79
points)

94
views
decidability
theoryofcomputation
contextfreelanguage
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
25
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 29, 2018
in
Theory of Computation
by
Deepanshu
Loyal
(
7.8k
points)

119
views
ricetheorem
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
26
MadeEasy Test Series: Theory Of Computation  Recursive And Recursive Enumerable Languages
asked
Dec 24, 2018
in
Theory of Computation
by
suneetha
(
441
points)

136
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
27
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_
(
425
points)

88
views
decidability
#theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
28
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
(
149
points)

67
views
theoryofcomputation
turingmachine
grammar
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
29
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
(
79
points)

63
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
30
self doubt  Turing Machines
I have doubt in the following question: Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language accepted by a turing machine M. Now, I am getting confused over the keyword “accepted”. What should L(M) be considered? Is it REC or RE?
asked
Dec 17, 2018
in
Theory of Computation
by
Harsh Kumar
Active
(
1.3k
points)

48
views
theoryofcomputation
turingmachine
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
Really helpful sir Thanks a ton👍👍
Amazing work Sir
Not in my hands. Flipkart is showing my location...
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
50,644
questions
56,523
answers
195,604
comments
101,286
users