# Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

$$L=\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$$

I tried writing $$L$$ as the union of the language created with $$j$$ odd and the one with $$j$$ even.

When $$j$$ is odd, I can prove using the pumping lemma that it is not a cfl.

When $$j$$ is even, I can prove that it is a cfl by writing a context-free grammar for it.

But then the union of a cfl and a non-cfl doesn't really help me prove $$L$$ is a cfl or not.

How do I proceed?

• Try to show that $a^ib^{i^2}$ is not context free. That might help. Commented Jun 2, 2022 at 12:48
• @NarekBojikian I can do that, but I don't really see how this will help me. Can you please explain? Commented Jun 2, 2022 at 13:13
• @Pete42 Have you tried proving $L$ is not cfl using pumping lemma? Commented Jun 2, 2022 at 13:19
• @JohnL. Well, I was not sure it would yield the correct solution. But since you mentioned it, is it correct to choose $j=2p + 1$, where $p$ is the constant from the pumping lemma, so that I get a string from the odd case. I can prove this is not CFL and it is contained in L, so this proves L is not CFL ? It seems to ignore the case where $j$ is even, but according to the statement of the pumping lemma it seems correct. Is this solution right ? Commented Jun 2, 2022 at 13:41
• The union of disjoint grammars is easier to reason about than general union.
– rici
Commented Jun 2, 2022 at 18:12

We can prove $$L$$ is not a CFL using the pumping lemma by choosing the string $$a^pb^{1}a^{p^2+1}$$, where $$p$$ is the constant in the pumping lemma.

Since $$|vwx|\le{p}$$, we can have:

If $$v$$ or $$x$$ contains more than one type of letter, so when we pump the order breaks.

If both $$v$$ and $$x$$ contain only $$a$$'s then when we pump the sum breaks because we either don't add enough letters or we add too much(the case with $$i^2$$ when pumping the first $$a$$'s).

The only other case is when either $$v=b$$ or $$x=b$$ that we solve by pumping $$v$$ down to 0, so the new string will match the $$j$$ even case with $$j=0$$, but $$i + j = p^2$$ while $$k = p^2 + 1$$.

• @JohnL. I updated. Is it ok? Commented Jun 2, 2022 at 18:26
• $v=b$, $w=\epsilon$, $x=a^{p^2+1-p}$. Pumping $v$ down to $\epsilon$, we get $a^pa^p\in L$. Commented Jun 2, 2022 at 23:17
• Yea, you're right. The pumping lemma solution isn't that easy after all or I didn't pick the right string at least. Commented Jun 3, 2022 at 12:03

Note that the context-free languages are closed under left-quotient as well as intersection with regular languages, as John L. noted.

Assume, for contradiction, that $$L$$ was context-free. Then $$L_1 := L \cap a^*ba^* = \{a^iba^{i^2 + 1} : i \geq 0\}$$ and $$L_2 := a^*ba \setminus L_1 = \{a^{i^2} : i \geq 0\}$$ must be context-free as well. If $$L_2$$ is context-free then it must also be regular, since it only contains one letter.

But using the Pumping lemma for regular languages it can be shown that $$L_2$$ isn't regular, contradicting our assumption that $$L$$ is context-free ↯