Prove the following language is not regular using the pummping lemma
$L = \{a^nb^m \mid 0\leq n<m\}$
I tried solving this problem what I don't think I was able to reach an accurate proof. But this is what I have so far:
Let s in L be given by s = anbn+1. By the pumping lemma, there must be some decomposition s = xyz where s = xyiz in L for every i>=0. Since |xy|<=n and |y|>0, the string y has to only consist of b's. So removing the string y decreases the number of b's in s. s has only one more b than a. Therefore xz can't have more b's than a's and is not in L. This leads to a contridiction and so L is not regular.
Best Answer
Your proof is on the right track. These pumping lemma questions end up being proof by contradiction. So, we first must assume something, then contradict it. Here we will assume the $L$ is regular, then get a contradiction. Here is a detailed proof below. The basic idea is we choose a string long enough so that the $y$ in the pumping lemma only had the letter $a$ in it. We then pump the $y$ to reach a contradiction.
Proof) Assume $L$ is regular. By the pumping lemma there exists a pumping length $p$. Now take the string $a^pb^{p+1} \in L$ (note this is essentially the same string you choose, but here we first made an assumption about the pumping length). Then write $a^pb^{p+1} = xyz$ with $|xy| \leq p$ and $|y| > 0$. This means $xy = a^q$ for some $0 < q \leq p$, that is $xy$ consists only of of the letter $a$. In particular $y = a^r$ for some $1 < r \leq q$ (note here this is different from your proof, $y$ consists of only $a$ so we will pump "up" instead of "down"). Thus $xy^2z = a^{p+r}b^{p+1} \in L$ by the pumping lemma, but this is a contraction to the definition of our language $L$ since $p+r \geq p+1$. Therefore the language $L$ is not regular.