0
$\begingroup$

We have a language $$ L = \{a^n b^m \mid 2n + 3m \le 1000 \} $$

Is this language regular?

I'm trying to disprove this using the Pumping Lemma, but it didn't work.

assume I say x = $x=a^{h}$ and $y=a^{t}$ and $z =a^{n-t-h}b^m$

if I say i = 0 everything is okay because $L =a^{n-t}b^m$ and 2(n-t) + 3m <= 1000

if I say i = 2 $L =a^{n+t}b^m$ and 2(n+t) + 3m <= 1000 because I'm not sure about t value.

I think it didn't work. Is this language regular? How can I prove that?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The language is finite and, as such, it is regular (all finite languages are regular).

To see that the language is finite, notice that the maximum length of each word in $L$ is upper bounded by $500$. Indeed, if $w \in L$, and $n$ (resp. $m$) is the number of $a$s (resp. $b$s) in $w$:

$$ 2|w| = 2(n + m) \le 2n+ 3m \le 1000. $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ What if 2n - 3m <= 1000? Is this language irregular? $\endgroup$
    – hermi
    Commented Apr 13, 2021 at 11:06
  • $\begingroup$ For the original language, the pumping Lemma didn’t prove anything, for a reason. For your proposed language, the pumping Lemma should work. $\endgroup$
    – gnasher729
    Commented Apr 13, 2021 at 11:10
  • $\begingroup$ @narges Hint: you can rewrite $2n-3m \le 1000$ as $n \le 500 + (3/2)m$. Can you come up with a word in the language that can be be "pumped" enough times to violate that inequality? $\endgroup$
    – Steven
    Commented Apr 13, 2021 at 11:26
  • $\begingroup$ @Steven Thanks a lot. $\endgroup$
    – hermi
    Commented Apr 13, 2021 at 11:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.