# Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? [duplicate]

Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free? I should probably use Ogden's lemma, but I don't know how to do that in this case.

• Try using Parikh's theorem. Jan 15 '18 at 21:22

If $L$ is context-free, then according to Parikh's theorem, the set $\{(p,q) : p,q \geq 1, p \geq q^2 \text{ or } q \geq p^2\}$ is semilinear, say it is the union of the linear sets $L_i$. Each linear set is either a singleton or of the form $(a,b) + \mathbb{N}(x,y)$. In the latter case, I claim that either $x = 0$ or $y = 0$. Otherwise, for large $n$ we have $\frac{a+nx}{b+ny} \approx \frac{x}{y}$, and in particular it isn't the case that $a+nx \geq (b+ny)^2$ or $b+ny \geq (a+nx)^2$.
It follows that there exists a finite set $F$ such that $$\bigcup_i L_i = F \cup \bigcup_j (p_j+\mathbb{N}t_j,q_j) \cup \bigcup_k (p'_k,q'_k+\mathbb{N}t'_k).$$ Let now $z \geq 2$ be some integer larger than all indices in $F$ and all $p_j,q_j,t_j,p'_k,q'_k,t'_k$, and consider the point $(z^2,z)$, which should be contained in this union. By construction, it is not contained in $F$ or in any $(p_j+\mathbb{N}t_j,q_j)$. If $(z^2,z) = (p'_k,q'_k+nt'_k)$ and $(p,q) = (p'_k,q'_k+(n+1)t'_k)$, then we must have $q \geq p^2$, which implies that $z+t'_k \geq z^2$. This again contradicts our choice of $z$. It follows that $(z^2,z)$ is missing from the union, and we reach a contradiction.