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?

$\endgroup$
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. $$

$\endgroup$
4
  • $\begingroup$ What if 2n - 3m <= 1000? Is this language irregular? $\endgroup$
    – hermi
    Apr 13 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
    Apr 13 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
    Apr 13 at 11:26
  • $\begingroup$ @Steven Thanks a lot. $\endgroup$
    – hermi
    Apr 13 at 11:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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