GATE 2024 Theory of computation Foundation Quiz 39

Consider languages L₁ and L₂ over alphabet Σ = {a, b}.

L₁ is known to be a some context-free language.

L₂ = {w|w contains some x as substring and x ∈ L₁}

Which of the following is true ?

Identify the correct statements among the following :

S1 : If a language is DCFL , then it satisfies prefix property

S2 : If a language satisfies prefix property , then it is DCFL.

Consider the following statements:

S₁ : {w₁cw₂ | w₁, w₂∈ {a, b}*, w₁≠ w₂} is regular language.

S₂: {aⁿ b^{n + k} | n ≥ 0, k ≥ 1} ∪ {a^{n + k} bⁿ | n ≥ 0, k ≥ 3} is DCFL.

Which of the following is true about S₁ and S₂?

Which of the following languages over the alphabet Σ = {a, b, 0} is CFL but not DCFL?

L₁ = {aⁿ 0 bⁿ│n ≥ 0}

L₂ = {0ww^R │w ∈ (a, b)*}

L₃ = {w0w^R│w ∈ (a, b)*}

L₄ = {ww^R│w∈ (a, b)*}

Consider the following statements:

S1 : Infinite union of regular languages can be context-free.

S2 : Language obtained after applying Kleen closure on a regular language will always be regular and infinite.
Which of the above statement is true?