Difference between revisions of "Automata qn 1"

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

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

@@ 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\}$
@@ Line 5: / Line 7: @@
 $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
@@ 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
-===Solution===
+==={{Template:Author|Arjun Suresh|{{arjunweb}} }}===
 (1) Regular.
   L₁ ∩ L₂
@@ Line 23: / Line 25: @@
 (2) CFL
-L₁ - L₂ = L₁, hence CFL
+ L₁ - L₃ = L₁, hence CFL
+ Proof,
+ L₁ - L₃ = {abcd,aabbcd,aaabbbccdd,.....} - { ∊,a,b,ab,aab,.....}
+ = {abcd,aabbcd,aaabbbccdd,.....}
+ = L₁
-Alternatively,
- L₁ - L₃ = L₁ ∩ L₃ʻ
- = L₁ ∩ {∊,a,b,ab,aab,....}ʻ
- = L₁ ∩ {(a+b)* (c+d)⁺}
- = L₁
 {{Template:FBD}}
-[[Category:Automata Theory]]
+[[Category: Non-GATE Questions from Automata Theory]]
-[[Category: Questions]]