2
$\begingroup$

(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?)

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for pointing that out. I missed the for every valid split. I guess that's the better approach. $\endgroup$ – joaoaccarvalho Jun 11 '18 at 21:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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