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?
Statement I is true and Statement II is false
Context-free languages are closed under homomorphism: replacing terminals by fixed strings preserves context-freeness. They are not closed under complement. Otherwise closure under union and De Morgan’s law would imply closure under intersection, which CFLs do not have.
Important Questions from Context Free Languages - Teaching
The language L = {a ib c i | i ≥ 0} over the alphabet {a, b, c} is :
Consider the following languages :
L 1 = {a m b n | m ≠ n}
L 2 = {a m b n | m = 2n + 1}
L 3 = {a m b n | m ≠ 2n}
Which one of the following statement is correct ?
Which of the following statements is true ?
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
Match List-I with List-II:
Where L1: Regular language
L2: Context-free language
L3: Recursive language
L4: Recursively enumerable language
List-1
List-2
(a) L' 3 U L 4
(i) Context-free language
(b) L' 2 U L 3
(ii) Recursively enumerable language
(c) L 1* ∩ L 2
(iii) Recursive language
Choose the correct from those given below:
