Match 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:
Solution
The 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
|