Question

Match List I with List II:

L_R: Regular language, LCF: Context free language

L_REC: Recursive language, L_RE: 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:

1. A - II, B - III, C - I 
2. A - III, B - I, C - II 
3. A - I, B - II, C - III
4. A - II, B - I, C - III

Answer 1

Correct Answer - Option 3 : A - I, B - II, C - III

The correct answer is option 3.

 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.

	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