I had an exam today and the professor gave us the following problem:

Let $L = \{a^nb^m : n|2m \}$. Prove that $L$ is not regular.

Ok this sounds easy. Here is my solution: Assume opposite -- $L$ is regular. Then by the pumping lemma there exist decomposition $xyz$ of string $s \in L$ such that $|y| \ge 1$, $|xy| \le p$, where $p$ is the pumping lemma length and $xy^iz \in L$ for all $i \ge 0$.

Setting $ s = а^pb^{2p}$, clearly $s$ is in $L$. Then $s = xyz$, and from the condition $|xy| \le p$ it follows that $y$-part consist only of $a's$.

Here is my problem: I say -- let $y = a$, choose $i = p+1$, then it should $xy^{p+1}z= a^{2p+1}b^p \in L$ -- a contradiction, so $L$ is not regular.

Is it my proof correct?

Many thanks to all, Ivan

  • 2
    $\begingroup$ Don't you need a $z$ somewhere in there? What does $xy^{p+1}x$ have to do with anything? And you seem to indicate you know the length of $y$, when all you know is the maximum length of $y$.... $\endgroup$ Jul 9 '13 at 15:01
  • $\begingroup$ Yes sorry. I mean $xy^{p+1}z$. $\endgroup$ Jul 9 '13 at 15:19

You've made assumptions about the length of $x,y,z$ if you know exactly what $xy^{p+1}z$ is.

You've shown that $x=a^k, y=a^\ell, z=a^{p-k-\ell}b^{2p}$ where $p\geq k+\ell$, $\ell>0$. Then can $xy^2z$ be in $L$?

  • $\begingroup$ Hello @Thomas Andrews. If we put $x=a^{p-1}$, $y=a$ and $x = b^{2p}$. Then we'll have $s = xy^{p+2}z$ and $s$ will not be in $L$. Is this will work? $\endgroup$ Jul 9 '13 at 15:28
  • $\begingroup$ We don't know that $x=a^{p-1}$. It's possible for $x$ to be an empty string. You can't just choose any $x,y,z$, the pumping lemma only asserts that some $x,y,z$ has this property. $\endgroup$ Jul 9 '13 at 15:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.