Consider the following languages L₁ = { ww | w ∈ {a, b}* } L₂ = { wwᴿ | w ∈…
2001
Consider the following languages
L₁ = { ww | w ∈ {a, b}* }
L₂ = { wwᴿ | w ∈ {a, b}*, wᴿ is the reverse of w }
L₃ = { 0²ⁱ | i is an integer }
L₄ = { 0ⁱ² | i is an integer }
Which of the languages are regular?
- A.
Only L₁ and L₂
- B.
Only L₂, L₃ and L₄
- C.
Only L₃ and L₄
- D.
Only L₃
Attempted by 25 students.
Show answer & explanation
Correct answer: D
$L_1 = \{ww\}$ and $L_2 = \{ww^R\}$ require unbounded memory to match halves or reverses, making them non-regular. $L_3 = \{0^{2i}\}$ represents even-length strings of zeros, expressible as $(00)^*$, so it is regular. $L_4 = \{0^{i^2}\}$ involves perfect square lengths, which is non-regular by the Pumping Lemma. Consequently, only $L_3$ satisfies the regularity condition.
A video solution is available for this question — log in and enroll to watch it.