# To show that language is not regular using pumping lemma

L = $\left \{ a^{n}b^{n} : n \geq1 \right \}\cup \left\{a^{n}b^{n+2}: n \geq1\right \}$

L = $\left \{ a^{n}b^{n}(\lambda+bb) : n \geq1 \right \}$

Assuming L is a regular language. Let p be the pumping length given by the pumping lemma.

We pick our string , w = $a^{p}b^{p}(\lambda+bb)$, and $\left | w \right | > p$

$w_{i} = xy^{i}z$ , i = 0,1,2,3...

y must contain entirely of a's

suppose $\left | y \right | = k$

then when i = 3, $xy^{3}z = a^{p+3k}b^p(\lambda+bb)$

This shows that $n_{a} > n_{b}$ but no such string exists in L

This indicates that the assumption that L is regular must be false.

Hence L is not regular

I did this proof referring from some other proofs. Is it correct? and if it is correct then how to choose y so that it helps in contradiction? In this proof i choose y = $a^k$ but can chose y = $b^k$ too?

• You can't really "choose" $y$ in that sense. The pumping lemma just tells you that $y$ has to exist. It is up to you to think up every single possibility for what $y$ could be, and show that each of them is impossible. $b^k$ is a possibility, but so is $a^kb^l$. Are there others? – Arthur Mar 18 '18 at 7:48
• i don't think so – Mk Utkarsh Mar 18 '18 at 7:54
• So Arthur what modifications i need to do in this proof? – Mk Utkarsh Mar 18 '18 at 7:57