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

  • $\begingroup$ can you show us a string in this language? $\endgroup$ – JimN Dec 14 '17 at 4:08
  • $\begingroup$ @JimN I can try not sure if I'm right. As I noted I find this set theoretic definition hard to grasp due to the symol usage. I think things of the nature $ abaaba $ are in the language but not things like $aaaabb $ or $ bbaaaa$ due to the exclusion in the property of the set. Essentially, satisfying the property by placing contigous a's or b's letting only mixtures of non-contigous a's / b's in the language. $\endgroup$ – Overflow2341313 Dec 14 '17 at 4:12
  • $\begingroup$ Almost. The number of b's is the square of the number of a's . So swap your a's and b's. Now pick a string that is 'sufficiently long' (that is, write some string with with more than $n$ symbols) $\endgroup$ – JimN Dec 14 '17 at 4:18
  • $\begingroup$ @JImN Right I get that part. Essentially the start of the proof is.... (from memory off the top of my head...) Suppose it is regular then by the pumping lemma there exists a DFA which accepts L. Let k be the number specified by the pumping lemma and let $ s \in L $ where $ length(s) \ge k $. By the pumping lemma we must have that there exists a decompositon , $ s = xyz $, such that the properties are satisfied. From here I fail to see the decomposition in order to break the third property. Pumping it is easy to break once that's found. $\endgroup$ – Overflow2341313 Dec 14 '17 at 4:21
  • $\begingroup$ Pick a form of the string first. You'll have to pick one. Just not the $a^{*}b^{*}$ or $b^{*}a^{*}$ formats. $\endgroup$ – JimN Dec 14 '17 at 4:27

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.

  • $\begingroup$ Welcome, and thanks for answering! For your information, we have collected some reference questions that are supposed to help people with many types of exercise problems. Before investing time to write an answer (esp. the umpteenth Pumping lemma proof), it's often a good idea to check if one of the questions from the list covers the question. Happy answering! $\endgroup$ – Raphael Dec 14 '17 at 6:58

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

  • $\begingroup$ I don´t understand, why $b_0 + nb_1$ has to be less than $a_0 + na_1$? $\endgroup$ – rotia Dec 16 '17 at 3:06
  • $\begingroup$ It seems I got $a,b$ mixed up $\endgroup$ – Yuval Filmus Dec 16 '17 at 5:46

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.