Project ForgeConsider the following languages.
L₁ = {wxyx | w,x,y ∈ (0+1)⁺}
L₂ = {xy | x,y ∈ (a+b)*, |x|=|y|, x≠y}Which one of the following is TRUE?
- L₁ is regular and L₂ is context-free.
- BL₁ is context-free but not regular and L₂ is context-free.
- CNeither L₁ nor L₂ is context-free.
- DL₁ is context-free but L₂ is not context-free.
Explanation
L₁ turns out to equal simply 'all binary strings of length ≥ 4' — over a 2-symbol alphabet, any string of length ≥4 can always be decomposed as w·x·y·x with all three parts non-empty (a repeated single-symbol suffix/prefix pattern can always be found by pigeonhole over just 2 symbols), making L₁ a plain length-threshold language, which is regular. L₂ — all strings formed by concatenating two equal-length, UNEQUAL halves — is a known context-free language: a PDA can nondeterministically guess a mismatch position, push the first half's symbols up to that point, then pop-and-compare to verify a genuine mismatch at the guessed position while matching lengths overall (this is the classical complement-style construction showing 'x≠y' variants of the ww-family are context-free even though {ww} itself is not). So L₁ is regular and L₂ is context-free.
Source: GATE CS 2020 (2020)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.