Gate Practice question

Question

$L_1 = \{a^n b^n c^n \mid n\geq 1\}, L_2 = Σ^*- L_1$ is : 

• A. $\{a^i b^j c^k ; i!=j\text{ or } i!=k\} \cup (Σ^* - a^*b^*c^*)$
• B. $\{a^i b^j c^k ; i!=j\text{ and } i!=k\} \cup (Σ^* - a^*b^*c^*)$
• C. $\{a^i b^j c^k ; i!=j\text{ or } i!=k\} ∩ (Σ^* - a^*b^*c^*)$
• D. $\{a^i b^j c^k ; i!=j \text{ and }i!=k\} ∩ (Σ^* - a^*b^*c^*)$

Comments

A) should be the answer

Answer 1

L₁ = aⁿbⁿcⁿ | n>=1

L₁ = aⁱb^jc^k | i=j and j=k

L₂ = Σ*- L₁ = L₁' 

so complement of aⁱb^jc^k | i=j and j=k  will be aⁱb^jc^k | i!=j or j!=k

But complement will also include string starting with b followed by a and then followed by c. I mean strings other than the sequence a followed by b followed by c

Hence answer should be A) 

Answer 2

Option A should be correct .

(Σ* - a*b*c*) will contain all strings which will not contain (a+b+c)* .

but L2 = Σ*- L1 so we have to perform union for getting L2 bcoz it will be having string related to a,b,c