Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 7: | Line 7: | ||
$L_3 = \{(a+b)^*\}$ | $L_3 = \{(a+b)^*\}$ | ||
− | + | (1) Intersection of $L_1$ and $L_2$ is | |
'''(A) Regular''' (B) CFL but not regular (C) CSL but not CFL (D) None of these | '''(A) Regular''' (B) CFL but not regular (C) CSL but not CFL (D) None of these | ||
Line 13: | Line 13: | ||
− | + | (2) $L_1$ - $L_3$ is | |
(A) Regular '''(B) CFL but not regular''' (C) CSL but not CFL (D) None of these | (A) Regular '''(B) CFL but not regular''' (C) CSL but not CFL (D) None of these |
Consider
$L_1 = \{a^nb^nc^md^m | m,n \ge 1\}$
$L_2 = \{a^nb^n | n \ge1\}$
$L_3 = \{(a+b)^*\}$
(1) Intersection of $L_1$ and $L_2$ is
(A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
(2) $L_1$ - $L_3$ is
(A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
(1) Regular.
L₁ ∩ L₂ = {abcd,aabbcd,aaabbbccdd,.....} ∩ {ab, aabb, aaabbb,....} = ϕ
(2) CFL
L₁ - L₃ = L₁, hence CFL Proof, L₁ - L₃ = {abcd,aabbcd,aaabbbccdd,.....} - { ∊,a,b,ab,aab,.....} = {abcd,aabbcd,aaabbbccdd,.....} = L₁
Consider
$L_1 = \{a^nb^nc^md^m | m,n \ge 1\}$
$L_2 = \{a^nb^n | n \ge1\}$
$L_3 = \{(a+b)^*\}$
(1) Intersection of $L_1$ and $L_2$ is
(A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
(2) $L_1$ - $L_3$ is
(A) Regular (B) CFL but not regular (C) CSL but not CFL (D) None of these
(1) Regular.
L₁ ∩ L₂ = {abcd,aabbcd,aaabbbccdd,.....} ∩ {ab, aabb, aaabbb,....} = ϕ
(2) CFL
L₁ - L₃ = L₁, hence CFL Proof, L₁ - L₃ = {abcd,aabbcd,aaabbbccdd,.....} - { ∊,a,b,ab,aab,.....} = {abcd,aabbcd,aaabbbccdd,.....} = L₁