Question

Which of the following languages is regular?
(A) {WW^R |W belongs to {0,1}^+}
(B) {WW^RX | X,W belongs to {0,1}^+}
(C) {WXW^RX | X,W belongs to {0,1}^+}
(D) {XWW^RX | X,W belongs to {0,1}^+}

Answer 1

Answer on Question#38161 – Math - Other

(C) $\{w x w^{R} \mid x, w \in (0,1)^{+}\}$

This is merely the language where the strings are either $0w0$, $1w1$ where $w$ is any string in $\{0,1\}^*$. The remaining are standard palindrome languages:

for (A) intersect with $0^+110^+$ and apply the pumping lemma;

for (B) intersect with $0^+110^+1$ and apply the pumping lemma;

for (D) intersect with $10^+110^+$ and apply the pumping lemma.