Gate2017 cs Q49

0. Consider the following languages over the alphabet ∑= {a,b,c}. Let L₁ = {aⁿ bⁿc^m | m, n >= 0 } and L₂ = {a^mbⁿcⁿ| m, n >= 0}.
Which of the following are context-free languages ?
I. L₁ ∪ L₂
II. L₁ ∩ L₂

Answer
Comment
Array

Option : A
Explanation :
Union of context free language is also context free language.
L₁ = { aⁿ bⁿ c^m| m >= 0 and n >= 0 } and
L₂ = { a^m bⁿcⁿ| n >= 0 and m >= 0 }
L₃ = L₁ ∪ L₂ = { aⁿbⁿc^m∪ a^mbⁿcⁿ| n >= 0, m >= 0 } is also context free.
L₁ says number of a’s should be equal to number of b’s and L₂ says number of b’s should be equal to number of c’s. Their union says either of two conditions to be true. So it is also context free language.
Intersection of CFG may or may not be CFG.
L₃ = L₁ ∩ L₂ = { aⁿbⁿcⁿ| n >= 0 } need not be context free

Forgot your password?

I agree with the Terms.