Use the pumping lemma to show the language is not regular

Question

I can use the pumping lemma to prove simpler examples, but i'm finding this problem rather complex partly due to the notation.

Can anyone explain how I would do this problem:

For any string $s$ in $\{a, b\}^*$, let $n_a(s)$ be the number of a’s in s, and let $n_b(s)$ be the number of b’s in s. Let L over {a, b} be given by $L = \{x \in \{a, b\}^* | n_b(x) = n_a(x)^2 \space \text{and} \space x \notin ((a^∗b^∗) ∪ (b^∗a^∗))\} $. Prove, using the pumping lemma for regular languages, that the language L is not a regular language

I know we suppose that it is regular then by the pumping lemma it has to satisfy the properties of the pumping lemma for regular languages.

Hence, we need to find a decomposition and break it by pumping this decomposition which is no longer in the language forming a contradiction by hypothesis. However, I fail to see the decomposition or what to pump....

Answer 1

Assume $L$ is regular, and let $p$ be as in the pumping lemma.

Note that $s = a^pb^{(2p)^2}a^p\in L$. Now, by the pumping lemma, we have a decomposition of $s = xyz$. As $|xy|\leq p$, we must have that $y\subseteq a^p$, Say that $y = a^k$ for some $k\leq p$ (and by the property that $|y|>0$, we have that $k\geq 1$).

Then, we have that: $$s = \underbrace{a^{p-k}}_x\underbrace{a^k}_y\underbrace{b^{4p^2}a^p}_z$$ Again, by the pumping lemma, we have that $L\ni xz = a^{p-k}b^{4p^2}a^p$. But, we have that $n_a(xz) = 2p-k$, and $n_b(xz) = 4p^2$, but $n_a(xz)^2 = 4p^2-4pk+k^2\neq 4p^2 = n_b(xz)$, where the lack of equality holds because $1\leq k\leq p$, as stated before.

So, we have a contradiction to the pumping lemma, so $L$ isn't regular.

This all is entirely standard, and the only "trick" is picking the right string $s$. A few tips for this:

1. $s$ will generally need to depend on $p$ in some way so it's "long enough to be pumped"

2. You'll want to carefully choose the first $p$ characters of $s$. If it can all be one character repeated (like in this case we had $a^p$), it makes determining what $y$ is much easier, and you can do the proof with a single case.

3. Besides that, you want to choose the rest of the string so $s\in L$, and some "pumped version" of $s$ isn't in $L$. This is clearly the hardest part, and the part I don't have a great procedure for. Generally trying a few things ends up with something working eventually. For "counting" based ones like the one you posted (some number of one symbol is equal to some number of some other symbol), usually having the part you pump be of the form $a^k$ is enough to mess with the counting.

Answer 2

An alternative proof uses Parikh's theorem. If $L$ were regular, then by Parikh's theorem the set $S := \{(n,n^2) : n \geq 2\}$ would be semilinear. In particular, there is an infinite linear subset, and so there must exist $a_0,b_0,a_1,b_1$ (with $(a_1,b_1) \neq (0,0)$) such that $(a_0,b_0) + \mathbb{N}(a_1,b_1) \subseteq S$, and in particular it must be the case that $b_0 + nb_1 = (a_0 + na_1)^2$ for all $n \geq 0$. However, this is impossible: it implies that $a_0 + na_1 = o(b_0 + nb_1)$, which is only possible when $a_1 = 0$, a case that is easy to rule out directly (since $b_1 \neq 0$ necessarily holds in that case).