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 } :
- S → a b c
- S → a S B c
- c B → W B
- W B → W X
- W X → B X
- B X → B c
- 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)?