is a^(m)b^(n) | m >= 99 and n>=999 a regular language?

65 Views Asked by At

I've been stuck on this problem for a while. Say we have the following language?

a^(m)b^(n) | m >= 99 and n>=999

I'm trying to use the pumping lemma to prove that it isn't regular because intuitively to me it seems like it isn't. Can anyone please give me a concrete answer?

3

There are 3 best solutions below

0
On

The language is the language accepted by the regular expression /aa...aa*bb...bb*/ where the number of a and b hiding in the dots is adjusted to needs.

0
On

The language is regular here is a regular expression that fits for the language:

$$a^*(\underbrace{aa\dots}_{\text{99 times}})b^*(\underbrace{bbb\dots}_{\text{999 times}})$$

0
On

A grammar would be $S\to a^{99}Ab^{999}B$, $A\to a$, $A\to aA$, $B\to b$, $B\to bB$.

This proves it is regular.

(Probably a more specific answer could be given if you could tell what programming language you are using (because your question has a strong smell of regular expression in context of programming languages).)