0
$\begingroup$

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

$\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
4
$\begingroup$

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.

$\endgroup$
  • $\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
  • $\begingroup$ Much appreciated answer $\endgroup$ – Alyssa Skyler Aug 2 '17 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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