menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent Blog Comments
hi this pdf have gate prevoius year questions or...
Thanks, dude for sharing your experience !! It...
Congratulations, at least you made it to the...
seems like you really enjoyed the process.......
I wrote an email to IISC regarding JEST 2021 but...
Network Sites
GO Mechanical
GO Electrical
GO Electronics
GO Civil
CSE Doubts
Peter Linz Edition 5 Exercise 11.1 Question 12 (Page No. 284)
0
votes
70
views
Let $L_1$ be recursive and $L_2$ recursively enumerable. Show that $L_2-L_1$ is necessarily recursively enumerable.
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
asked
Mar 16, 2019
in
Computer Networks
Rishi yadav
70
views
answer
comment
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
2
Answers
1
vote
Best answer
$L_2 - L_1 = L_2 \cap {L_1}^c$
Now, complement of a recursive language is always recursive - so ${L_1}^c$ is recursive and hence recursively enumerable too.
Intersection of two recursively enumerable languages always gives a recursively enumerable language (Recursively Enumerable set is closed under union and intersection but not under complement).
So, $L_2 - L_1$ is guaranteed to be recursively enumerable.
answered
Mar 16, 2019
Arjun
selected
Mar 17, 2019
by
Rishi yadav
comment
Please
log in
or
register
to add a comment.
0
votes
Recursive is closed under complement.
Recursive ennum is closed under intersection .
answered
Mar 17, 2019
abhishekmehta4u
comment
Please
log in
or
register
to add a comment.
← Prev.
Next →
← Prev. Qn. in Sub.
Next Qn. in Sub. →
Related questions
0
votes
1
answer
1
72
views
Peter Linz Edition 5 Exercise 11.1 Question 11 (Page No. 284)
Prove that the complement of a context-free language must be recursive.
Prove that the complement of a context-free language must be recursive.
asked
Mar 16, 2019
in
Computer Networks
Rishi yadav
72
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
1
vote
1
answer
2
57
views
Peter Linz Edition 5 Exercise 11.1 Question 10 (Page No. 284)
Is the family of recursive languages closed under concatenation$?$
Is the family of recursive languages closed under concatenation$?$
asked
Mar 16, 2019
in
Computer Networks
Rishi yadav
57
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
3
53
views
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.
Show that the families of recursively enumerable and recursive languages are closed under reversal.
asked
Mar 16, 2019
in
Computer Networks
Rishi yadav
53
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
4
30
views
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.
Show that the family of recursive languages is closed under union and intersection.
asked
Mar 16, 2019
in
Computer Networks
Rishi yadav
30
views
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
...