2
$\begingroup$

I have a language as follows: $L = \{ ww^Rw \mid w \in \{a,b\}^*\} $

I believe that the language is not regular, since designing a DFSM for it is not possible. To prove that the language is not regular, I decided to use the pumping lemma.


Assume $L$ is regular.

Let $w = a^mb^ma^m$

Ex) $a^mb^ma^ma^mb^ma^ma^mb^ma^m$

By the pumping lemma, $s = xyz$ where $y$ is not empty and $|xy| \leqslant m$.

Because $|xy| \leqslant m$, $xy$ must consist of just $a$'s.

Since $y$ is not empty, $y$ is one or more $a$'s.

Suppose $|y| = k$. (So $y = a^k$)

We see that $a^mb^ma^ma^mb^ma^ma^mb^ma^m$ would not exist in L, since $w^R$ would no longer represent the reverse of $w$ - there would be more than $m$ $a$'s in $w$.

Therefore, $L$ is not regular.


Is this correct? I am new to applying the pumping lemma.

$\endgroup$
1
$\begingroup$

There are two inaccuracies in your argument. First, you should specify the pumping length at the beginning of your argument:

Assume $L$ is regular and let $m$ be the pumping length of $L$.

But more importantly, you never used the third condition of the pumping lemma: for all $i \geqslant 0$, $xy^iz \in L$. You just have written that $a^mb^ma^ma^mb^ma^ma^mb^ma^m = xyz$, with say $x = a^s$, $y = a^k$ (with $k > 0$ and $k+s \leqslant m$) and $z = a^{m-(s+k)}b^ma^ma^mb^ma^ma^mb^ma^m$.

Hint. Can you show now that $xy^2z$ is not in $L$?

$\endgroup$
2
  • $\begingroup$ Could I say that xy^2z = a^(m+k)b^ma^m but xy^2z must be in L by the pumping theorem. Then just say therefore L is not regular. $\endgroup$ Oct 21 '16 at 7:01
  • 1
    $\begingroup$ Yes, your proof is now complete. $\endgroup$
    – J.-E. Pin
    Oct 21 '16 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.