Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| Line 22: | Line 22: | ||
(2) CFL | (2) CFL | ||
| + | |||
L₁ - L₂ = L₁, hence CFL | L₁ - L₂ = L₁, hence CFL | ||
Alternatively, | Alternatively, | ||
| − | L₁ - L₃ = L₁ ∩ | + | L₁ - L₃ = L₁ ∩ L₃ʻ |
| − | = L₁ ∩ {∊,a,b,ab,aab,....} | + | = L₁ ∩ {∊,a,b,ab,aab,....}ʻ |
= L₁ ∩ (a+b)* (c+d)⁺ | = L₁ ∩ (a+b)* (c+d)⁺ | ||
= L₁ | = 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.
GATECSEL₁ ∩ L₂
= {abcd,aabbcd,aaabbbccdd,.....} ∩ {ab, aabb, aaabbb,....}
= ϕ
(2) CFL
L₁ - L₂ = L₁, hence CFL
Alternatively,
L₁ - L₃ = L₁ ∩ L₃ʻ
= L₁ ∩ {∊,a,b,ab,aab,....}ʻ
= L₁ ∩ (a+b)* (c+d)⁺
= 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
Alternatively,
L₁ - L₃ = L₁ ∩ L₃'
= L₁ ∩ {∊,a,b,ab,aab,....}'
= L₁ ∩ (a+b)* (c+d)⁺
= L₁