To show that language is not regular using pumping lemma

30 Views Asked by At

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?