Prove the language is not regular: $L = \lbrace{ a^n b^m \mid n \le m \le 2n \lor m \le n \le 2m \rbrace}$.
I want to use the pumping lemma but I don't know which parts of the string to split up because it seems that the language's condition will always be met no matter how I split up the string. Is the language regular? If not, can I get a hint on how to split up the string?
We can write $L= \{ a^n b^m | m \le 2n \le 4m \}$.
The pumping lemma says there exists some $p$ such that if $|w| \ge p$, then we can write $w=xyz$ with $|y| \ge 1$, $|xy| \le p$ and then $x y^k z \in L$ for all $k$.
Let $w \in L$ with $|w| \ge p$. Then we see that $y$ must have the form $y=a^l$ or $y=b^l$.
If $y=a^l$ (in which case $x,z$ have the form $z=a^r b^s$ and $x=a^t$) we can choose $k$ such that $lk > 2|z|$ in which case $m\le |z|$ and $n \ge lk > 2|z| \ge 2 m$ which contradicts $w \in L$.
If $y=b^l$ (in which case $x,z$ have the form $x=a^r b^s$ and $z=b^t$) we can choose $k$ such that $lk > 2|x|$ in which case $n \le|x|$ and $m \ge lk > 2|x| \ge 2n$ which contradicts $w \in L$.
Hence $L$ is not regular.
