When using the Pumping lemma, how do I deal with different cases of y?

Question

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$

I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know how to handle different cases of y in pumping lemma.

Answer 1

To review, the PL says that if a language $L$ is regular, then there is an integer $p$ such that for any string $s\in L$ of length, $|s|\ge p$ we can write $s=xyz$ with

1. $|y|>0$
2. $|xy|\le p$
3. $xy^iz\in L$, for all integers $i\ge 0$

Assume your language is regular and select the string $ab^pab^pab^p$ to pump. Now, where can $y$ live? Since $|xy|\le p$ you know that $xy$ lives in the first $p$ or fewer characters of $s$, namely $xy=ab^k$ for some $k<p$. We then have two possibilities for $y$: it either contains the first $a$ or it doesn't, so we have two possibilities, where I've colored the string y: $$\begin{array}{c} (\color{red}{ab\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)\\ (a\color{red}{b\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b) \end{array}$$

Then for each case we argue thus:

1. $y$ is $ab^n$ (i.e., $x=\epsilon$), with $0\le n\le p$. Then $xyz=ab^pab^pab^p=(ab^n)b^{p-n}ab^pab^p$. Then $xy^2z=(ab^n)(ab^n)b^{p-n}ab^pab^p=ab^nab^pab^pab^p$. It's not difficult to see that this cannot be in $L$, so we've reached a contradiction.
2. $y$ is $b^n$ (i.e., $x=ab\dotsc b$). Then $xy^2z = ab^pb^nab^pab^p$ and again, this string can't be in $L$.

In all cases, we reach a contradiction, so our initial assumption, that $L$ was regular, was false.

By the way, it's easier to use the candidate string $a^pba^pba^pb$, since for this we only have one possibility for where $y$ could live, namely among the first string of a's.