# Why is $L := \{b^2a^nb^ma^3|m,n \geq 0\}$ a regular language?

(Pre-note: I'm learning Theory of Computation on my own, so bear with me if I'm saying something wrong/stupid.)

Why is $L := \{b^2a^nb^ma^3\mid m,n \geq 0\}$ a regular language?

This question appeared in a problem set, whose answer is the following:

The language is regular. Indeed, it can be expressed by the regular expression $\mathcal{R} := b^2a^*b^*a^3$.

However, I (think I) can find a contradiction using the pumping lemma.

Consider $s = xyz = b^2 a^{p-3}b^1a^3$. (I assume one can take a specific string from the language.)

Clearly, $\forall p>3, s \in L$, and $|s|\geq p$, the pumping length.

Take $x = b^2$, $y=a^{p-3}b^1$, $z = a^3$. (I assume one can take specific values for $x, y, z$).

The pumping lemma says that if $L$ is regular, there is a number $p$ (pumping length) where, if $s \in L \wedge |s| \geq p$, $s$ may be split into three pieces, $s = xyz$, satisfying the conditions:

1. $|y| > 0$,
2. $|xy| \leq p$,
3. $\forall i \geq 0, xy^iz \in L$.

Conditions (1) and (2) are fulfilled. As for condition (3) ...

$xy^iz = b^2(a^{p-3}b^1)^ia^3$

For $i=0$, $xy^0z = b^2a^3 \in L$.

However, for $i = 2$, $xy^2z = b^2(a^{p-3}b)(a^{p-3}b)a^3$, and taking $p=4$, it is clear that $xy^2z = b^2ababa^3 \notin L$.

Thus, we find a contradiction (because $xy^2z \notin L$) and $L$ is not regular.

(Could you help understand where is the fallacy here?)

The pumping lemma says that there is some $p$ such that every string longer than $p$ can be split in some way that can be pumped.
You've shown that there's some $p$ and some splitting that doesn't work but (since the language is regular), that just means you chose the wrong $p$ and/or the wrong splitting of your string.
In fact, the value of $p$ is the number of states in the smallest automaton that accepts the language (plus one, I think). The language you give is going to need about eight or nine states, so your $p$ was too small. However, that doesn't much matter. Given the string $b^2a^{p-3}ba^3$, we can split it as $x=b^2$, $y=a$, $z= [\text{the rest}]$ and now $xy^iz\in L$ for all $i\geq 0$, as the pumping lemma claims. Sure, some other splits don't work, but that one does and the lemma just claims that some split works.
Remember: to show that a language is non-regular using the pumping lemma, you need to show that, for every $p$, there is at least one word of length at least $p$ in the language such that every valid splitting as $xyz$ results in $xy^iz\notin L$ for at least one $i$.