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

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

• What did you try to solve it yourself? – fade2black Aug 2 '17 at 7:14
• S -> aSb | aSbb | epsilon – Alyssa Skyler Aug 2 '17 at 7:18
• There is a post on how to prove a language a CF. You should also check if it is really CF. – fade2black Aug 2 '17 at 7:28
• Please try sometime trying to solve yourself. We can help you later if you get stuck. – fade2black Aug 2 '17 at 7:46
• Possible duplicate of How to prove that a language is context-free? – David Richerby Aug 2 '17 at 11:19

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.

• Awesome! With this in mind, one can design an elementary proof: if $w=a^i b^j \in L$, then if $i \ne j$ and $i \ge 3$, it is easy to prove that $w$ has the form $a^2 S b^3$ with $S \in L$. In the same way, if $i = j$ and $i\ge 2$, one proves that $w$ has the form $a S b$ with $S\in L$. The only remaining cases are $a b$ and $a^2 b^3$. Conversely, if $S\in L$ then $a S b$ and $a^2 S b^3\in L$. – Gribouillis Aug 2 '17 at 10:26
• Much appreciated answer – Alyssa Skyler Aug 2 '17 at 11:13