Question 61

1. Analyze $L_1 = \{w x w^R \mid w, x \in \{a, b\}^+ \text{ and } |w|, |x| > 0\}$:
   Since $|w| \ge 1$, we can choose $w$ to be a single symbol ($a$ or $b$).

• If $w = a$, then $w^R = a$, producing strings of the form $a x a$ where $x \in \{a, b\}^+$.
• If $w = b$, then $w^R = b$, producing strings of the form $b x b$ where $x \in \{a, b\}^+$.
  Conversely, any string in $\{a, b\}^+$ that starts and ends with the same symbol and has length $\ge 3$ can be written as $w x w^R$ by setting $w$ to the first symbol (so $|w| = 1$).
  Thus, $L_1$ is simply the regular language:

Since it is expressed by a regular expression, $L_1$ is regular.

2. Analyze $L_2 = \{a^m b^n \mid m \neq n \text{ and } m, n > 0\}$:
   Recognizing whether $m \neq n$ requires infinite memory to compare the count of $a$'s and $b$'s. By the Pumping Lemma, $L_2$ is not regular.

3. Analyze $L_3 = \{a^p b^q c^r \mid p, q, r \ge 0\}$:
   This language is generated directly by the regular expression $a^* b^* c^*$, so $L_3$ is regular.

Thus, $L_1$ and $L_3$ only are regular (option A).