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:
(a)-(ii); (b)-(iii); (c)-(i)
For (a), recursive languages are closed under complement, and their union with a recursively enumerable language is recursively enumerable: (ii). For (b), every context-free language is decidable; recursive languages are closed under complement and union, so the result is recursive: (iii). For (c), \(L_1^*\) is regular, and intersecting a regular language with a context-free language remains context-free: (i). Thus a–ii, b–iii, c–i.
Important Questions from Context Free Languages - Teaching
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?
Consider the following statements with respect to the language L = {a nb n|n≥ 0}
S 1: L 2is context free language
S 2: L kis context-free language for any given k ≥ 1
S 3: L̅ and L* are context free languages
Which one of the following is correct?
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 ?
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
