0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Arthur Mar 18 '18 at 7:48
  • $\begingroup$ i don't think so $\endgroup$ – Mk Utkarsh Mar 18 '18 at 7:54
  • $\begingroup$ So Arthur what modifications i need to do in this proof? $\endgroup$ – Mk Utkarsh Mar 18 '18 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.