Can someone help with this $L= \{a^ib^j | 2i \leq 2j \leq 3i, i>0\}$
$\begingroup$
$\endgroup$
-
$\begingroup$ What did you try to solve it yourself? $\endgroup$ – fade2black Aug 2 '17 at 7:14
-
$\begingroup$ S -> aSb | aSbb | epsilon $\endgroup$ – Alyssa Skyler Aug 2 '17 at 7:18
-
2$\begingroup$ There is a post on how to prove a language a CF. You should also check if it is really CF. $\endgroup$ – fade2black Aug 2 '17 at 7:28
-
$\begingroup$ Please try sometime trying to solve yourself. We can help you later if you get stuck. $\endgroup$ – fade2black Aug 2 '17 at 7:46
-
2$\begingroup$ Possible duplicate of How to prove that a language is context-free? $\endgroup$ – David Richerby Aug 2 '17 at 11:19
$\begingroup$
$\endgroup$
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.
answered Aug 2 '17 at 9:11
-
$\begingroup$ 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$. $\endgroup$ – Gribouillis Aug 2 '17 at 10:26
-
