1

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

azimut
  • 22,696
user2564944
  • 13

1 Answers1

0

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$?

Thomas Andrews
  • 177,126
  • 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? – user2564944 Jul 09 '13 at 15:28
  • 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. – Thomas Andrews Jul 09 '13 at 15:30