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₃ʻ
  = L₁ ∩ {∊,a,b,ab,aab,....}'
+
  = L₁ ∩ {∊,a,b,ab,aab,....}ʻ
 
  = L₁ ∩ (a+b)* (c+d)⁺
 
  = L₁ ∩ (a+b)* (c+d)⁺
 
  = L₁
 
  = L₁

Revision as of 21:53, 16 December 2013

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

Solution

(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₁




blog comments powered by Disqus

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

Solution[edit]

(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₁




blog comments powered by Disqus