GATE 2024 Theory of computation Foundation Quiz 90

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₂?