2
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ can you show us a string in this language? $\endgroup$
    – JimN
    Dec 14, 2017 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$ Dec 14, 2017 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, 2017 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$ Dec 14, 2017 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, 2017 at 4:27

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
  • $\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, 2017 at 6:58
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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