Mistake in Wikipedia CSG example?

Question

I'm confused about the example given in Wikipedia article about Context-sensitive grammar:

https://en.wikipedia.org/wiki/Context-sensitive_grammar

Disclamer: I've already changed discussed section in wikipedia article, so current state of article will differ from what I'm discussing in this question. Original version is here: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366

The following grammar, with start symbol S, generates the canonical non-context-free language { anbncn : n ≥ 1 } :

1. S → a b c
2. S → a S B c
3. c B → W B
4. W B → W X
5. W X → B X
6. B X → B c
7. b B → b b

They do not claim directly that this grammar is context-sensitive, but next sentence implies that that they consider it as context-sensitive:

rules 3 to 6 allow for successively exchanging each cB to Bc (four rules are needed for that since a rule cB → Bc wouldn't fit into the scheme αAβ → αγβ)

So they appeal to the canonical form of context-sensitive grammar rules: αAβ → αγβ, implying that whole grammar is context-sensitive.

What I'm confused about is rule #3, which seems to be not fitting scheme αAβ → αγβ. I consider terminal $c$ here as part of $\alpha$, variable $B$ as $A$ in scheme, $\beta$ is empty. This implies that $cB$ can not produce $WB$, as $c$ should be saved on same place ($cB\rightarrow c\dots$).

Did I missed something or this grammar was really placed here mistakenly (as it is not real context-sensitive)?

Answer 1

If I am not mistaken, a simpler CS grammar is possible. Here it is:

1. $S \rightarrow ABSc$
2. $S \rightarrow Abc$
3. $BA \rightarrow XA$
4. $XA \rightarrow XY$
5. $XY \rightarrow AY$
6. $AY \rightarrow AB$
7. $A \rightarrow a$
8. $Bb \rightarrow bb$.

A derivation for the string $aaabbbccc$ is

$\Rightarrow_1 ABSc\\\Rightarrow_1 AB\textbf{ABSc}c\\\Rightarrow_2 ABAB\textbf{Abc}cc\\\Rightarrow_3 A\textbf{XA}BAbccc\\\Rightarrow_4 A\textbf{XY}BAbccc\\\Rightarrow_5 A\textbf{AY}BAbccc\\\Rightarrow_6 A\textbf{AB}BAbccc\\\dots\\\Rightarrow_{3-6}AAB\textbf{AB}bccc\\\Rightarrow_{3-6}AA\textbf{AB}Bbccc\\\Rightarrow_{7...}\textbf{aaa}BBbccc\\\Rightarrow_8 aaaB\textbf{bb}ccc\\\Rightarrow_8 aaa\textbf{bb}bccc$

Answer 2

Actually as several viewers agreed original grammar was incorrect. As @EmilJeřábek noticed, there was already discussion of this problem here: https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language

So it appears that neither 7-rule grammar (which I was inquiring above in my question), neither 9-rule grammar which was here before and present in other-languages articles, both are incorrect. This 9-rule grammar:

1. S → a B C
2. S → a S B C
3. C B → W B
4. W B → W C
5. W C → B C
6. a B → a b
7. b B → b b
8. b C → b c
9. c C → c c

is incorrect example as it can produces words of the form "aaa bb cccc" `which doesn't fit formula $a^nb^nc^n$.

So I suggest following enhancement of this grammar by replacing rules 3-5 to four rules:

1. S → a B C
2. S → a S B C
3. C B → C Z
4. C Z → W Z
5. W Z → W C
6. W C → B C
7. a B → a b
8. b B → b b
9. b C → b c
10. c C → c c

Rules 3-6 will help avoid problem with replacing CB to WB and then WC to BC.

EDIT: As @EmilJeřábek suggested again, rules #7 and #8 can be simplified to one rule $B\rightarrow b$.