Statement I: CFLs are closed under homomorphism. Statement II: CFLs are closed under complement. Which 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 each terminal in the grammar) but not under complement.
More Theory of Computation and Compilers questions
- Assertion (A): A load-and-go assembler avoids the overhead of writing the object program out and reading it back in. Reason (R): This can b…
- Which of the following languages are not regular? A. L = {(01)ⁿ0ᵏ | n > k, k ≥ 0} B. L = {cⁿbᵏaⁿ⁺ᵏ | n ≥ 0, k ≥ 0} C. L = {0ⁿ1ᵏ | n ≠ k}
- Any string of terminals generated by the CFG S → XY, X → 0X | 1X | 0, Y → Y0 | Y1 | 0 (S is the start symbol)
- Let L1 = {0ⁿ1ⁿ0ᵐ | n ≥ 1, m ≥ 1}, L2 = {0ⁿ1ᵐ0ᵐ | n ≥ 1, m ≥ 1}, L3 = {0ⁿ1ⁿ0ⁿ | n ≥ 1}. Which are correct? A. L3 = L1 ∩ L2. B. L1 and L2 are…
- Given below are two statements Statement I: The family of context free languages is closed under homomorphism Statement II: The family of c…
- What is the minimum number of states required to the finite automaton equivalent to the transition diagram given below?