You do not have permission to edit this page, for the following reason:

The action you have requested is limited to users in one of the groups: Users, Administrators.


You can view and copy the source of this page.

Return to Automata qn 1.

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