Consider the following statements about context-free languages (CFL):
Statement I: CFLs are closed under homomorphism.
Statement II: CFLs are closed under complement.
Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: A. Statement I is true and Statement II is false
Explanation
CFLs are closed under homomorphism (substitute terminals in the grammar) but not under complement.More Theory of Computation and Compilers questions
- Match List – I with List – II. List – I (Propositions) (A) P ∧ (P → Q) (B) ¬(P ∨ Q) → (P ∧ Q) (C) P → Q (D) P ∨ (Q ∧ R) List – II (Disjunct…
- Overfitting is expected when we observe that?
- Mr X designed open source software which must comply with some criteria. Choose the false statement in respect of above. (A) No restriction…
- Match List (I) with List (II): List I A. Product Complexity B. Structured System Analysis C. Coupling & cohesion D. Symbolic Execution List…
- Suppose a cloud contains software stack such as Operating System, Application software, etc. This model is referred as _____ model.
- Which one of the following is not typically provided by Source Code Management Software?