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.
Best Answer
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.