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