HQ11

Let L = {a^i b^j c^k : i >= j or i >= k }. (a [4 points]) Prove that L is CFL by constructing a CFG but (b [6 point]) complement(L) is not CFL.

For the CFG, describe the strings that each variable should generate and the justify that the strings generated by the starting variable are exactly the strings in L.



Hint: It may be helpful to use closure properties for both parts. Wait... what... closure properties for proving non-context-free?