Clarification on Lemma problem

62 Views Asked by At

I have trouble understanding this question. I have no idea where to start.

Let $A$ be the set of palindromes over $\{a, b\}$.

Suppose you are trying to prove that $A$ is not regular using the pumping lemma. Your proof starts (correctly) like this: Suppose for a contradiction that $A$ is regular. Let $p$ be the pumping length given by the pumping lemma. Now you have to choose string $s$. For each choice of $s$ below, you have to state whether or not this choice of $s$ can be used to finish the proof that $A$ is not regular.

(a) $s=b^pa^pb^p$. Can this $s$ be used? Briefly explain your answer.

Thanks.

1

There are 1 best solutions below

0
On

Yes, it can. Assume we can write $s=uvw$ with $|uv|\le p$ and $v$ nonempty. Then $uv$ is just a sequnce of $b$'s. By the pumping lemma we should have $uw\in A$, but $uw=b^xa^pb^p$ with $x=p-|v|<p$ is ("obviously") not a palindrome.