Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Videos > Question Bank for GATE Computer Science Engineering > Recursive & Recursively Enumerable Languages
Recursive & Recursively Enumerable Languages Video Lecture | Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE)
FAQs on Recursive & Recursively Enumerable Languages Video Lecture - Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE)
| 1. What is the difference between a recursive language and a recursively enumerable language? |  |
Ans. A recursive language is a language for which there exists an algorithm that can decide whether a given input belongs to the language or not. In other words, a recursive language is decidable. On the other hand, a recursively enumerable language is a language for which there exists an algorithm that can enumerate all the strings in the language, but it may not be able to decide whether a given string belongs to the language or not.
| 2. Can a recursively enumerable language be recursive as well? | |
Ans. Yes, a recursively enumerable language can also be recursive. If a language is recursively enumerable and there exists an algorithm that can decide whether a given input belongs to the language or not, then the language is both recursively enumerable and recursive. In other words, every recursive language is also recursively enumerable.
| 3. Are all recursive languages recursively enumerable? | |
Ans. Yes, all recursive languages are recursively enumerable. This is because if a language is recursive, then there exists an algorithm that can decide whether a given input belongs to the language or not. By modifying this algorithm slightly, we can also enumerate all the strings in the language. Therefore, every recursive language is also recursively enumerable.
| 4. Is it possible for a language to be neither recursive nor recursively enumerable? | |
Ans. Yes, it is possible for a language to be neither recursive nor recursively enumerable. Such languages are called non-recursive and non-recursively enumerable languages. These languages cannot be decided or enumerated by any algorithm. Examples of such languages include the language of all Turing machine descriptions that do not halt on empty input, and the language that contains all strings that encode a valid proof in a formal system.
| 5. Can a recursively enumerable language have an algorithm that decides it? | |
Ans. No, a recursively enumerable language cannot have an algorithm that decides it. A language can only be decided if it is recursive, but a recursively enumerable language may have an algorithm that can only enumerate its strings.
About this Video
4.61/5
Rating
Oct 19, 2025
Last updated
Related Exams
Video Description: Recursive & Recursively Enumerable Languages for Computer Science Engineering (CSE) 2025 is part of Question Bank for GATE Computer Science Engineering preparation.
The notes and questions for Recursive & Recursively Enumerable Languages have been prepared according to the Computer Science Engineering (CSE) exam syllabus.
Information about Recursive & Recursively Enumerable Languages covers all important topics for Computer Science Engineering (CSE) 2025 Exam.
Find important definitions, questions, notes, meanings, examples, exercises and tests below for Recursive & Recursively Enumerable Languages.
Introduction of Recursive & Recursively Enumerable Languages in English is available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Recursive & Recursively Enumerable Languages in
Hindi for Question Bank for GATE Computer Science Engineering course. Download more important topics related with notes, lectures and mock test series for
Computer Science Engineering (CSE) Exam by signing up for free.
Description
Video Lecture & Questions for Recursive & Recursively Enumerable Languages Video Lecture | Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE) - Computer Science Engineering (CSE) full syllabus preparation | Free video for Computer Science Engineering (CSE) exam to prepare for Question Bank for GATE Computer Science Engineering.
Information about Recursive & Recursively Enumerable Languages
Here you can find the meaning of Recursive & Recursively Enumerable Languages defined & explained in the simplest way possible.
Besides explaining types of Recursive & Recursively Enumerable Languages theory, EduRev gives you an ample number of questions to practice Recursive & Recursively Enumerable Languages tests,
examples and also practice Computer Science Engineering (CSE) tests.
Related Searches
Sample Paper
,Exam
,Recursive & Recursively Enumerable Languages Video Lecture | Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE)
,Extra Questions
,study material
,Free
,Objective type Questions
,Semester Notes
,Recursive & Recursively Enumerable Languages Video Lecture | Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE)
,past year papers
,Previous Year Questions with Solutions
,mock tests for examination
,MCQs
,ppt
,practice quizzes
,Important questions
,Summary
,shortcuts and tricks
,Recursive & Recursively Enumerable Languages Video Lecture | Question Bank for GATE Computer Science Engineering - Computer Science Engineering (CSE)
,video lectures
,Viva Questions
;
Study Recursive & Recursively Enumerable Languages on the App
Students of Computer Science Engineering (CSE) can study Recursive & Recursively Enumerable Languages alongwith tests & analysis from the EduRev app,
which will help them while preparing for their exam. Apart from the Recursive & Recursively Enumerable Languages,
students can also utilize the EduRev App for other study materials such as previous year question papers, syllabus, important questions, etc.
The EduRev App will make your learning easier as you can access it from anywhere you want.
The content of Recursive & Recursively Enumerable Languages is prepared as per the latest Computer Science Engineering (CSE) syllabus.
|
© EduRev
|
Education Revolution
|
|
Signup on EduRev and stay on top of your study goals
10M+ students crushing their study goals daily