# Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I am trying to find a context sensitive grammar for the type-1 language

$$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$$

I can construct the first part with

\begin{align*} S &\to aSbB \mid B \mid \epsilon\\ B &\to bB \mid \epsilon\\ \end{align*}

but how do I continue from there? I tried

\begin{align*} S &\to aSbBcC \mid B \mid \epsilon\\ B &\to bBcC \mid \epsilon\\ CB &\to BC \\ C &\to cC \end{align*} but this does not seem to work e.g. $$S \to aSbBC \to aaSbBCbBC \to aabBCbBC$$

## 1 Answer

\begin{align*} S &\to XABS' \mid XBS' \mid XS' \mid XAB \mid XB \mid X \mid \epsilon \\ S' &\to ABCS' \mid BCS' \mid CS' \mid C \\ \\ BA & \to AB \\ CA & \to AC \\ CB & \to BC \\ \\ XA &\to aX \\ X &\to Y \\ YB &\to bY\\ Y &\to Z \\ ZC &\to cZ \\ Z &\to c \end{align*}

For the intuition behind this construction see this question.

• Technically, that's not a CSG, right? The last rule could only appear in a non-restricted grammar. – rici Apr 27 '20 at 20:19
• Right, I edited my answer. Also the productions of the form $PQ \to \alpha \beta$, where $\alpha$ and $\beta$ have length at least $1$ and can contain both terminals and non-terminals, are technically not CS. However, they can be simulated as $PQ \to RQ, \quad RQ \to RU, \quad RU \to \alpha U, \quad \alpha U \to \alpha\beta$, where $R$ and $U$ are newly added non-terminals. – Steven Apr 27 '20 at 20:58