retagged by
750 views
3 votes
3 votes
$L_{1}=\{a^nb^mc^md^n | m,n \geq 1\} \\ L_{2}=\{0^p1^q\ |p > q\geq 0\} \cup \{0^p1^q\ |q > p\geq 0\} \\ L_{3} = L_1 \cup L_2 \\ L_{4} = L_1L_2 $

Then which of the following is necessarily CFL?

$ A. L_{3} \cap L_{4}  \\

B. \overline{L_{3} \cap L_{4}}  \\

C.\overline L_3 \cap L_4  \\

D. L_3.L_4$
retagged by

1 Answer

3 votes
3 votes

L1={anbmcmdn|m,n≥1} : It is clearly DCFL (store a, then store b, then remove b if c comes, then remove a if d comes)

L2={0p1q |p>q≥0} ∪ {0p1q |q>p≥0}: It is as good as {0p1q | either p is greater than q or q is greater than p, i,e. p!=q}, It is also DCFL.

L3=L1∪L2 = DCFL ∪ DCFL = CFL (bcz DCFL is not closed under union, but CFL is, we have upgraded DCFL to CFL)

L4=L1L2 = DCFL.DCFL = CFL (bcz DCFL is not closed under concatenation, but CFL is, we have upgraded DCFL to CFL)

A. L3∩L4 : CFL  CFL = CSL (bcz CFL is not closed under intersection, but CSL is, we have upgraded CFL to CSL)

B. comp(L3∩L4) : CFL  CFL = CSL, comp(CSL) = CSL

C. comp(L3)∩L4 : comp(CFL) ∩ CFL = CSL  CFL = CSL

D. L3.L4 : CFL.CFL = CFL (bcz CFL is closed under concatenation)

Answer should be D

follow this link for closure property: http://gatecse.in/closure-property-of-language-families/

Related questions

3 votes
3 votes
2 answers
1
0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
0 votes
0 votes
1 answer
4
admin asked Oct 12, 2019
1,301 views
We defined the rotational closure of language $A$ to be $RC(A) = \{yx \mid xy \in A\}$.Show that the class of CFLs is closed under rotational closure.