0
$\begingroup$

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<p$.

Am I correct about this? Thanks for your help !

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ How do you know $j+k<5+p$, all I have is $j+l \leq p$ and $l > 0$ ? $\endgroup$
    – user145509
    Commented Nov 21, 2021 at 12:08
  • $\begingroup$ Your hypotheses were $j + l + k = 5 + p$ and $l > 0$, then $j+k = 5 + p - l < 5 + p$. $\endgroup$
    – Nathaniel
    Commented Nov 21, 2021 at 12:25
  • $\begingroup$ How does $j + k < 5 + p$ suffice to prove that this language is not regular, I think only $j + k < p$ can prove it. $\endgroup$
    – user145509
    Commented Nov 21, 2021 at 12:51
  • $\begingroup$ 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$). $\endgroup$
    – Nathaniel
    Commented Nov 21, 2021 at 13:59
  • $\begingroup$ 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. $\endgroup$
    – user145509
    Commented Nov 21, 2021 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.