Consider the following statements with respect L = {anbn ∣ n ≥ 0} to the language
S : L2 1 is context free language
S : Lk 2 is conext-free language for any given k ≥ 1 ¯¯¯
S : L L∗ 3 and are context free languages Which one of the following is correct? S S
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: D. 1 2 and 3
Explanation
For L = {aⁿbⁿ}, L² and Lᵏ are CFL (concatenation), L* is CFL (star), and L's complement is CFL since L is a deterministic CFL. All three statements hold.
More Theory of Computation and Compilers questions
- Consider the following languages : L = {anbncm} ∪ {anbmcm}, n, m ≥ 0 1 L = {wwR ∣ w ∈ {a, b}*} 2 Where R represents reversible operation. W…
- Let G=(V, T, S, P) be any context-free grammar λ without any -productions or unit productions. Let K be the maximum number of symbols on th…
- Consider the following language families : L ≡ The context - free languages 1 L ≡ The context - sensitive languages 2 L 3 ≡ The recursively…
- Consider the following statements : S 1 : These exists no algorithm for deciding if any M M two Turing machines 1 and 2 accept the same lan…
- Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}; C = {00, 001, 1000} and D = {0, 11, 011}. Which pairs have a Post correspondence…
- Which data structure is used by the compiler for managing variables and their attributes?