Question
Download Solution PDFMatch List I with List II:
LR: Regular language, LCF: Context free language
LREC: Recursive language, LRE: Recursively enumerable language.
|
List I |
List II |
|
(A) Recursively Enumerable language |
(I) L̅REC ∪ LRE |
|
(B) Recursive language |
(II) L̅CF ∪ LREC |
|
(C) Context Free language |
(III) LR ∩ LCF |
Choose the correct answer from the options given below:
Answer (Detailed Solution Below)
Detailed Solution
Download Solution PDFThe correct answer is option 3.
Key Points
L̅REC ∪ LRE = (Recursive ∪ Recursively enumerable)= Recursively enumerable
Recursive languages closed under complement so, L̅REC is Recursive. Union of recursive and recursively enumerable is recursively enumerable.
L̅CF ∪ LREC = (not Context-free ∪ Recursive ) =(Recursive ∪ Recursive)= Recursive.
Context-free is not closed for a complement so, L̅CF is Recursive. The union of recursive and recursive is recursive.
LR ∩ LCF = (Regular ∩ Context Free ) = Context Free.
The intersection of regular and context-free is Context Free.
∴ Hence the correct answer is A - I, B - II, C - III.
Additional Information
| Regular | DCFL | CFL | CSL | Recursive | REL | |
| Union | Y | N | Y | Y | Y | Y |
| Intersection | Y | N | N | Y | Y | Y |
| Complement | Y | Y | N | Y | Y | N |
| Difference | Y | N | N | Y | Y | N |
| Prefix | Y | Y | Y | Y | Y | Y |
| Suffix | Y | Y | Y | Y | Y | Y |
| Substring | Y | Y | Y | Y | Y | Y |
| Concatenation | Y | N | Y | Y | Y | Y |
| Reversal | Y | N | Y | Y | Y | Y |
| Kleen closure | Y | N | Y | Y | Y | Y |
| positive closure | Y | N | Y | Y | Y | Y |
| subset | N | N | N | N | N | N |
| substitution | Y | N | Y | N | N | Y |
| Homomorphism | Y | N | Y | N | N | Y |
| Inverse Homomorphism | Y | Y | Y | Y | Y | Y |
|
Y=Closed N=Not closed |
||||||
Last updated on Jun 12, 2025
-> The UGC NET June 2025 exam will be conducted from 25th to 29th June 2025.
-> The UGC-NET exam takes place for 85 subjects, to determine the eligibility for 'Junior Research Fellowship’ and ‘Assistant Professor’ posts, as well as for PhD. admissions.
-> The exam is conducted bi-annually - in June and December cycles.
-> The exam comprises two papers - Paper I and Paper II. Paper I consists of 50 questions and Paper II consists of 100 questions.
-> The candidates who are preparing for the exam can check the UGC NET Previous Year Papers and UGC NET Test Series to boost their preparations.