-
Consider the following languages over the alphabet ∑ = {a, b, c}.
Let L1 = { an bn cm | m , n ≥ 0 } and L2 = { { am bn cn | m , n ≥ 0 }
Which of the following are context-free languages?
I. L1 ∪ L2
II. L1 ∩ L2
-
- I only
- II only
- I and II
- Neither I nor II
- I only
Correct Option: A
The given language over Alphabets ∑ = (a, b, c) and the given language are :-
L1 = { an bn cm | n , m ≥ 0 } is a CFL
L2 = { am bn cn | n , m ≥ 0 } is also a CFL
then union of two CFL is always CFL,
L1 ∪ L2 = { an bm ck | (n = m) or (m = k), n , m ≥ 0 } is a context free language.
Intersection of two CFL is may or may not be a context free language.
L1 ∩ L2 = { an bm ck | (n = m) or (m = k) n , m ≥ 0 } or { an bn cn | n ≥ 0 } is a non context free language.
Hence, option (a) is correct.
