Answer

Correct Option: (iv) Strings with even number of $0$’s

Explanation

(iv) Even number of $0$’s — Regular

Language $L_4 = \{ w \in \{0,1\}^* \mid \#_0(w) \text{ is even} \}$ is regular. DFA with 2 states suffices:

• $q_0$: even count (start, accepting)
• $q_1$: odd count
  $\delta(q_0,0)=q_1,\;\delta(q_1,0)=q_0,\;\delta(q,1)=q$.

Regular expression: $(1^*0\,1^*0)^*1^*$ or $(1^*01^*01^*)^*$.

By Myhill-Nerode, only 2 equivalence classes.

(i) Length is prime — Not regular

$L_1 = \{ w \mid |w| \in \text{PRIMES} \}$. Use Pumping Lemma. Let $p$ be pumping length, choose $w = 0^p$ where $p$ prime, pump gives length $p + k|y|$ which will be composite for suitable $k$ (e.g., $k=p$). So not regular. Primes set not ultimately periodic.

(ii) Palindromes — Not regular

$L_2 = \{ ww^r \mid w\in\Sigma^*\}^{? }$ Classic non-regular. Requires unbounded stack to compare second half with first reversed. Pumping lemma: $w = 0^p1\,0^p$ in palindrome form fails. Needs PDA, is CFL but not regular.

(iii) Contains $ww^r$ as substring — also Not regular

$L_3 = \{ x \, ww^r \, y \mid \dots\}$ Need to remember arbitrarily long $w$ to check $w^r$ follows. This is not regular (can be shown via Myhill-Nerode with infinitely many distinct suffixes). It is context-sensitive.

Final Answer

Only (iv) is regular.