Consider the following statements about Context Free Language (CFL):
Statement I: CFL is closed under homomorphism.
Statement II: CFL is closed under complement.
Which of the following is correct?
1.Statement I is true and Statement II is false ✓ Correct
2.Statement II is true and Statement I is false
3.Both Statement I and Statement II are true
4.Neither Statement I nor Statement II is true
Solution
CFL's are closed under union, concatenation, and Kleene closure. Also, under reversal, homomorphisms and inverse homomorphisms.
But Context-free languages are not closed under:
- Intersection − If L1 and L2 are context free languages, then L1 ∩ L2 is not necessarily context free.
- Complement − If L1 is a context free language, then L1' may not be context free.
Hence only Statement I is True.