# Is the language $L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$ regular or not regular?

I'm trying to understand how to prove a language is regular or not regular, for example this language: $$L=\{a^nb^m:n,m\in\mathbb{N}\land n-m=5 \}$$ Is this language regular or not?

My solution
Using the pumping lemma, I can choose a string with a pumping length $$p$$ like: $$w=a^{5+p}b^p$$, then $$x = a^j, y=a^l$$ and $$z=a^kb^p$$ such that $$j+l+k=5+p$$, I will pump with $$i=0$$, so the string will be $$xz=a^{j+k}b^p$$, this is not regular because $$j+k.

If $$L$$ is regular, then so is $$L\{b\}^5$$. You can conclude by studying $$L\{b\}^5$$ (which is a very classic language).

Also in your proof, you cannot guarantee that $$j+k < p$$, but $$j+k < 5 + p$$ is enough.

• How do you know $j+k<5+p$, all I have is $j+l \leq p$ and $l > 0$ ?
– user145509
Nov 21 '21 at 12:08
• Your hypotheses were $j + l + k = 5 + p$ and $l > 0$, then $j+k = 5 + p - l < 5 + p$. Nov 21 '21 at 12:25
• How does $j + k < 5 + p$ suffice to prove that this language is not regular, I think only $j + k < p$ can prove it.
– user145509
Nov 21 '21 at 12:51
• Because $xz=a^{j+k}b^p$ and $j+k<5+p$, so $xz$ is of the form $a^nb^m$ with $n-m < 5$, so $xz$ is not in $L$ (remember the definition of the language $L$). Nov 21 '21 at 13:59
• I know the definition, but the problem is normally I see people compare 2 exponents of $a$ and $b$, in this case which is $j+k$ and $p$, if it's not equal then I can conclude that the string is not in $L$, I just find it confusing that why did you use $5+p$ instead of $p$ (the exponent of $b$) to prove.
– user145509
Nov 21 '21 at 14:36