Difference between revisions of "Automata qn 1"

Revision as of 21:48, 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

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

@@ 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\}$
-$L_3 = {(a+b)^*}
+$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₁
+{{Template:FBD}}
+[[Category:Automata Theory]]
+[[Category: Questions]]