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?

  • $\begingroup$ Perhaps have a look at the example in Wikipedia, technically your grammar is "noncontracting" rather than context-sensitive. $\endgroup$ Commented Feb 19, 2021 at 17:22

2 Answers 2


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


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.

  • $\begingroup$ The fact that it is possible to derive a sentential form that is not a sentence from which no more productions can be applied does not imply, per se, that the grammar is incorrect. Of course, in this particular case the grammar IS incorrect. $\endgroup$
    – Steven
    Commented Feb 18, 2021 at 15:28
  • $\begingroup$ As @Nathaniel pointed out, but I think you can apply the 1. rule then the 3. the result is abXcZ. Isn't it? $\endgroup$ Commented Feb 18, 2021 at 15:40
  • 1
    $\begingroup$ Yes, I said it wrongly, but in the case of the previous rules, no sequence of derivation could finish except for $S\rightarrow abc$. Thanks for pointing out this fact. @Erhard Dinhobl: the rules have changed in the original post and my current answer does not apply the the current rules. $\endgroup$
    – Nathaniel
    Commented Feb 18, 2021 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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