Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?

Question

The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the pumping lemma with constant $N$ for a substring $\alpha\beta = a^{3}b^{t},|\alpha\beta| \leq N$, let $\alpha = a$ and $\beta = a^{2}b^{t}$, therefore $\gamma = b^{N-t}$, and when $k = 0$, $\sigma = \alpha \beta^{0} \gamma = \alpha \gamma = ab^{N-t}$, which doesn't belong to $\mathcal{L}$ and the language isn't regular.

So, is really the regex equal to $\mathcal{L}$? or am I pumping wrong?

Answer 1

You are making a classical mistake in applying the pumping lemma. The pumping lemma states that each word $w$ of length at least $N$ in the language (where $N$ is the number of states in the minimal DFA for the language) can be decomposed as $w = xyz$, where $|xy| \leq N$, $|y| \geq 1$, and $xy^i z$ is in the language for all $i$. You don't get to choose this partition! The lemma just states that there is some partition. Taking as an example your word $a^3 b^t$, since $N = 6$ (indeed, the minimal DFA for the language has $6$ states), we can always choose $x = a^3$ and $y = b$, and then $xy^i z = a^3 b^{t+i-1}$ which is always in the language (since $t \geq 3$).

When you use the pumping lemma to prove that a language is not regular, you don't know $N$, and so you have to start by taking $N$ to be arbitrary, and run the proof from there. What you are in effect showing is that for each $N$, there is no DFA accepting the language with at most $N$ states.