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$


$$ \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.

  • $\begingroup$ Technically, that's not a CSG, right? The last rule could only appear in a non-restricted grammar. $\endgroup$ – rici Apr 27 '20 at 20:19
  • $\begingroup$ 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. $\endgroup$ – Steven Apr 27 '20 at 20:58

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.