Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Let L be a language and L' be its complem...
Start Learning for Free
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?
- a)Neither L nor L' is recursively enumerable (r.e.).
- b)One of L and L' is r.e. but not recursive; the other is not r.e.
- c)Both L and L' are r.e. but not recursive.
- d)Both L and L' are recursive
Correct answer is option 'C'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Let L be a language and L' be its complement. Which one of the fol...
A) It is possible if L itself is NOT RE. Then L' will also not be RE.
B) Suppose there is a language such that turing machine halts on the input. The given language is RE but not recursive and its complement is NOT RE.
C) This is not possible because if we can write enumeration procedure for both languages and it's complement, then the language becomes recursive.
D) It is possible because L is closed under complement if it is recursive. Thus, C is the correct choice.
B) Suppose there is a language such that turing machine halts on the input. The given language is RE but not recursive and its complement is NOT RE.
C) This is not possible because if we can write enumeration procedure for both languages and it's complement, then the language becomes recursive.
D) It is possible because L is closed under complement if it is recursive. Thus, C is the correct choice.
Most Upvoted Answer
Let L be a language and L' be its complement. Which one of the fol...
Explanation:
To understand why option C is not a viable possibility, let's analyze the different options one by one.
a) Neither L nor L is recursively enumerable (r.e.):
In this case, both the language L and its complement L are not recursively enumerable. This means that there is no Turing machine that can accept all the strings in L or L. This is a valid possibility.
b) One of L and L is r.e. but not recursive; the other is not r.e.:
In this case, one of the language L or its complement L is recursively enumerable but not recursive, while the other language is not recursively enumerable. This is also a valid possibility.
c) Both L and L are r.e. but not recursive:
This option states that both the language L and its complement L are recursively enumerable but not recursive. However, this is not a viable possibility because the complement of a recursively enumerable language is not necessarily recursively enumerable. In other words, if L is recursively enumerable, it does not imply that its complement L is also recursively enumerable. Therefore, option C is not a valid possibility.
d) Both L and L are recursive:
This option states that both the language L and its complement L are recursive. A recursive language is a language for which there exists a Turing machine that can accept all the strings in the language and reject all other strings. This is a valid possibility.
Therefore, the correct answer is option C as it states a possibility that is not viable.
To understand why option C is not a viable possibility, let's analyze the different options one by one.
a) Neither L nor L is recursively enumerable (r.e.):
In this case, both the language L and its complement L are not recursively enumerable. This means that there is no Turing machine that can accept all the strings in L or L. This is a valid possibility.
b) One of L and L is r.e. but not recursive; the other is not r.e.:
In this case, one of the language L or its complement L is recursively enumerable but not recursive, while the other language is not recursively enumerable. This is also a valid possibility.
c) Both L and L are r.e. but not recursive:
This option states that both the language L and its complement L are recursively enumerable but not recursive. However, this is not a viable possibility because the complement of a recursively enumerable language is not necessarily recursively enumerable. In other words, if L is recursively enumerable, it does not imply that its complement L is also recursively enumerable. Therefore, option C is not a valid possibility.
d) Both L and L are recursive:
This option states that both the language L and its complement L are recursive. A recursive language is a language for which there exists a Turing machine that can accept all the strings in the language and reject all other strings. This is a valid possibility.
Therefore, the correct answer is option C as it states a possibility that is not viable.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Top Courses for Computer Science Engineering (CSE)View all
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer?
Question Description
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer?.
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer?.
Solutions for Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer?, a detailed solution for Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? has been provided alongside types of Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?a)Neither L nor L' is recursively enumerable (r.e.).b)One of L and L' is r.e. but not recursive; the other is not r.e.c)Both L and L' are r.e. but not recursive.d)Both L and L' are recursiveCorrect answer is option 'C'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup