Line 17: Line 17:
 
(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
  
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
(1) Regular.
 
(1) Regular.
 
  L₁ ∩ L₂  
 
  L₁ ∩ L₂  

Revision as of 14:05, 14 April 2014

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 by Arjun Suresh

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




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 by Arjun Suresh[edit]

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




blog comments powered by Disqus