Prove that this language is regular or not

144 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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$?