1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ The languages are the same. $\endgroup$ – Yuval Filmus Apr 28 '13 at 4:31
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Certainly the partition is out of my control! thanks again @YuvalFilmus. Moreover is very interesting (not for the class heh) what I accidentaly showed, excellent complement of the answer. $\endgroup$ – Alejandro Sazo Apr 28 '13 at 4:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.