Consider the following statements about Context Free Language (CFL) :…
2022
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 ?
- A.
Statement I is true and Statement II is false
- B.
Statement II is true and Statement I is false
- C.
Both Statement I and Statement 𝐼𝐼 are true
- D.
Neither Statement I nor Statement II is true
Attempted by 78 students.
Show answer & explanation
Correct answer: A
Answer: Statement I is true; Statement II is false.
Reason:
Closure under homomorphism (sketch): Given a context-free grammar G that generates L and a homomorphism h, construct a grammar G' that generates h(L) by replacing each occurrence of a terminal a in productions of G with a small subgrammar that generates the string h(a). Equivalently, simulate G while expanding terminals according to h; this yields a context-free grammar for h(L), so CFLs are closed under homomorphism.
Not closed under complement (counterexample): Let L = { a^n b^n | n ≥ 0 } over the alphabet {a,b}. L is context-free, but the complement of L over {a,b}* is not context-free. Therefore, context-free languages are not closed under complement in general.
Note: Deterministic context-free languages are closed under complement, but this does not extend to all context-free languages.
A video solution is available for this question — log in and enroll to watch it.