Question : Show that the language wb^|w| (any string w over {a,b} followed by as many b’s as the size of w) is not regular.
My proof (as per my opinion) is that: We suppose that w is a regular language so (w^2)b^|w| would also be regular and we will use pumping lemma that this is not regular by contradiction.
So, our language would be: If
- W=1: ab
- W=2: aabb
- W=3: aaabbb (That's where I am confused at If I am doing if rightly)
then, X = XYZ where, |XY|<=n and |Y|>0,
Let's take X = a, Y=ab, Z=b, and then for XY^iZ, we will take i = 3.
Then our X = aabababb. Which wouldn't be available in our language. Hence proved by contradiction.
That's what I think The answer is but I am bit doubtful. Any comments would be helpful.
Let $L=\left\{wb^{|w|}:w\in\{a,b\}^*\right\}$; you want to prove that $L$ is not regular. This can easily be done with the pumping lemma, but what you’ve done doesn’t make much sense.
First, there is no reason to bring in the language $\left\{w^2b^{|w|}:w\in\{a,b\}^*\right\}$, and it is not at all clear that this language would be regular if $L$ were. Next, it is not at all clear what you are doing with $W$: you’ve given us no explanation of the bulleted lines. Finally, if $X=XYZ$, then $Y=Z=\epsilon$, the empty word, which I’m sure is not what you intended.
To use the pumping lemma properly, suppose that $L$ is regular, let $p$ be the pumping length, and let $u=a^pb^p$; setting $w=a^p$, we can see that $u\in L$. The pumping lemma now tells us that $u$ can be decomposed as $u=xyz$, where $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for each integer $k\ge 0$.
Since $|xy|\le p$, $xy$ must be contained in the $a^p$ part of $u$. Thus, there are integers $r\ge 0$ and $s\ge 1$ such that $x=a^r$, $y=a^s$, and $r+s\le p$. Of course this means that $z=a^{p-r-s}b^p$. Then for each $k\ge 0$ we have
$$xy^kz=a^ra^{ks}a^{p-r-s}b^p=a^{p+(k-1)s}b^p\in L\,.$$
But $p+(k-1)s>p$ whenever $k>1$, and in particular, $xy^2z=a^{p+s}b^p$. If we can show that this word is not in $L$, we’ll have a contradiction proving that $L$ is not regular after all.
To show that $a^{p+s}b^p\notin L$, we have to show that there is no $w\in\{a,b\}^*$ such that $a^{p+s}b^p=wb^{|w|}$. Suppose that $a^{p+s}b^p=wb^{|w|}$; there are only $p$ $b$s in $a^{p+s}b^p$, so $|w|\le p$. But then
$$\left|wb^{|w|}\right|=2|w|\le 2p<2p+s=\left|a^{p+s}b^p\right|\,,$$
since $s\ge 1$, so in fact $wb^{|w|}$ cannot be equal to $a^{p+s}b^p$, and $a^{p+s}b^p$ cannot be in $L$. This is the contradiction that we wanted, showing that $L$ is not regular.