PDA or CFG for language $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Question

Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$

Answer 1

Let me prove a more general theorem.

For $A \subseteq \mathbb{N}^2$, the language $L(A) = \{a^i b^j : (i,j) \in A \}$ is context-free iff $A$ is semi-linear.

One direction is Parikh's theorem. In the other direction, it suffices to show that $L(A)$ is context-free if $A$ is linear (since every semi-linear set is a union of linear sets). Indeed, suppose that $A = (i_0,j_0) + \sum_{t=1}^m \mathbb{N} (i_t,j_t)$. Then $L(A)$ is generated by the grammar $$ S \to a^{i_0} b^{j_0} \mid a^{i_1} S b^{j_1} \mid \cdots \mid a^{i_m} S b^{j_m}. $$

A classical result shows that a set is semi-linear iff it is definable in Presburger arithmetic. In particular, if $A$ is the solution set of a system of linear inequalities with rational coefficients (as in your example) then $A$ is semi-linear and so so $L(A)$ is context-free.

In your particular case, ignoring for the moment the condition $i > 0$, we have $$ A = \{ (i,j) : 2i \leq 2j \leq 3j \} = \mathbb{N}(1,1) + \mathbb{N}(2,3). $$ Indeed, clearly $(1,1),(2,3) \in A$ and $A$ is closed under addition, and so $\mathbb{N}(1,1) + \mathbb{N}(2,3) \subseteq A$. In the other direction, suppose that $2i \leq 2j \leq 3i$. Then $$ (3i-2j)(1,1) + (j-i)(2,3) = (i,j). $$ This shows that the following grammar generates your language without the condition $i > 0$: $$ S \to \epsilon \mid aSb \mid a^2Sb^3. $$ If we bring back the condition $i > 0$, then we get the decomposition $$ A = \{ (i,j) : 2i \leq 2j \leq 3j \text{ and } i > 0 \} = \{(1,1) + (2,3)\} + \mathbb{N}(1,1) + \mathbb{N}(2,3), $$ leading to the grammar $$ S \to ab \mid a^2b^3 \mid aSb \mid a^2Sb^3. $$

In these examples all linear sets were generated by two vectors ("periods"). Indeed, a classical result (following from Caratheodory's theorem; see for example Slide 24 of these slides by Widjaja Lin) shows that every semi-linear set in dimension $k$ (in our case, $k=2$) is the union of linear sets with at most $k$ periods.

If you are interested in the algorithmic side of things, The taming of the semi-linear set is a good starting point.