0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Try using Parikh's theorem. $\endgroup$ Jan 15 '18 at 21:22
0
$\begingroup$

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.

$\endgroup$

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