Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I was wondering, in my other topic, how to find grammar for: $\left\{ a^n b^n c^n: n\ge 1 \right\}$ when I found this. Context-sensitive grammars is completely new topic for me and I don't understand few things.

Firstly: why is it OK? I think I get basic intuition behind this approach - we generate as many $a$ as we need and simultaneously same number of $B, \ C$ - space for the letters $b, \ c$. Then we use some kind of bubble sort to swap all adjacent $CB$ to get string in form: $a...aB...BC...C$ then we will easily get desired string using few steps.

But why can't we just use simply rule $CB\rightarrow BC$ and we need to do this transformation in few steps using nonterminal $H$?

Second question: is order of rules in context-sensitive grammars relevant? Because when we use this grammar like that: $$S\rightarrow aSBC\rightarrow aaBCBC\rightarrow aabCBC\rightarrow aabcBC$$ then we are in dead end, but I suppose I don't understand something and everything is OK. But why? Can you explain it to me? I would be very grateful.

share|cite|improve this question
up vote 1 down vote accepted

The use of $H$ is there to force you to finish swapping the $B$s and $C$s before converting them to $b$s and $c$s. Otherwise, you could easily generate $aabcbc$, for example.

As for the second part, yes the order of application of rules in a context sensitive grammar is important, because one rule application may use up part of the string that another rule might otherwise use.

share|cite|improve this answer
That explains a lot. Thank you so much! :-) – xan Feb 24 '13 at 18:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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