How can the following language be regular?

Question

Lets assume the language $L=\{a^n b^m\}$

When we try proofing $L$ is regular using the Pumping lemma and say $w=xyz$ and thus for every $w=xy^iz $ , $w$ has to be $ \in L $.

now if we say $y$ only consists of $a$'s or $b$'s everything seems to be fine because there are no restrictions on how many $a$'s or $b$'s a Word from $L$ should contain.

But if I now say $y$ consists of $ab$ and pump $y$ at least once. Dont we end up with a Word that is not from the given Form of $a$'s followed by $b$'s. So how can $L$ possibly be regular

Answer 1

Welcome to MSE! This language is regular as there are no restrictions on $m$ and $n$. The Pumping Lemma is only applied if you want to show that it's not regular.

You can either provide a finite-state automaton accepting this language or a regular grammar generating this language. Both tasks are easy exercises.

Answer 2

Pumping Lemma is used to prove that a language is not regular. In this case, in order to prove that a language is regular, one could easily show that there exists a deterministic finite automaton (DFA) that accepts it.

I assume that the language you specified was

$$L=\{a^nb^m\}\quad\text{where}\ n,m\ge0$$

In that case, the automaton would look like this (double circle means that the state is also an accept state):

Answer 3

The pumping lemma says the following:

If $L$ is a regular, language, then (something about pumping strings in the language.)

Given how this implication is structured, you can use the pumping lemma in one of two ways:

1. If you have a language that you know for a fact is regular, then you can say something about how strings in the language can be pumped.
2. If you have a language that breaks the rules about pumpable strings, then it's not regular.

So in that sense, if your objective is to prove that $S = \{a^mb^n | m \in \mathbb{N}, n \in \mathbb{N}\}$ is regular, you shouldn't use the pumping lemma, since the pumping lemma doesn't enable you to do this. You can show that the language is regular by writing a regex for it (for example, $a^\star b^\star$), or by drawing a finite automaton for it, as @ampersander has done.

But let's turn to the other (good!) question you're asking here: "I'm pretty sure $S$ is regular, but it looks like it fails the condition of the pumping lemma." Let's see what the pumping lemma says in full:

• If $L$ is a regular language, then
  • there exists a natural number $p$ where
    • for any string $w \in L$ where $|w| \ge p$,
      • there are strings $x$, $y$, and $z$ where
        • $w = xyz$,
        • $|xy| \le p$,
        • $|y| \ne 0$, and
        • for any natural number $i$,
          • $xy^iz \in L$.

This claim is true for the language $S$ you've described. Specifically, you can pick your pumping length $p = 1$. If you take any string $w \in S$ whose length is at least 1, then the pumping lemma says that you can split that string $w$ apart into strings $x$, $y$, and $z$ meeting the above criteria. In particular, you can check that with $p = 1$ it has to be the case that $x$ is the empty string and $y$ is a single character. Therefore, the pumping lemma here says that for your language $S$, if you have a string in the language, you can either drop off the first character or repeat it as many times as you'd like and you're left with a string in the language. And that's true:

• If the string is of the form $a^n$, then the resulting string is all $a$'s.
• If the string is of the form $b^n$, then the resulting string is all $b$'s.
• If the string is of the form $a^{n+1}b^m$, then the resulting string consists of some number of $a$'s followed by some number of $b$'s.

Your original argument was concerned about what would happen if the string to pump consisted of a mix of $a$'s and $b$'s, which is a legitimate thing to initially be worried about. However, by picking the pumping length to be 1, we can dodge this entirely by forcing the string to repeat to consist of just a single character.

Hope this helps!