Given below are two statements Statement I: The family of context free…
2021
Given below are two statements Statement
I: The family of context free languages is closed under homomorphism Statement
II: The family of context free languages is closed under reversal
In light of the above statements, choose the correct answer from the options given below
- A.
Both Statement I and Statement II are true
- B.
Both Statement I and Statement II are false
- C.
Statement I is true but Statement II is false
- D.
Statement I is false but Statement II is true
Attempted by 71 students.
Show answer & explanation
Correct answer: A
Answer: Both Statement I and Statement II are true.
Reasoning and constructive sketches:
Statement I — Closure under homomorphism: If L is a context-free language generated by a context-free grammar G and h is a homomorphism, then h(L) is context-free. Sketch of construction: for each terminal a with h(a)=w (a string over the target alphabet), introduce a small sequence of new nonterminals and productions that derive w, and replace occurrences of a in G's productions by that sequence of nonterminals. This yields a new context-free grammar that generates exactly h(L).
Statement II — Closure under reversal: If L is context-free with grammar G, construct a grammar G' by replacing each production of the form A → X1 X2 ... Xn with A → Xn ... X2 X1 (i.e., reverse the right-hand side). Then G' generates the set of reversals of strings generated by G, so the reversal of a context-free language is context-free.
Thus both closure properties hold, so both statements are true.
A video solution is available for this question — log in and enroll to watch it.