(13 intermediate revisions by the same user not shown)
Line 1: Line 1:
Consider $L_1 = \{a^nb^nc^md^m | m,n \ge 1\}$
+
Consider
 +
 
 +
$L_1 = \{a^nb^nc^md^m | m,n \ge 1\}$
  
 
$L_2 = \{a^nb^n | n \ge1\}$
 
$L_2 = \{a^nb^n | n \ge1\}$
Line 5: Line 7:
 
$L_3 = \{(a+b)^*\}$
 
$L_3 = \{(a+b)^*\}$
  
'''(1) Intersection of $L_1$ and $L_2$ is'''
+
(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 11: Line 13:
  
  
'''(2) $L_1$ - $L_3$ is'''
+
(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
  
===Solution===
+
==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 
(1) Regular.
 
(1) Regular.
 
  L₁ ∩ L₂  
 
  L₁ ∩ L₂  
Line 24: Line 26:
  
 
  L₁ - L₃ = L₁, hence CFL
 
  L₁ - L₃ = L₁, hence CFL
 +
Proof,
 +
L₁ - L₃ = {abcd,aabbcd,aaabbbccdd,.....} - { ∊,a,b,ab,aab,.....}
 +
= {abcd,aabbcd,aaabbbccdd,.....}
 +
= L₁
  
Proof
 
L₁ - L₃ = L₁ ∩ L₃ʻ
 
= L₁ ∩ {∊,a,b,ab,aab,....}ʻ
 
= L₁ ∩ {(a+b)* (c+d)⁺}
 
= L₁
 
  
 
{{Template:FBD}}
 
{{Template:FBD}}
  
[[Category:Automata Theory]]
+
[[Category: Non-GATE Questions from Automata Theory]]
[[Category: Questions]]
 

Latest revision as of 11:25, 15 July 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[edit]

(1) Regular.

L₁ ∩ L₂ 
= {abcd,aabbcd,aaabbbccdd,.....} ∩ {ab, aabb, aaabbb,....} 
= ϕ

(2) CFL

L₁ - L₃ = L₁, hence CFL

Proof

L₁ - L₃ = L₁ ∩ L₃ʻ
= L₁ ∩ {∊,a,b,ab,aab,....}ʻ
= L₁ ∩ {(a+b)* (c+d)⁺}
= L₁




blog comments powered by Disqus