(Solution)
 
(10 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 28: Line 30:
 
  = {abcd,aabbcd,aaabbbccdd,.....}  
 
  = {abcd,aabbcd,aaabbbccdd,.....}  
 
  = L₁
 
  = 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₃ = {abcd,aabbcd,aaabbbccdd,.....} - { ∊,a,b,ab,aab,.....} 
= {abcd,aabbcd,aaabbbccdd,.....} 
= L₁




blog comments powered by Disqus