Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$

Question

I tried many grammars and so far I got this one:

\begin{align} &S \to aXbZ \mid abc \\ &XZ \to Ybcc \\ &Xb \to bX \\ &bY \to Yb \\ &aY \to aa \mid aaX \end{align}

Is my grammar correct? Is there a simpler one?

Answer 1

Your grammar is not correct. To see this notice that no sentence generated by your grammar can have more than two "c"s.

Indeed, the only productions that generate one or more occurrences of "c" are $S \to abc$ and $XZ \to Ybcc$.

Clearly, if $S \to abc$ is used, the resulting sentence has exactly one "c" (no production has $S$ on its right side). Moreover, at most one $Z$ can be in any sentential form $\alpha$ and, when this happens, $\alpha$ contains no "c". This is true because the only production that generates $Z$ is $S \to aXbZ$. Then $XZ \to Ybcc$ can be applied at most once from $\alpha$.

Answer 2

Edit: my answer applies to the first post before modification.

It seems to me that your grammar is not correct. For example, if you use the first rule for $S$ and then the second rule for $S$, you get $aabcXY$ and no rule can be applied from there.

Inspired by what you proposed, it seems that the following rules are right : $$S \rightarrow aSXY | abc$$ $$cX \rightarrow Xc$$ $$bX \rightarrow bb$$ $$cY \rightarrow cc$$ The first rule guarantees that there are as many $a$'s as there are ($b$ and $X$) and ($c$ and $Y$). The third rule move $X$'s to the left until it is next to a $b$. The last 2 rules replace $X$'s with $b$'s and $Y$'s with $c$'s.