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&gt;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: 


$|y| &gt; 0$,
$|xy| \leq p$,
$\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&nbsp;$p$ such that every string longer than&nbsp;$p$ can be split in some way that can be pumped.

You've shown that there's some&nbsp;$p$ and some splitting that doesn't work but (since the language is regular), that just means you chose the wrong&nbsp;$p$ and/or the wrong splitting of your string.

In fact, the value of&nbsp;$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&nbsp;$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&nbsp;$p$, there is at least one word of length at least&nbsp;$p$ in the language such that every valid splitting as $xyz$ results in $xy^iz\notin L$ for at least one&nbsp;$i$.